Dynamical functional theory for compressed sensing

Burak Çakmak, Manfred Opper, Ole Winther, Bernard H. Fleury

Introduction

Compressed sensing aims to recover a sparse signal $x \in \mathbb{R}^N$ from a reduced set of noisy linear measurements $y = Ax + n$, where $A \in \mathbb{R}^{M \times N}$ is the measurement matrix. Among the various recovery algorithms, Approximate Message Passing (AMP) has gained prominence due to its low computational complexity and the existence of "state evolution"—a rigorous framework that tracks the algorithm's performance through simple scalar iterations. However, the standard AMP framework relies heavily on the assumption that the matrix $A$ consists of independent and identically distributed (iid) Gaussian entries. In practice, structured matrices (e.g., partial Fourier or row-orthogonal matrices) are preferred for their computational efficiency, yet they often cause standard AMP to diverge.

This paper addresses this limitation by leveraging Dynamical Functional Theory (DFT) from statistical physics to extend the AMP framework to a broader class of rotationally invariant random matrix ensembles.

Theoretical Framework: DFT and Free Probability

The authors bridge the gap between signal processing and statistical mechanics by employing two sophisticated mathematical tools:

  1. Dynamical Functional Theory (DFT): Originally developed to study the dynamics of spin glasses, DFT provides a method to describe the statistical trajectory of high-dimensional iterative processes. Rather than tracking every component of the system, DFT focuses on the "marginal statistics" of a single typical component over time. This allows for a macroscopic description of the algorithm's behavior.
  2. Free Probability and R-Transforms: To characterize the eigenvalue distributions of general matrix ensembles, the authors utilize the R-transform. This tool is essential for calculating the memory terms required to stabilize the algorithm when the iid assumption is violated.

The Single-Step Memory Design

The primary challenge in generalizing AMP is the "Onsager correction" term, which accounts for the correlation between the current estimate and previous iterations. For non-iid matrices, a simple one-step correction is insufficient.

The authors propose a "Single-Step Memory" design. By carefully structuring the algorithm's internal state (the "field"), they ensure that it remains Gaussian in the large-system limit ($N, M \to \infty$). This preservation of Gaussianity is crucial because it allows the algorithm's performance to be predicted by a generalized version of state evolution. This design ensures that the "decoupling principle"—where components of the estimate behave as if they were passed through a scalar Gaussian channel—holds throughout the entire dynamical trajectory, not just at the fixed point.

Key Results and Validation

The paper validates the proposed framework through both theoretical derivation and application to specific matrix ensembles:

  • Generalized State Evolution: The authors derive explicit formulas for the variance of the estimates over time. These formulas provide a deterministic way to predict the Mean Squared Error (MSE) of the algorithm at each iteration for any invariant matrix ensemble.
  • Unification with Standard AMP: The theory is shown to be backward-compatible. When the measurement matrix $A$ is iid Gaussian, the complex DFT-based equations simplify exactly to the standard AMP state evolution.
  • Stability for Row-Orthogonal Matrices: For random row-orthogonal matrices—a case where standard AMP typically fails—the authors derive a compact analytic form for the variance. This proves that the single-step memory design successfully stabilizes the recovery process for structured matrices.
  • Consistency with Replica Symmetry: The fixed points of the proposed dynamical algorithm are shown to be consistent with the "replica ansatz." This is a significant finding, as it aligns the algorithmic performance with the information-theoretic limits predicted by non-rigorous methods in statistical physics.

Limitations and Future Outlook

While the DFT approach offers a powerful generalization of AMP, several areas for future research remain:

  • Dynamical Instability: The algorithm can exhibit sensitivity to initialization, particularly in low-noise regimes. Understanding the conditions for dynamical stability is essential for practical deployment.
  • Alternative Designs: This work focuses on "single-step memory" designs. The authors suggest that "single-step response" designs might offer different trade-offs between computational speed and convergence robustness.
  • Relationship to VAMP: The results are closely related to Vector AMP (VAMP) and other expectation-propagation-based methods. Establishing a rigorous mathematical link between the DFT approach and VAMP remains a key objective for the field.

Conclusion

By applying Dynamical Functional Theory to compressed sensing, this paper provides a robust theoretical foundation for designing iterative recovery algorithms that work with a wide range of measurement matrices. This extension moves AMP beyond the restrictive iid Gaussian assumption, paving the way for more versatile and theoretically grounded signal processing tools.

Summary updated

Abstract

We introduce a theoretical approach for designing generalizations of the approximate message passing (AMP) algorithm for compressed sensing which are valid for large observation matrices that are drawn from an invariant random matrix ensemble. By design, the fixed points of the algorithm obey the Thouless-Anderson-Palmer (TAP) equations corresponding to the ensemble. Using a dynamical functional approach we are able to derive an effective stochastic process for the marginal statistics of a single component of the dynamics. This allows us to design memory terms in the algorithm in such a way that the resulting fields become Gaussian random variables allowing for an explicit analysis. The asymptotic statistics of these fields are consistent with the replica ansatz of the compressed sensing problem.
BibTeX
@inproceedings{cakmak2017dynamical,
  author = {Burak Çakmak and Manfred Opper and Ole Winther and Bernard H. Fleury},
  title = {{Dynamical functional theory for compressed sensing}},
  booktitle = {ISIT},
  year = {2017},
  url = {https://openreview.net/forum?id=4wsl5z4pRd-},
}
Figure