Abstract
We consider a nonlinear inverse problem $\mathbf{y}= f(\mathbf{Ax})$, where observations $\mathbf{y} \in \mathbb{R}^m$ are the componentwise nonlinear transformation of $\mathbf{Ax} \in \mathbb{R}^m$, $\mathbf{x} \in \mathbb{R}^n$ is the signal of interest and $\mathbf{A}$ is a known linear mapping. Our main goal in this paper is to understand the impact of the spectrum of sensing matrices on the difficulty of recovering $\mathbf{x}$ from $\mathbf{y}$. We study the performance of the expectation propagation algorithm (EP) and define a measure for the "spikiness" of the spectrum of $\mathbf{A}$. We show that whether the spikiness of the spectrum hurts or helps recovery depends on the nonlinearity $f$. Based on our framework, we demonstrate that in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, flatter spectrums offer better recoveries.
Introduction
In Generalized Linear Models (GLMs), the objective is to recover a signal $\mathbf{x}$ from nonlinear measurements $\mathbf{y} = f(\mathbf{Ax})$. While standard theoretical analysis often assumes i.i.d. Gaussian sensing matrices $\mathbf{A}$—which possess relatively flat spectra—real-world sensing matrices frequently exhibit diverse spectral properties. This paper addresses the fundamental question: How does the "spikiness" or "flatness" of the spectrum of $\mathbf{A}$ impact signal recovery? We provide a unified theoretical framework to explain why specific matrix structures are optimal for certain nonlinearities but detrimental to others.
Methodology
The analysis centers on the Expectation Propagation (EP) algorithm, a powerful iterative method for inverse problems. To characterize its performance in the large system limit, we utilize State Evolution (SE), which tracks the mean squared error (MSE) across iterations. We formally define spectral "spikiness" using the Lorenz Partial Order, a concept borrowed from economics to measure inequality; here, a spiky spectrum indicates a high concentration of energy in a few eigenvalues. Furthermore, Rényi Information Dimension is employed to establish information-theoretic lower bounds, allowing us to evaluate how closely EP approaches optimal recovery.
Experiments were conducted using synthetic Gaussian signals and structured random matrices generated via Singular Value Decomposition (SVD). The singular values follow a geometric distribution, where a parameter $\beta$ controls the degree of spikiness, implemented efficiently using Discrete Cosine Transforms (DCT).
The $G(v_r)$ Criterion and Spectral Impact
A central finding of this work is that the optimal sensing spectrum is dictated by the specific nonlinearity $f$. We identify a scalar function, $G(v_r)$, derived from $f$, which serves as a predictor for the impact of spectral spikiness.
- Increasing $G(v_r)$: When $G$ is an increasing function, as seen in phase retrieval ($f(z) = |z|$), a spikier spectrum significantly enhances recovery. Spikiness helps the algorithm resolve phase ambiguities more effectively.
- Decreasing $G(v_r)$: Conversely, if $G$ is decreasing, as in 1-bit compressed sensing ($f(z) = \text{sign}(z)$), a flatter spectrum (e.g., an orthogonal matrix) is preferred.
By tuning the spikiness of the sensing matrix based on this criterion, the EP algorithm can be made to approach the information-theoretic limit, achieving recovery with the absolute minimum number of measurements required.
Results and Conclusion
Simulations in phase retrieval demonstrate that increasing spectral spikiness allows for perfect recovery with fewer measurements, shifting the phase transition boundary closer to the theoretical limit. The framework also proves that recovery remains stable under noise, provided the measurement ratio exceeds the perfect recovery threshold.
While this work provides a robust theory for rotationally invariant matrices and generic signals, future research is needed to incorporate signal structures like sparsity and to extend the analysis to low-SNR regimes and more constrained matrix structures, such as circulant matrices used in optical imaging. Ultimately, this research offers a platform for designing optimal sensing systems tailored to specific nonlinear measurement processes.
Summary updated