  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
nonconvex 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.
