Sparse Recovery beyond Compressed Sensing: Separable Nonlinear Inverse Problems

Brett Bernstein, Sheng Liu, Chrysa Papadaniil, Carlos Fernandez-Granda

Research output: Contribution to journalArticlepeer-review


Extracting information from nonlinear measurements is a fundamental challenge in data analysis. In this work, we consider separable inverse problems, where the data are modeled as a linear combination of functions that depend nonlinearly on certain parameters of interest. These parameters may represent neuronal activity in a human brain, frequencies of electromagnetic waves, fluorescent probes in a cell, or magnetic relaxation times of biological tissues. Separable nonlinear inverse problems can be reformulated as underdetermined sparse-recovery problems, and solved using convex programming. This approach has had empirical success in a variety of domains, from geophysics to medical imaging, but lacks a theoretical justification. In particular, compressed-sensing theory does not apply, because the measurement operators are deterministic and violate incoherence conditions such as the restricted-isometry property. Our main contribution is a theory for sparse recovery adapted to deterministic settings. We show that convex programming succeeds in recovering the parameters of interest, as long as their values are sufficiently distinct with respect to the correlation structure of the measurement operator. The theoretical results are illustrated through numerical experiments for two applications: heat-source localization and estimation of brain activity from electroencephalography data.

Original languageEnglish (US)
Article number9052719
Pages (from-to)5904-5926
Number of pages23
JournalIEEE Transactions on Information Theory
Issue number9
StatePublished - Sep 2020


  • Sparse recovery
  • convex programming
  • correlated measurements
  • dual certificates
  • incoherence
  • nonlinear inverse problems
  • source localization

ASJC Scopus subject areas

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


Dive into the research topics of 'Sparse Recovery beyond Compressed Sensing: Separable Nonlinear Inverse Problems'. Together they form a unique fingerprint.

Cite this