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

Abstract

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does ${\ell }_1$-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 ${\ell }_1$-norm solutions to linear systems. From this condition, we deduce that a sparsest solution coincides with the unique least ${\ell }_1$-norm solution to a linear system if and only if the so-called \emph{range space property} (RSP) holds at this solution. This yields a broad understanding of the relationship between ${\ell }_0$- and ${\ell }_1$-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 ${\ell }_1$-minimization by a deterministic analysis, and if a linear system has multiple sparsest solutions, when does ${\ell }_1$-minimization guarantee to find one of them? Moreover, new matrix properties (such as the \emph{RSP of order $K$} and the \emph{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.

Cited by in corpus (9)

• The Sparsest Solutions to $Z$-Tensor Complementarity Problems
• Exact Recovery for Sparse Signal via Weighted $l_1$ Minimization
• A Theoretical Analysis of Sparse Recovery Stability of Dantzig Selector and LASSO
• Nonuniqueness of Solutions of a Class of ${\ell }_0$-minimization Problems
• A Lagrangian Dual Based Approach to Sparse Linear Programming
• 1-Bit Compressive Sensing: Reformulation and RRSP-Based Sign Recovery Theory
• New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems
• Stability Analysis for a Class of Sparse Optimization Problems
• A Majorization Penalty Method for SVM with Sparse Constraint