标题： 受限法锥与带有线性约束的稀疏优化 显示英文标题

标题： Restricted normal cones and sparsity optimization with affine constraints

摘要： 寻找满足欠定线性方程组的非零元素最少的向量的问题是一个NP难问题，通常通过凸启发式方法或行为良好的非凸松弛进行数值求解。 在本文中，我们考虑使用交替投影的基本方法（MAP）来解决稀疏优化问题，而无需使用凸启发式方法。 在一篇并行论文中，我们最近引入了受限法锥，它推广了经典的Mordukhovich法锥，并弥合了MAP算法局部线性收敛的充分条件理论中的一些基本缺口。 我们结合受限法锥和超正则性的概念，该概念自然满足仿射稀疏优化问题，以获得将MAP算法应用于具有仿射约束的稀疏优化时的局部线性收敛结果，并给出收敛半径的估计。 显示英文摘要

摘要： The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved non convex relaxations. In this paper we consider the elementary method of alternating projections (MAP) for solving the sparsity optimization problem without employing convex heuristics. In a parallel paper we recently introduced the restricted normal cone which generalizes the classical Mordukhovich normal cone and reconciles some fundamental gaps in the theory of sufficient conditions for local linear convergence of the MAP algorithm. We use the restricted normal cone together with the notion of superregularity, which is naturally satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorithm applied to sparsity optimization with an affine constraint.