Some smooth divergences for ℓ 1 − \ell_{1}- approximations

Pierre Bertrand and Wolfgang Stummer · 2025

Read Some smooth divergences for ℓ 1 − \ell_{1}- approximations by Pierre Bertrand and Wolfgang Stummer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00219.txt.

Introduction

Pierre Bertrand and Wolfgang Stummer write a brief math note on distance measures between data patterns. They take smooth cases of a broad family called phi-divergences, plus a new family they name scaled shift divergences. For these cases they derive close approximations to the widely used L1 distance and L1 norm, which add up absolute gaps. The note is aimed at readers in statistics and probability who work with such measures.

Catalog record

CREATORPierre Bertrand and Wolfgang Stummer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00219

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Some smooth divergences for ℓ 1 − \ell_{1}- approximations Pierre Bertrand and Wolfgang Stummer Abstract For some smooth special case of generalized φ − \varphi- divergences as well as of new divergences (called scaled shift divergences), we derive approximations of the omnipresent (weighted) ℓ 1 − \ell_{1}- distance and (weighted) ℓ 1 − \ell_{1}- norm. 1 The generalized \varphi- divergence case It is well-known that a divergence is a real-valued function D on (a subset of) \mathbb{R}^{K}\times\mathbb{R}^{K} which has the following two properties: (i) D(\mathbf{Q},\mathbf{P})\geq 0 for K- dimensional vectors \mathbf{Q},\mathbf{P} , and (ii) D(\mathbf{Q},\mathbf{P})=0 if and only if \mathbf{Q}=\mathbf{P} . Since in general, D(\mathbf{Q},\mathbf{P})\neq D(\mathbf{P},\mathbf{Q}) and the triangle inequality is not satisfied, D(\mathbf{Q},\mathbf{P}) can be interpreted as a directed distance ; accordingly, the divergence D can be connected to geometric issues in various different ways, see e.g. the detailed discussion in Section 1.5 of [ 4 ] , and [ 16 ] . Typically, a divergence D is generated by some function \varphi . For the latter, we require for the rest of the paper: • \varphi:\,]-\infty,\infty[\rightarrow[0,\infty] is lower semicontinuous and convex, with \varphi(1)=0 ; • the effective domain dom(\varphi):=\{t\in\mathbb{R}:\varphi(t)<\infty\} has interior int(dom(\varphi)) of the form int(dom(\varphi))=\,]a,b[ for some -\infty\leq a<1<b\leq\infty ; • t\mapsto\varphi(t) is strictly convex at t=1 (i.e. it is not identically zero in the open interval ]1-\varepsilon,1+\varepsilon[ for any \varepsilon>0 , cf. e.g. Liese & Miescke [ 13 ] ). Also, we set \varphi(a):=\lim_{t\downarrow a}\varphi(t) and \varphi(b):=\lim_{t\uparrow b}\varphi(t) . For \mathbf{P}:=\left(p_{1},\ldots,p_{K}\right)\in\mathbb{R}_{>0}^{K}:=\{\mathbf{R}:=(r_{1},\ldots,r_{K})\in\mathbb{R}^{K}:\,r_{i}>0\ \text{for all}\ i=1,\ldots,K\} and \mathbf{Q}:=(q_{1},\ldots,q_{K})\in\mathbf{\Omega}\subset\mathbb{R}^{K} , we define as directed distance the generalized \varphi- divergence (generalized Csiszár-Ali-Silvey-Morimoto divergence) D_{\varphi}(\mathbf{Q},\mathbf{P}):=\sum_{k=1}^{K}p_{k}\cdot\varphi\left(\frac{q_{k}}{p_{k}}\right); (1) for a comprehensive technical treatment, see e.g. [ 3 ] . Comprehensive overviews on these important (generalized) \varphi- divergences are given in e.g. [ 14 ] , [ 19 ] , [ 4 ] , [ 5 ] , and the references therein. Notice that the \ell_{1}- distance — also called total variation distance — D_{\varphi_{TV}}(\mathbf{Q},\mathbf{P}):=\sum_{k=1}^{K}p_{k}\cdot\varphi_{TV}\negthinspace\left(\frac{q_{k}}{p_{k}}\right)=\sum_{k=1}^{K}|\,p_{k}-q_{k}\,| with \varphi_{TV}(t):=|t-1| is covered here. Another interesting example is given as follows: for any parameter-triple \alpha,\beta,\widetilde{c}\in\,]0,\infty[ we choose ]a,b[\,:=\,]-\infty,\infty\,[ and \displaystyle\varphi_{\alpha,\beta,\widetilde{c}}(t) \displaystyle:= \displaystyle\begin{cases}\widetilde{c}\cdot\alpha\cdot\Big\{\sqrt{1+\beta^{2}\cdot\Big(\frac{1-t}{\alpha}\Big)^{2}}-1+\log\frac{2\cdot\Big(\sqrt{1+\beta^{2}\cdot\Big(\frac{1-t}{\alpha}\Big)^{2}}-1\Big)}{\beta^{2}\cdot\Big(\frac{1-t}{\alpha}\Big)^{2}}\Big\}\in\,]0,\infty[,\\ \hskip 184.9429pt\textrm{if }\ t\in\,]-\infty,1[\,\cup\,]1,\infty[\,,\\ 0,\hskip 176.407pt\textrm{if }\ t=1,\end{cases} (2) (cf. Broniatowski & Stummer [ 5 ] ). Notice that \varphi_{\alpha,\beta,\widetilde{c}}(1)=0 , \varphi_{\alpha,\beta,\widetilde{c}}^{\prime}(1)=0 , \varphi_{\alpha,\beta,\widetilde{c}}(-\infty)=\infty and \varphi_{\alpha,\beta,\widetilde{c}}(\infty)=\infty . Moreover, \varphi_{\alpha,\beta,\widetilde{c}}^{\prime}(-\infty)=\varphi_{\alpha,\beta,\widetilde{c}}^{\prime}(a)=-\widetilde{c}\cdot\beta and \varphi_{\alpha,\beta,\widetilde{c}}^{\prime}(\infty)=\varphi_{\alpha,\beta,\widetilde{c}}^{\prime}(b)=\widetilde{c}\cdot\beta . Furthermore, \varphi_{\alpha,\beta,\widetilde{c}}(\cdot) is strictly convex and smooth (i.e. of C^{\infty}- type), and \varphi_{\alpha,\beta,\widetilde{c}}(t)\leq\widetilde{c}\cdot\beta\cdot|t-1| with equality iff t=1 . From ( 2 ), we construct the generalized \varphi- divergence \displaystyle\hskip-14.22636ptD_{\varphi_{\alpha,\beta,\widetilde{c}}}(\mathbf{Q},\mathbf{P})=\sum\limits_{k=1}^{K}p_{k}\cdot\varphi_{\alpha,\beta,\widetilde{c}}\Big(\frac{q_{k}}{p_{k}}\Big) \displaystyle\hskip-14.22636pt=\begin{cases}\widetilde{c}\cdot\alpha\cdot\sum\limits_{k=1}^{K}p_{k}\cdot\Big\{\sqrt{1+\beta^{2}\cdot\Big(\frac{1-\frac{q_{k}}{p_{k}}}{\alpha}\Big)^{2}}\,-\,1+\log\frac{2\cdot\Big(\sqrt{1+\beta^{2}\cdot\Big(\frac{1-\frac{q_{k}}{p_{k}}}{\alpha}\Big)^{2}}\,-\,1\Big)}{\beta^{2}\cdot\Big(\frac{1-\frac{q_{k}}{p_{k}}}{\alpha}\Big)^{2}}\Big\},\\ \hskip 187.78836pt\textrm{if }\ \mathbf{P}\in\mathbb{R}_{>0}^{K},\mathbf{Q}\in\mathbb{R}^{K}\backslash\{\mathbf{P}\}\,,\\ 0,\hskip 177.82971pt\textrm{if }\ \mathbf{Q}=\mathbf{P}.\end{cases} (3) As a background, in [ 5 ] we have shown that for any fixed \mathbf{P}\in\mathbb{R}_{>0}^{K} with M_{\mathbf{P}}=\sum_{i=1}^{K}p_{i}\in\,]0,\infty[ there holds for \varphi:=\varphi_{\alpha,\beta,\widetilde{c}} the important condition M_{\mathbf{P}}\cdot\varphi(t)=\sup_{z\in\mathbb{R}}\Big(z\cdot t-\log\int_{\mathbb{R}}e^{zy}d\widetilde{\mathbb{\zeta}}(y)\Big),\qquad t\in\mathbb{R}, for some probability distribution \widetilde{\mathbb{\zeta}} on the real line such that the function z\mapsto MGF_{\widetilde{\mathbb{\zeta}}}(z):=\int_{\mathbb{R}}e^{zy}d\widetilde{\mathbb{\zeta}}(y) is finite on some open interval containing zero. Indeed, the corresponding distribution \widetilde{\zeta}[\,\cdot\,]:=\widetilde{\zeta}_{\alpha,\beta,\widetilde{c}}[\,\cdot\,]:=\Pi[\widetilde{W}\in\cdot\,] is the comfortably simulable generalized Laplace distribution of a random variable \widetilde{W}:=1+\widetilde{Z}_{1}-\widetilde{Z}_{2} , where \widetilde{Z}_{1} and \widetilde{Z}_{2} are auxiliary random variables which are independent and identically GAM(M_{\mathbf{P}}\cdot\widetilde{c}\cdot\beta,M_{\mathbf{P}}\cdot\widetilde{c}\cdot\alpha)- distributed. Accordingly, \widetilde{W} has expectation 1 and variance 2\cdot\frac{(M_{\mathbf{P}}\cdot\widetilde{c}\cdot\alpha)^{2}}{M_{\mathbf{P}}\cdot\widetilde{c}\cdot\beta}=2M_{\mathbf{P}}\cdot\widetilde{c}\cdot\frac{\alpha^{2}}{\beta} . In the following, we show how the \varphi- divergence ( 3 ) can be employed to achieve smooth approximations of the \ell_{1}- distance as well as the \ell_{1}- norm: Proposition 1 (a) For all t\in\,]-\infty,\infty[ , \beta\in\,]0,\infty[ and \widetilde{c}\in\,]0,\infty[ there holds \lim_{\alpha\rightarrow 0_{+}}\varphi_{\alpha,\beta,\widetilde{c}}(t)\ =\ \widetilde{c}\cdot\beta\cdot|t-1|. (b) For all t\in\,]-\infty,\infty[ , \alpha\in\,]0,\infty[ and \beta\in\,]0,\infty[ there holds \lim_{\frac{\alpha}{\beta}\rightarrow 0_{+}}\varphi_{\alpha,\beta,1/\beta}(t)\ =\ |t-1|. (c) For all \beta\in\,]0,\infty[ , \widetilde{c}\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} and \mathbf{P}\in\mathbb{R}_{>0}^{K} there holds \lim_{\alpha\rightarrow 0_{+}}D_{\varphi_{\alpha,\beta,\widetilde{c}}}(\mathbf{Q},\mathbf{P})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}|q_{k}-p_{k}|\ =\ \widetilde{c}\cdot\beta\cdot||\mathbf{Q}-\mathbf{P}||_{1}. (d) For all \alpha\in\,]0,\infty[ , \beta\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} and \mathbf{P}\in\mathbb{R}_{>0}^{K} there holds \lim_{\frac{\alpha}{\beta}\rightarrow 0_{+}}D_{\varphi_{\alpha,\beta,1/\beta}}(\mathbf{Q},\mathbf{P})\ =\ \sum_{k=1}^{K}|q_{k}-p_{k}|\ =\ ||\mathbf{Q}-\mathbf{P}||_{1}. (4) (e) For all \alpha\in\,]0,\infty[ , \beta\in\,]0,\infty[ , \widetilde{c}\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} and all sequences (\mathbf{P}_{m})_{m\in\mathbb{N}} in \mathbb{R}_{>0}^{K} which tend (component-wise) to \mathbf{0} (i.e. \mathbf{P}_{m}\stackrel{{\scriptstyle m\rightarrow\infty}}{{\longrightarrow}}\mathbf{0} ) there holds \lim_{m\rightarrow\infty}D_{\varphi_{\alpha,\beta,\widetilde{c}}}(\mathbf{Q},\mathbf{P}_{m})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}|q_{k}|\ =\ \widetilde{c}\cdot\beta\cdot||\mathbf{Q}||_{1}; (5) especially for \mathbf{P}_{m}:=\frac{1}{m}\cdot\mathbf{1} (i.e. each of the K components has value \frac{1}{m} ) one has \lim_{m\rightarrow\infty}D_{\varphi_{\alpha,\beta,\widetilde{c}}}(\mathbf{Q},\frac{1}{m}\cdot\mathbf{1})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}|q_{k}|\ =\ \widetilde{c}\cdot\beta\cdot||\mathbf{Q}||_{1}. The proof of Proposition 1 will be given in Section 4 below. 2 The case of the scaled shift-divergence case Instead of the generalized \varphi- divergence ( 1 ), let us now construct — for \mathbf{P}\in\mathbb{R}_{>0}^{K} , \mathbf{Q}\in\mathbb{R}^{K} , \mathbf{Q}^{\ast}\in\mathbb{R}^{K} and \mathbf{\sigma}\in\mathbb{R}_{>0}^{K} — the new scaled shift divergence D_{\varphi,\mathbf{P},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ :=\ \sum\limits_{k=1}^{K}p_{k}\cdot\varphi\negthinspace\left(\frac{q_{k}-q_{k}^{\ast}}{p_{k}\cdot\sigma_{k}}+1\right) where the divergence generator \varphi has the general properties declared in the beginning of Section 1 . Notice that \mathbf{P} plays a different role — namely that of a weight/scaling — than in ( 1 ). Clearly, there hold the divergence properties D_{\varphi,\mathbf{P},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\geq 0 , with equality if and only if \mathbf{Q}=\mathbf{Q}^{\ast} . For the special choice \varphi:=\varphi_{\alpha,\beta,\widetilde{c}} (cf. ( 2 )) we end up with \displaystyle\hskip-5.69046ptD_{\varphi_{\alpha,\beta,\widetilde{c}},\mathbf{P},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ :=\ \sum\limits_{k=1}^{K}p_{k}\cdot\varphi_{\alpha,\beta,\widetilde{c}}\negthinspace\left(\frac{q_{k}-q_{k}^{\ast}}{p_{k}\cdot\sigma_{k}}+1\right) \displaystyle\hskip-5.69046pt=\begin{cases}\widetilde{c}\cdot\alpha\cdot\sum\limits_{k=1}^{K}p_{k}\cdot\Big\{\sqrt{1+\frac{\beta^{2}}{\alpha^{2}}\cdot\Big(\frac{q_{k}-q_{k}^{\ast}}{p_{k}\cdot\sigma_{k}}\Big)^{2}}-1+\log\frac{2\cdot\Big(\sqrt{1+\frac{\beta^{2}}{\alpha^{2}}\cdot\Big(\frac{q_{k}-q_{k}^{\ast}}{p_{k}\cdot\sigma_{k}}\Big)^{2}}-1\Big)}{\frac{\beta^{2}}{\alpha^{2}}\cdot\Big(\frac{q_{k}-q_{k}^{\ast}}{p_{k}\cdot\sigma_{k}}\Big)^{2}}\Big\}\in\,]0,\infty[,\\ \hskip 244.69386pt\textrm{if }\ \mathbf{Q}\in\mathbb{R}^{K}\backslash\{\mathbf{Q}^{\ast}\}\,,\\ 0,\hskip 236.15796pt\textrm{if }\ \mathbf{Q}=\mathbf{Q}^{\ast}.\end{cases} For this, we can deduce the following weighted \ell_{1}- distance approximations: Proposition 2 (a) For all \beta\in\,]0,\infty[ , \widetilde{c}\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} , \mathbf{Q}^{\ast}\in\mathbb{R}^{K} , \mathbf{P}\in\mathbb{R}_{>0}^{K} and \mathbf{\sigma}\in\mathbb{R}_{>0}^{K} there holds \lim_{\alpha\rightarrow 0_{+}}D_{\varphi_{\alpha,\beta,\widetilde{c}},\mathbf{P},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}\frac{|q_{k}-q_{k}^{\ast}|}{\sigma_{k}} where the latter is (a multiple of) a weighted \ell_{1}- distance between \mathbf{Q} and \mathbf{Q}^{\ast} . (b) For all \alpha\in\,]0,\infty[ , \beta\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} , \mathbf{Q}^{\ast}\in\mathbb{R}^{K} , \mathbf{P}\in\mathbb{R}_{>0}^{K} , \mathbf{\sigma}\in\mathbb{R}_{>0}^{K} we get \lim_{\frac{\alpha}{\beta}\rightarrow 0_{+}}D_{\varphi_{\alpha,\beta,1/\beta},\mathbf{P},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ =\ \sum_{k=1}^{K}\frac{|q_{k}-q_{k}^{\ast}|}{\sigma_{k}}. (6) (c) For all \alpha\in\,]0,\infty[ , \beta\in\,]0,\infty[ , \widetilde{c}\in\,]0,\infty[ , \mathbf{Q}\in\mathbb{R}^{K} , \mathbf{Q}^{\ast}\in\mathbb{R}^{K} , \mathbf{\sigma}\in\mathbb{R}_{>0}^{K} and all sequences (\mathbf{P}_{m})_{m\in\mathbb{N}} in \mathbb{R}_{>0}^{K} which tend to \mathbf{0} (i.e. \mathbf{P}_{m}\stackrel{{\scriptstyle m\rightarrow\infty}}{{\longrightarrow}}\mathbf{0} ) there holds \lim_{m\rightarrow\infty}D_{\varphi_{\alpha,\beta,\widetilde{c}},\mathbf{P}_{m},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}\frac{|q_{k}-q_{k}^{\ast}|}{\sigma_{k}}; (7) in particular, for \mathbf{P}_{m}:=\frac{1}{m}\cdot\mathbf{1} there holds \lim_{m\rightarrow\infty}D_{\varphi_{\alpha,\beta,\widetilde{c}},\frac{1}{m}\cdot\mathbf{1},\mathbf{\sigma}}^{new}(\mathbf{Q},\mathbf{Q}^{\ast})\ =\ \widetilde{c}\cdot\beta\cdot\sum_{k=1}^{K}\frac{|q_{k}-q_{k}^{\ast}|}{\sigma_{k}}. For the special choice \mathbf{Q}^{\ast}=\mathbf{0} in (a),(b),(c) we immediately obtain the corresponding limit assertions for the weighted \ell_{1}- norm . The proof of Proposition 2 will be given in Section 4 below. 3 Some visualizations In the following, we visualize some of the above convergences in a concrete context, say, at a LASSO minimizer point (cf. Tibshirani [ 18 ] ) \widehat{\mathbf{Q}}\in\argmin_{\mathbf{Q}\in\mathbb{R}^{K}}\Big(\sum_{i=1}^{n}\Big(y_{i}-\sum_{k=1}^{K}x_{i,k}\cdot q_{k}\Big)^{2}+\lambda\cdot||\mathbf{Q}||_{1}\Big), with data observations y_{i} ( i=1,\ldots,n) , deterministic explanatory variables x_{i,k} and \ell_{1}- norm-regularization (penalization) parameter \lambda\geq 0 . This LASSO task is — as e.g. discussed in Chapter 9 of Theodoridis [ 17 ] — equivalent to finding the minimizer for the basis pursuit denoising problem (cf. Donoho et al. [ 10 ] , see also e.g. Candès et al. [ 7 ] , Lustig et al. [ 15 ] , Candès [ 8 ] , Candès et al. [ 9 ] , Goldstein & Osher [ 12 ] , Zhang et al. [ 20 ] , Edgar et al. [ 11 ] ) \displaystyle\min_{\mathbf{Q}\in\mathbf{\Omega}}\,||\mathbf{Q}||_{1} (8) \displaystyle\textrm{with}\quad\mathbf{\Omega}:=\Big\{\mathbf{Q}\in\mathbb{R}^{K}:\,\sum_{i=1}^{n}\Big(y_{i}-\sum_{k=1}^{K}x_{i,k}\cdot q_{k}\Big)^{2}\leq\varepsilon\Big\} for chosen fitting-quality parameter \varepsilon>0 . In the light of this, and in order to prepare for forthcoming studies dealing with the (smooth bare-simulation-type, cf. [ 5 ] , [ 6 ] ) optimization of the corresponding smoothed version of ( 8 ), it is reasonable to compare ||\widehat{\mathbf{Q}}||_{1} with its smoother approximations D_{\varphi_{\alpha,\beta,1/\beta}}\Big(\widehat{\mathbf{Q}},\frac{1}{m}\cdot\mathbf{1}\Big) and D_{\varphi_{\alpha,\beta,1/\beta},\frac{1}{m}\cdot\mathbf{1},\mathbf{1}}^{new}(\widehat{\mathbf{Q}},\mathbf{0}) for various different parameter constellations (\alpha,\beta,m) (cf. Proposition 1 (d) and Proposition 2 (b)). In the following, we analyse this for the LASSO-solution generated by the Scikit-learn package by the code given in Figure 1 (a), where K=5001 . Accordingly, we get ||\widehat{\mathbf{Q}}||_{1}=142970.51 (with a performance score of about 0.9997 ). In order to visually demonstrate the approximations for some of the above-mentioned limits, let us always choose (say) \alpha=1 . Concerning ( 4

Read the complete text