| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
