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.