Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
复制标题
DOI：
10.1109/tsp.2014.2339801
复制
发表时间：
2014-09-15
影响因子：
5.4
通讯作者：
Neumann, Patrick
中科院分区：
文献类型：
--
作者：
Hesse, Robert;Luke, D. Russell;Neumann, Patrick
寻找满足欠定线性方程组的具有最少非零元素的向量的问题是一个np完全问题，通常通过凸启发式或表现良好的非凸松弛在数值上解决。在这项工作中，我们考虑基于投影的初等方法来解决稀疏可行性问题，而不使用凸启发式。最近的研究表明，在局部情况下，交替投影的基本方法必须线性收敛于具有仿射约束的稀疏可行性问题的解。在本文中，我们应用不同的分析工具，使我们能够在熟悉的约束条件下显示交替投影的全局线性收敛性。这些分析工具也可以应用于其他算法。杰出的Douglas-Rachford算法证明了这一点，我们建立了该方法应用于稀疏仿射可行性问题的局部线性收敛性。
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 work we consider elementary methods based on projections for solving a sparse feasibility problem without employing convex heuristics. It has been shown recently that, locally, the fundamental method of alternating projections must converge linearly to a solution to the sparse feasibility problem with an affine constraint. In this paper we apply different analytical tools that allow us to show global linear convergence of alternating projections under familiar constraint qualifications. These analytical tools can also be applied to other algorithms. This is demonstrated with the prominent Douglas-Rachford algorithm where we establish local linear convergence of this method applied to the sparse affine feasibility problem.