Weak Stability of ℓ1-minimization Methods in Sparse Data Reconstruction

Yun-Bin Zhao, Houyuan Jiang (Contributor), Zhi-Quan Luo (Contributor)

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
197 Downloads (Pure)


As one of the most plausible convex optimization methods for sparse data reconstruction, ℓ1-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, we propose a unified means to develop the so-called weak stability theory for ℓ1-minimization methods under the condition called weak range space property of a transposed design matrix, which turns out to be a necessary and sufficient condition for the standard ℓ1-minimization method to be weakly stable in sparse data reconstruction. The reconstruction error bounds established in this paper are measured by the so-called Robinson's constant.

We also provide a unified weak stability result for standard ℓ1-minimization under several existing compressed-sensing matrix properties. In particular, the weak stability of ℓ1-minimization under the constant-free range space property of order k of the transposed design matrix is established for the first time in this paper. Different from the existing analysis, we utilize the classic Hoffman's Lemma concerning the error bound of linear systems as well as the Dudley's theorem concerning the polytope approximation of the unit ℓ2-ball to show that ℓ1-minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements.
Original languageEnglish
Pages (from-to)153-179
Number of pages26
JournalMathematics of Operations Research
Issue number1
Publication statusPublished - 14 Sept 2018


Dive into the research topics of 'Weak Stability of ℓ1-minimization Methods in Sparse Data Reconstruction'. Together they form a unique fingerprint.

Cite this