Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
Authors:
- 16 July 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (18) , 4868-4881
Abstract
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 nonconvex 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.Keywords
All Related Versions
Funding Information
- DFG (SFB 755-C2)
- DFG (SFB 755-C2, SFB 755-A4)
- DFG (GRK1023)
This publication has 35 references indexed in Scilit:
- The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed SensingIEEE Transactions on Information Theory, 2013
- Prox-Regularity of Rank Constraint Sets and Implications for AlgorithmsJournal of Mathematical Imaging and Vision, 2012
- A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems2011
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert SpaceSIAM Journal on Optimization, 2008
- Metric Inequality, Subdifferential Calculus and ApplicationsSet-Valued Analysis, 2001
- Variational Analysis1998
- Decomposition through formalization in a product spaceMathematical Programming, 1984
- Splitting Algorithms for the Sum of Two Nonlinear OperatorsSIAM Journal on Numerical Analysis, 1979
- Eclatement de contraintes en parallele pour la minimisation d'une forme quadratiqueLecture Notes in Computer Science, 1976