IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v44y2019i1p173-195.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Yun-Bin Zhao & Houyuan Jiang & Zhi-Quan Luo, 2019. "Weak Stability of ℓ 1 -Minimization Methods in Sparse Data Reconstruction," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 173-195, February.
    • Handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:173-195
    DOI: 10.1287/moor.2017.0919
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0919
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2017.0919?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hui Zhang & Wotao Yin & Lizhi Cheng, 2015. "Necessary and Sufficient Conditions of Solution Uniqueness in 1-Norm Minimization," Journal of Optimization Theory and Applications, Springer, vol. 164(1), pages 109-122, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tim Hoheisel & Elliot Paquette, 2023. "Uniqueness in Nuclear Norm Minimization: Flatness of the Nuclear Norm Sphere and Simultaneous Polarization," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 252-276, April.
    2. Patrick R. Johnstone & Pierre Moulin, 2017. "Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions," Computational Optimization and Applications, Springer, vol. 67(2), pages 259-292, June.
    3. Fan Wu & Wei Bian, 2020. "Accelerated iterative hard thresholding algorithm for $$l_0$$l0 regularized regression problem," Journal of Global Optimization, Springer, vol. 76(4), pages 819-840, April.
    4. Jean Charles Gilbert, 2017. "On the Solution Uniqueness Characterization in the L1 Norm and Polyhedral Gauge Recovery," Journal of Optimization Theory and Applications, Springer, vol. 172(1), pages 70-101, January.
    5. James Folberth & Stephen Becker, 2020. "Safe Feature Elimination for Non-negativity Constrained Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 931-952, March.
    6. Yunier Bello-Cruz & Guoyin Li & Tran Thai An Nghia, 2022. "Quadratic Growth Conditions and Uniqueness of Optimal Solution to Lasso," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 167-190, July.
    7. Abdessamad Barbara & Abderrahim Jourani & Samuel Vaiter, 2019. "Maximal Solutions of Sparse Analysis Regularization," Journal of Optimization Theory and Applications, Springer, vol. 180(2), pages 374-396, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:173-195. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.