Introduction
In many signal processing and machine learning tasks, the goal is to recover an unknown signal $\mathbf{x} \in \mathbb{R}^n$ from a set of nonlinear measurements $\mathbf{y} = f(\mathbf{Ax})$. Here, $\mathbf{A}$ is a known linear sensing matrix, and $f$ is a component-wise nonlinear transformation. By properly specifying $f$, this Generalized Linear Model (GLM) encompasses a wide array of applications, including compressed sensing and phase retrieval.
While much of the existing theory assumes the sensing matrix $\mathbf{A}$ is populated with i.i.d. Gaussian entries (which yields a relatively "flat" eigenvalue spectrum), real-world applications often allow engineers to design the sensing matrix. This raises a fundamental question: How does the spectrum of $\mathbf{A}$ impact the difficulty of recovering $\mathbf{x}$? Specifically, does a "spiky" spectrum—where a few eigenvalues are significantly larger than the rest—make recovery easier or harder?
This paper investigates how the "spikiness" of a sensing matrix's spectrum affects signal recovery in nonlinear inverse problems. The authors demonstrate that the impact of the spectrum is highly dependent on the chosen nonlinearity $f$. While a spiky spectrum aids in tasks like phase retrieval, it hinders performance in others like 1-bit compressed sensing. This work provides a theoretical framework for designing optimal sensing systems tailored to specific nonlinearities.
Methodology
To understand the impact of the sensing matrix spectrum, the authors analyze the performance of the Expectation Propagation (EP) algorithm, a powerful iterative method for solving Bayesian inverse problems.
The theoretical analysis relies on several key components:
- State Evolution (SE): The authors employ a State Evolution framework to precisely track the algorithm's mean squared error (MSE) at each iteration in the high-dimensional limit.
- Lorenz Partial Order: To formally define and compare the "spikiness" of different matrices, the authors borrow the Lorenz order from economics (traditionally used to measure wealth inequality). This provides a rigorous mathematical tool to evaluate how concentrated the eigenvalues of a matrix are.
- Information-Theoretic Limits: They derive lower bounds for the number of measurements required for perfect recovery, leveraging the Rényi information dimension of the nonlinear transformation.
The theoretical predictions are validated using synthetic signals drawn from generic continuous distributions and sensing matrices with geometrically distributed eigenvalues (controlled by a parameter $\beta$ to tune spikiness). Numerical simulations of the GLM-EP algorithm confirm that the State Evolution theory accurately predicts practical performance.
Key Insights: The Monotonicity Rule
The most significant takeaway from the paper is that spikiness is a double-edged sword. The effect of the eigenvalue distribution depends entirely on the nature of the nonlinearity $f$.
To formalize this, the authors define a specific function, $G(v_r)$, which is derived directly from the nonlinearity $f$. The behavior of $G(v_r)$ dictates how the spectrum affects recovery:
- If $G(v_r)$ is an increasing function, a spikier spectrum improves recovery. This is the case for Phase Retrieval ($f(z) = |z|$).
- If $G(v_r)$ is a decreasing function, a flatter spectrum is optimal. This applies to 1-bit Compressed Sensing ($f(z) = \text{sign}(z)$).
Furthermore, the paper shows that if the spectrum is sufficiently spiky (for nonlinearities where spikiness is beneficial), the EP algorithm can achieve the information-theoretic lower bound for the minimum number of measurements required for perfect recovery. This implies that computationally efficient algorithms can be paired with optimally designed sensing matrices to reach theoretical performance limits.
Fundamental Limits and Stability
The authors establish several formal theorems detailing these limits:
- Information Dimension Limits (Theorems 1 & 2): The fundamental limit for recovery is bounded by the information dimension $d(f(Z))$. For instance, in 1-bit compressed sensing, perfect recovery is impossible in the high-dimensional limit because the information dimension of the output is zero.
- Impact of Spikiness (Theorem 3): For any nonlinearity $f$, shifting to a more spiky spectrum (in the Lorenz sense) consistently reduces the minimum number of measurements needed for perfect recovery, provided $G(v_r)$ is increasing.
- Robustness to Noise: The recovery guarantees are shown to be stable even in the presence of noise (in the high SNR regime), as long as the number of measurements exceeds the derived theoretical threshold.
Limitations and Future Directions
While providing a robust framework, the current analysis assumes the signal $\mathbf{x}$ is drawn from a generic continuous distribution and does not explicitly exploit structural priors like sparsity. Given that sparsity is a cornerstone of many compressed sensing applications, extending this framework to structured signals is a critical next step.
Additionally, the noise analysis is primarily focused on the high signal-to-noise ratio (SNR) regime, leaving the low SNR behavior for future investigation. Finally, the theory assumes the sensing matrix has Haar-distributed singular vectors; real-world matrices with highly structured singular vectors may exhibit different behaviors that warrant further study.
Summary updated