Analysis of Sensing Spectral for Signal Recovery under a Generalized Linear Model

Junjie Ma, Ji Xu, Arian Maleki

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?

Example of a nonlinear step function $f(z)$ and its inverse mapping $f^{-1}(y)$, typical in quantized sensing.

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)$).
Plot illustrating the behavior of the $G(v_r)$ function, which dictates whether a spiky spectrum helps or hurts recovery.

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

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. By properly specifying the nonlinear processing function, this model can be particularized to many signal processing problems, including compressed sensing and phase retrieval. Our main goal in this paper is to understand the impact of sensing matrices, or more specifically the spectrum of sensing matrices, on the difficulty of recovering $\mathbf{x}$ from $\mathbf{y}$. Towards this goal, we study the performance of one of the most successful recovery methods, i.e. the expectation propagation algorithm (EP). We define a notion for the spikiness of the spectrum of $\mathbf{A}$ and show the importance of this measure in the performance of the EP. Whether the spikiness of the spectrum can hurt or help the recovery performance of EP depends on $f$. We define certain quantities based on the function $f$ that enables us to describe the impact of the spikiness of the spectrum on EP recovery. Based on our framework, we are able to show that for instance, in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky (flatter) spectrums offer better recoveries. Our results unify and substantially generalize the existing results that compare sub-Gaussian and orthogonal matrices, and provide a platform toward designing optimal sensing systems.
BibTeX
@inproceedings{ma2021analysis,
  author = {Junjie Ma and Ji Xu and Arian Maleki},
  title = {{Analysis of Sensing Spectral for Signal Recovery under a Generalized Linear Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=5-iRjd9FreV},
}
Figure