论文标题
稀疏恢复的关键点理论
Critical point theory for sparse recovery
论文作者
论文摘要
我们研究了压缩感测的稀疏恢复问题。这是为了最大程度地减少稀疏向量的传感误差，其中最多是$ s $ non-Zero条目。我们开发了所谓的临界点理论，以稀疏恢复。这是通过引入非等级的M型点来完成的，该点充分描述了该非convex优化问题的全局结构。我们表明，所有M平稳点都是非排定的。特别是，在通用稀疏恢复问题的所有局部最小化器中，稀疏性约束都处于活动状态。此外，显示了强稳定性和非平稳级的等效性。我们声称，鞍点的出现 - 这些是恰好$ s-1 $ non-Zero条目的M平稳点 - 不能忽略。为此，我们得出了所谓的摩尔斯关系，该关系在局部最小化器的数量方面给出了鞍点数量的下限。通过解决稀疏恢复到全球最优性的问题，可以将相对涉及的鞍点结构视为众所周知的难度的来源。
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.
