Representation recovery via L1-norm minimization with corrupted data

Woon Huei Chai, Shen Shyang Ho, Hiok Chai Quek

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper studies the recovery probability of a state-of-the-art sparse recovery method, the optimization problem of YALL1, which has been rigorously used in face recognition, dense error correction, anomaly detection, etc. This work generalizes a theoretical work which is based on a special case of the optimization problem of YALL1. Furthermore, the new results cover more practical cases which do not fulfill the bouquet model proposed in the early work. The results also show that not only the special case but also some other cases of the optimization problem of YALL1; which fulfill certain conditions; can also recover any sufficiently sparse coefficient vector x when the fraction of the support of the error e is bounded away from 1 and the support of x is a very small fraction of its dimension m as m becomes large. The trade-off parameter λ in the optimization problem of YALL1 allows the recovery probability to be optimally tuned than the special case. Experimental results also show that the optimization problem of YALL1 (the Eq. (7)) with primal augmented Lagrangian optimization technique outperforms the state-of-the-art sparse recovery methods using their corresponding optimization techniques in term of the speed.

Original languageEnglish (US)
Pages (from-to)395-426
Number of pages32
JournalInformation Sciences
StatePublished - May 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems and Management
  • Artificial Intelligence
  • Theoretical Computer Science
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'Representation recovery via L1-norm minimization with corrupted data'. Together they form a unique fingerprint.

Cite this