Critical point theory for sparse recovery. (1st February 2023)

• Record Type: Journal Article
• Authors: Lämmel, S.; Shikhman, V.
• Is Part Of: Optimization. Volume 72:Number 2(2023)
• Page Start: 521
• Page End: 549
• Publication Date: 2023-02-01
• Subjects: Sparse recovery -- compressed sensing -- critical point theory -- nondegenerate M-stationarity -- strong stability; 90C26 -- 90C46; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2021.1981317
• Languages: English
• ISSNs: 0233-1934

Abstract

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.