Critical point theory for sparse recovery

Abstract

We study the problem of sparse recovery in the context of compressed sensing. This is to minimize the sensing error of linear measurements by sparse vectors with at most s non-zero entries. We develop the so-called critical point theory for sparse recovery. This is done by introducing nondegenerate M-stationary points which adequately describe the global structure of this non-convex optimization problem. We show that all M-stationary points are generically nondegenerate. In particular, the sparsity constraint is active at all local minimizers of a generic sparse recovery problem. Additionally, the equivalence of strong stability and nondegeneracy for M-stationary points is shown. We claim that the appearance of saddle points – these are M-stationary points with exactly s−1 non-zero entries – cannot be neglected. For this purpose, we derive a so-called Morse relation, which gives a lower bound on the number of saddle points in terms of the number of local minimizers. The relatively involved structure of saddle points can be seen as a source of well-known difficulty by solving the problem of sparse recovery to global optimality.

Keywords:

• Sparse recovery
• compressed sensing
• critical point theory
• nondegenerate M-stationarity
• strong stability

MSC:

• 90C26
• 90C46

Acknowledgments

The authors would like to thank Hubertus Th. Jongen for fruitful discussions. Our thanks go also to the anonymous referee who not only suggested a simpler proof of Theorem 2.1, but also provided the statement of Lemma 4.1 being of independent interest. The other anonymous referee kindly encouraged us to make the proof of Lemma 5.2 more algebraically coherent.

Disclosure statement

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