Efficient and guaranteed rank minimization by atomic decomposition

Kiryung Lee, Yoram Bresler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recht, Fazel, and Parrilo provided an analogy between rank minimization and lo-norm minimization. Subject to the rank-restricted isometry property, nuclear norm minimization is a guaranteed algorithm for rank minimization. The resulting semidefinite formulation is a convex problem but in practice the algorithms for it do not scale well to large instances. Instead, we explore missing terms in the analogy and propose a new algorithm which is computationally efficient and also has a performance guarantee. The algorithm is based on the atomic decomposition of the matrix variable and extends the idea in the CoSaMP algorithm for lo-norm minimization. Combined with the recent fast low rank approximation of matrices based on randomization, the proposed algorithm can efficiently handle large scale rank minimization problems.

Original languageEnglish (US)
Title of host publication2009 IEEE International Symposium on Information Theory, ISIT 2009
Pages314-318
Number of pages5
DOIs
StatePublished - Nov 19 2009
Event2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of
Duration: Jun 28 2009Jul 3 2009

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8102

Other

Other2009 IEEE International Symposium on Information Theory, ISIT 2009
CountryKorea, Republic of
CitySeoul
Period6/28/097/3/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Efficient and guaranteed rank minimization by atomic decomposition'. Together they form a unique fingerprint.

  • Cite this

    Lee, K., & Bresler, Y. (2009). Efficient and guaranteed rank minimization by atomic decomposition. In 2009 IEEE International Symposium on Information Theory, ISIT 2009 (pp. 314-318). [5205530] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2009.5205530