Constant along primal rays conjugacies and the l₀ pseudonorm

Abstract

The so-called ${\ell }_0$ pseudonorm on ${\mathbb{R}}^d$ counts the number of nonzero components of a vector. For exact sparse optimization problems – with the ${\ell }_0$ pseudonorm standing either as criterion or in the constraints – the Fenchel conjugacy fails to provide relevant analysis. In this paper, we display a class of conjugacies that are suitable for the ${\ell }_0$ pseudonorm. For this purpose, we suppose given a (source) norm on ${\mathbb{R}}^d$. With this norm, we define, on the one hand, a sequence of so-called coordinate-k norms and, on the other hand, a coupling between ${\mathbb{R}}^d$ and itself, called Capra (constant along primal rays). Then, we provide formulas for the Capra-conjugate and biconjugate, and for the Capra subdifferentials, of functions of the ${\ell }_0$ pseudonorm, in terms of the coordinate-k norms. As an application, we provide a new family of lower bounds for the ${\ell }_0$ pseudonorm, as a fraction between two norms, the denominator being any norm.

Keywords:

• ${\ell }_0$ pseudonorm
• Fenchel–Moreau conjugacy
• Capra conjugacy
• coordinate-k norm

2010 Mathematics Subject Classifications:

• 46N10
• 49N15
• 46B99
• 52A41
• 90C46

Acknowledgments

The authors want to thank Guillaume Obozinski for discussions on first versions of this work, as well as the anonymous Referee and Associate Editor whose comments helped us improve the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Here, following notation from Game Theory, we have denoted by $-K$ the complementary subset of K in $\text{⟦}1,d\text{⟧}$: $K\cup (-K)=\text{⟦}1,d\text{⟧}$ and $K\cap (-K)=set$.

2 The notation $\bigcup _{|K|\le k}$ is a shorthand for $\bigcup _{K\subset \text{⟦}1,d\text{⟧},|K|\le k}$.

3 The notation $\underset{|K|\le k}{sup}$ is a shorthand for $\underset{K\subset \text{⟦}1,d\text{⟧},|K|\le k}{sup}$.

4 In what follows, by ‘or’ we mean the so-called exclusive or (exclusive disjunction). Thus, every ‘or’ should be understood as ‘or $x\ne 0$ and’

5 See footnote 4.

6 In (34g(34g) $\begin{array}{rl}((\varphi \circ {\ell }_0{)}^{¢}{)}^{{\star }^{\prime }}\left(x\right)& =\underset{\begin{array}{c}\left({\lambda }_0,{\lambda }_1,\dots ,{\lambda }_d\right)\in {\mathrm{\Delta }}_{d+1}\\ x\in \sum _{j=1}^d{\lambda }_j{\mathbb{B}}_{\left(j\right)}^{\mathcal{R}}\end{array}}{min}\sum _{j=0}^d{\lambda }_j\varphi \left(j\right),\mathrm{\forall }x\in {\mathbb{R}}^d.\end{array}$(34g) ), the sum starts from $j=0$, whereas in (34h(34h) $\begin{array}{rl}((\varphi \circ {\ell }_0{)}^{¢}{)}^{{\star }^{\prime }}\left(x\right)& =\underset{\begin{array}{c}\left({\lambda }_0,{\lambda }_1,\dots ,{\lambda }_d\right)\in {\mathrm{\Delta }}_{d+1}\\ x\in \sum _{j=1}^d{\lambda }_j{\mathbb{S}}_{\left(j\right)}^{\mathcal{R}}\end{array}}{min}\sum _{j=1}^d{\lambda }_j\varphi \left(j\right),\mathrm{\forall }x\in {\mathbb{R}}^d,\end{array}$(34h) ) and in (34i(34i) $\begin{array}{rl}& =\underset{\begin{array}{c}{z}^{\left(1\right)}\in {\mathbb{R}}^d,\dots ,z^{\left(d\right)}\in {\mathbb{R}}^d\\ \sum _{j=1}^d{\left|\right|\left|z^{\left(j\right)}\right|\left|\right|}_{\left(j\right)}^{\mathcal{R}}\le 1\\ \sum _{j=1}^d{z}^{\left(j\right)}=x\end{array}}{min}\sum _{j=1}^d\varphi \left(j\right){\left|\right|\left|z^{\left(j\right)}\right|\left|\right|}_{\left(j\right)}^{\mathcal{R}},\mathrm{\forall }x\in {\mathbb{R}}^d,\end{array}$(34i) ), the sum starts from $j=1$

7 In convex analysis, one does not use the notation ${}^{{\star }^{\prime }}$, but simply the notation ${}^{{\star }^{\prime }}$, as it is often the case that $\mathbb{X}=\mathbb{Y}$