Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility

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. In a recent paper Bauschke, Luke, Phan and Wang (2014) showed 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.

29 pages, 2 figures, 37 references. Much expanded version from last submission. Title changed to reflect new developments

References in corpus (1)

• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle

Cited by in corpus (21)

• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results
• Quantitative convergence analysis of iterated expansive, set-valued mappings
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Circumcentering the Douglas--Rachford method
• Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem
• Dynamic string-averaging CQ-methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning
• On the linear convergence of the circumcentered-reflection method
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• Union Averaged Operators with Applications to Proximal Algorithms for Min-Convex Functions
• Regularity Properties of Non-Negative Sparsity Sets
• The Block-wise Circumcentered-Reflection Method
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• Local Convergence of Proximal Splitting Methods for Rank Constrained Problems
• Alternating conditional gradient method for convex feasibility problems
• A minimalist approach to 3D photoemission orbital tomography: algorithms and data requirements
• A Douglas-Rachford construction of non-separable continuous compactly supported multidimensional wavelets
• Phase retrieval with sparse phase constraint
• A parameterized Douglas-Rachford Splitting algorithm for nonconvex optimization
• Method of Alternating Projection for the Absolute Value Equation
• Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting