Weak stability of l_1-minimization methods in sparse data reconstruction
View / Open Files
Authors
Zhao, YB
Jiang, H
Luo, ZQ
Publication Date
2019-02Journal Title
Mathematics of Operations Research
ISSN
1526-5471
Publisher
Institute for Operations Research and the Management Sciences
Volume
44
Issue
1
Pages
173-195
Type
Article
Metadata
Show full item recordCitation
Zhao, Y., Jiang, H., & Luo, Z. (2019). Weak stability of l_1-minimization methods in sparse data reconstruction. Mathematics of Operations Research, 44 (1), 173-195. https://doi.org/10.1287/moor.2017.0919
Abstract
As one of the most plausible convex optimization methods for sparse data reconstruction, l_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 l_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 l_1-minimization under several existing compressed sensing matrix properties. In particular, the weak stability of l_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 Ho˙man’s lemma concerning the error bound of linear systems as well as Dudley’s theorem concerning the polytope approximation of the unit l_2-ball to show that l_1-minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements.
Keywords
sparsity optimization, l(1)-minimization, convex optimization, linear program, weak stability, weak range space property
Identifiers
External DOI: https://doi.org/10.1287/moor.2017.0919
This record's URL: https://www.repository.cam.ac.uk/handle/1810/283592
Rights
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk