Projection methods for sparse affine feasibility: results and counterexamples

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 nu-merically 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. We show that the fundamental method of alternating projections must converge locally linearly to a solution to the sparse feasibility problem with an affine constraint. Our analysis provides the radius of convergence and rate based on the angle of intersection of the sparsity set and the affine constraint. Under stronger assumptions on the intersection we also show local linear con-vergence, with radius of convergence, of the Douglas-Rachford algorithm. The stronger assumptions are in fact necessary for convergence of the Douglas-Rachford for affine feasibility. We show that these assumptions are not satisfied for most sparsity problems of interest, indicating that methods related to the Douglas-Rachford Algorithm, such as Alternating Directions Method of Multipliers, are not a promising algorithmic approach asymptotically for sparsity optimization