RSP-Based Analysis for Sparsest and Least $\ell _1$ -Norm Solutions to Underdetermined Linear Systems

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does ℓ₁-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary and sufficient condition for the uniqueness of least ℓ₁-norm solutions to linear systems. From this condition, we deduce that a sparsest solution coincides with the unique least ℓ₁-norm solution to a linear system if and only if the so-called range space property (RSP) holds at this solution. This yields a broad understanding of the relationship between ℓ₀- and ℓ₁-minimization problems. Our analysis indicates that the RSP truly lies at the heart of the relationship between these two problems. Through RSP-based analysis, several important questions in this field can be largely addressed. For instance, how to efficiently interpret the gap between the current theory and the actual numerical performance of ℓ₁-minimization by a deterministic analysis, and if a linear system has multiple sparsest solutions, when does ℓ₁-minimization guarantee to find one of them? Moreover, new matrix properties (such as the RSP of order K and the Weak-RSP of order K) are introduced in this paper, and a new theory for sparse signal recovery based on the RSP of order K is established.