Robustness of Sparse Recovery via F-Minimization: A Topological Viewpoint

Jingbo Liu, Jian Jin, Yuantao Gu

Research output: Contribution to journalArticlepeer-review


A recent trend in compressed sensing is to consider nonconvex optimization techniques for sparse recovery. The important case of F-minimization has become of particular interest, for which the exact reconstruction condition (ERC) in the noiseless setting can be precisely characterized by the null space property (NSP). However, little work has been done concerning its robust reconstruction condition (RRC) in the noisy setting. We look at the null space of the measurement matrix as a point on the Grassmann manifold, and then study the relation between the ERC and RRC sets, denoted as ΩJ and ΩrJ, respectively. It is shown that ΩrJ is the interior of ΩJ, from which a previous result of the equivalence of ERC and RRC for lp-minimization follows easily as a special case. Moreover, when F is nondecreasing, it is shown that ΩJ \ int(ΩJ ) is a set of measure zero and of the first category. As a consequence, the probabilities of ERC and RRC are the same if the measurement matrix A is randomly generated according to a continuous distribution. Quantitatively, if the null space N(A) lies in the d-interior of ΩJ , then RRC will be satisfied with the robustness constant C = 2 + 2d/dσmin(Aτ); and conversely, if RRC holds with C = 2 - 2d/dσmax(Aτ), then N(A) must lie in d-interior of ΩJ . We also present several rules for comparing the performances of different cost functions. Finally, these results are capitalized to derive achievable tradeoffs between the measurement rate and robustness with the aid of Gordon's escape through the mesh theorem or a connection between NSP and the restricted eigenvalue condition.

Original languageEnglish (US)
Article number7114292
Pages (from-to)3996-4014
Number of pages19
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 1 2015
Externally publishedYes


  • compressed sensing
  • minimization methods
  • null space
  • Reconstruction algorithms
  • robustness

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Robustness of Sparse Recovery via F-Minimization: A Topological Viewpoint'. Together they form a unique fingerprint.

Cite this