Sparse Recovery Beyond Compressed Sensing: Separable Nonlinear Inverse Problems

Brett Bernstein, Sheng Liu, Chrysa Papadaniil, Carlos Fernandez-GrandaIEEE Trans. Information Theory 2019 · DOI · OpenReview

Abstract

This paper establishes a new theoretical foundation for solving Separable Nonlinear (SNL) inverse problems—where data is a linear combination of nonlinear functions—using convex optimization. While standard Compressed Sensing (CS) relies on randomness and "incoherence," this work proves that exact recovery is possible in deterministic, highly correlated settings. The core finding is that recovery is guaranteed if the underlying parameters are sufficiently separated relative to the "correlation decay" of the measurement operator.

Introduction

Many scientific and engineering challenges involve extracting discrete parameters from nonlinear measurements. These are often categorized as Separable Nonlinear (SNL) problems, where a signal is composed of a sum of components, each defined by a linear weight (amplitude) and a nonlinear parameter (such as location or frequency). Common examples include deconvolution in seismology, super-resolution in imaging, and source localization in physics.

Examples of Separable Nonlinear (SNL) problems, including deconvolution, super-resolution, and heat-source localization.

Traditionally, these problems are approached via nonlinear least-squares, which are notoriously difficult to optimize due to non-convexity and local minima. A more robust alternative is "linearizing" the problem by treating it as a sparse recovery task on a continuous domain, solved via Total-Variation (TV) norm minimization.

Theoretical Framework: Embracing Correlation

Standard Compressed Sensing theory often fails to explain the success of TV-norm minimization in SNL problems because it requires "incoherent" measurement operators, typically achieved through randomness. In contrast, SNL measurements are deterministic and highly correlated—small changes in a parameter lead to small changes in the measurement signature.

The authors propose a framework based on the correlation structure of the measurement operator. They define three critical conditions on the correlation function:

  1. Near Condition: Local concavity and smoothness at the peak.
  2. Intermediate Condition: Bounding the correlation away from the peak.
  3. Decay Condition: Predictable drop-off (e.g., exponential) as parameters separate.

By constructing a novel "correlation-based dual certificate," the authors prove that exact recovery is guaranteed if the true parameters meet a minimum separation distance $\Delta$. This distance is derived directly from the constants governing the correlation decay and its derivatives, rather than relying on stochastic properties.

Applications and Validation

The theory was validated using simulations across diverse physical domains, most notably in EEG brain activity localization and heat-source detection.

EEG Brain Activity

Using the ICBM152 template to model complex head geometry, the researchers simulated brain activity from 256 sensors. The method successfully recovered three distinct sources across the occipital, temporal, and frontal lobes. This demonstrates that the theory holds even in the presence of the complex, non-uniform geometry of the human cortex.

Parameter space and spatial maps for EEG brain activity localization using the ICBM152 template.

Heat-Source Localization

In tests involving non-uniform thermal conductivity, the authors found that "correlation-aware" separation was a significantly more accurate predictor of recovery success than simple physical distance. This highlights the importance of accounting for local resolution variations in real-world physics.

Conclusion and Future Work

This work shifts the paradigm of sparse recovery from a reliance on randomness to a reliance on parameter separation and correlation decay. While solving these problems on high-dimensional grids remains computationally intensive, the framework provides a rigorous foundation for applying convex optimization to complex nonlinear inverse problems. Future research directions include improving computational efficiency through machine learning and refining the stability analysis for noisy environments.

Summary updated

Abstract

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.
BibTeX
@article{bernstein2019sparse,
  author = {Brett Bernstein and Sheng Liu and Chrysa Papadaniil and Carlos Fernandez-Granda},
  title = {{Sparse Recovery Beyond Compressed Sensing: Separable Nonlinear Inverse Problems}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  doi = {10.1109/tit.2020.2985015},
}
Figure