Abstract
The so-called pseudonorm on
counts the number of nonzero components of a vector. For exact sparse optimization problems – with the
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
pseudonorm. For this purpose, we suppose given a (source) norm on
. 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
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
pseudonorm, in terms of the coordinate-k norms. As an application, we provide a new family of lower bounds for the
pseudonorm, as a fraction between two norms, the denominator being any norm.
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 the complementary subset of K in
:
and
.
2 The notation is a shorthand for
.
3 The notation is a shorthand for
.
4 In what follows, by ‘or’ we mean the so-called exclusive or (exclusive disjunction). Thus, every ‘or’ should be understood as ‘or and’
5 See footnote 4.
6 In (Equation34g(34g)
(34g) ), the sum starts from
, whereas in (Equation34h
(34h)
(34h) ) and in (Equation34i
(34i)
(34i) ), the sum starts from
7 In convex analysis, one does not use the notation , but simply the notation
, as it is often the case that