Relation between exact and robust recovery for F-minimization: A topological viewpoint

Jingbo Liu, Jian Jin, Yuantao Gu

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


Recent work in compressed sensing has shown the possibility reducing the number of measurements via non-convex optimization methods. Most of these methods can be studied in the general framework called 'F-minimization', for which the relation between the noiseless exact recovery condition (ERC) and noisy robust recovery condition (RRC) was not fully understood. In this paper, we associate each set of nulls spaces of the measurement matrices satisfying ERC/RRC as a subset of a Grassmannian, and show that the RRC set is exactly the interior of the ERC set. Then, a previous result of the equivalence of ERC and RRC for lp-minimization follows easily as a special case. We also show under some mild but necessary additional assumption that the ERC and RRC sets differ by a set of measure zero.

Original languageEnglish (US)
Title of host publication2013 IEEE International Symposium on Information Theory, ISIT 2013
Number of pages5
StatePublished - 2013
Externally publishedYes
Event2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey
Duration: Jul 7 2013Jul 12 2013

Publication series

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


Other2013 IEEE International Symposium on Information Theory, ISIT 2013

ASJC Scopus subject areas

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

Cite this