Restricted normal cones and sparsity optimization with affine constraints

The problem of finding a vector with the fewest nonzero elements that satisfies an underdeter-mined system of linear equations is an NP-complete problem that is typically solved numeri-cally via convex heuristics or nicely-behaved nonconvex 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 recon-ciles 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 superreg-ularity, which is inherently satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorith