Abstract
Generalized Linear Models (GLMs) are fundamental to signal recovery from nonlinear measurements. While standard analysis often assumes i.i.d. Gaussian sensing matrices, real-world applications frequently involve structured matrices. This work explores how the eigenvalue distribution (spectrum) of the sensing matrix impacts the Expectation Propagation (EP) algorithm. Using the Lorenz partial order to quantify spectral "spikiness," we demonstrate that spiky spectra can significantly lower the sampling threshold for perfect reconstruction, even reaching information-theoretic limits in phase retrieval. However, a trade-off exists: spikiness can hinder Mean Squared Error (MSE) performance in specific tasks like 1-bit compressed sensing. These findings provide a unified framework for designing optimal sensing matrices in nonlinear inverse problems.
Introduction
Signal recovery from nonlinear observations $y = f(Ax)$ is a cornerstone of modern signal processing. While the i.i.d. Gaussian assumption for the sensing matrix $A$ simplifies theoretical analysis, it often fails to capture the flexibility available in system design, such as choosing masks in computational imaging or pulse shapes in communications. This paper addresses a critical gap: how does the spectral "shape" of $A$—the distribution of its singular values—affect recovery performance?
The core challenge lies in understanding whether a specific matrix structure helps or hurts efficient recovery algorithms like Expectation Propagation (EP). By characterizing the spectrum's "spikiness," the authors provide a new lens through which to optimize sensing matrix design.
Methodology and Theoretical Tools
The authors analyze the GLM-EP algorithm, a powerful iterative method for solving GLMs. To provide a rigorous analysis, they introduce three primary tools:
- State Evolution (SE): A framework that exactly predicts the algorithm's Mean Squared Error (MSE) at each iteration in the large-system limit.
- Lorenz Partial Order: Borrowed from economics, this concept is used to formally define the "spikiness" of a matrix's spectrum. A spiky spectrum is characterized by a few dominant eigenvalues and many small ones, whereas a "flat" spectrum (like an orthogonal matrix) has more uniform eigenvalues.
- Information-Theoretic Limits: Benchmarks based on the Rényi information dimension ($d(Y)$) are derived to evaluate how closely GLM-EP approaches the absolute physical limits of recovery.
The Spikiness Duality
A central discovery of this research is that spectral spikiness is not a universal benefit; its impact depends heavily on the specific nonlinearity $f(\cdot)$ of the problem.
- Phase Retrieval ($f(z) = |z|$): In this regime, spikier spectra significantly improve recovery. The authors demonstrate that a spiky matrix allows the algorithm to succeed at sampling ratios near the theoretical minimum ($\delta \approx 1$).
- 1-bit Compressed Sensing ($f(z) = \text{sign}(z)$): Conversely, for 1-bit CS, a flatter spectrum is actually better for minimizing MSE. In noisy settings, increasing spikiness can lead to a substantial degradation in performance.
Despite this duality in MSE performance, spikiness consistently lowers the threshold for perfect recovery in noiseless settings. This suggests that for high-SNR applications, designing matrices with spiky spectra is almost always advantageous for reaching reconstruction limits.
Experimental Results and Validation
The theoretical predictions were validated through extensive synthetic simulations. Sensing matrices were constructed using Singular Value Decomposition ($A = U\Sigma V^T$), where the singular values in $\Sigma$ were sampled from a geometric distribution to precisely control spikiness via a parameter $\beta$.
Key findings from the simulations include:
- Algorithmic Optimality: In phase retrieval, GLM-EP with a highly spiky matrix ($\beta=20$) achieved reconstruction at a sampling ratio of $\delta = 1.01$, nearly reaching the information-theoretic bound of $\delta = 1$. Standard Gaussian matrices typically require much higher ratios.
- MSE Trade-offs in 1-bit CS: At a sampling ratio of $\delta=2$, the MSE increased from 0.27 with a flat spectrum ($\beta=0$) to 0.62 with a spiky spectrum ($\beta=10$), confirming that spikiness is detrimental in this context.
- Stability: The algorithm exhibits graceful degradation in the presence of noise, provided the sampling ratio remains above the critical threshold for perfect recovery.
Conclusion and Future Directions
This work provides a unified framework for understanding the interplay between sensing matrix structure and nonlinear recovery. While it establishes clear benefits for spiky spectra in lowering recovery thresholds and reaching information-theoretic limits, it also highlights task-specific trade-offs in MSE performance.
Future research directions include extending this analysis to structured signals (e.g., sparse vectors) and investigating the low-SNR regime, where the impact of the spectrum may differ from the high-SNR findings presented here. Additionally, providing a rigorous proof for the original GLM-EP algorithm, rather than the smoothed version used for theoretical derivations, remains an open challenge.
Summary updated