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

Yun-Bin Zhao (), Houyuan Jiang () and Zhi-Quan Luo ()
Additional contact information
Yun-Bin Zhao: School of Mathematics, University of Birmingham, Edgbaston, Birmingham, West Midlands B15 2TT, United Kingdom
Houyuan Jiang: Judge Business School, University of Cambridge, Cambridge CB2 1AG, United Kingdom
Zhi-Quan Luo: Shenzhen Research Institute of Big Data, Chinese University of Hong Kong, 51872 Shenzhen, Guangdong, China

Mathematics of Operations Research, 2019, vol. 44, issue 1, 173-195

Abstract: 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 the restricted isometry property, null space property, 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 the 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 this method under the constant-free range space property of the transposed design matrix is established, to our knowledge, 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 Dudley’s theorem concerning the polytope approximation of the unit ball to show that ℓ 1 -minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements.

Keywords: sparsity optimization; ℓ 1 -minimization; convex optimization; linear program; weak stability; weak range space property (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0919 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:1:p:173-195

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().