Abstract
We study the problem of recovering an unknown signal $\mathbf{x}$ given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator $\hat{\mathbf{x}}^L$ and a spectral estimator $\hat{\mathbf{x}}^s$. The former is a data-dependent linear combination of the columns of the measurement matrix, and its analysis is quite simple. The latter is the principal eigenvector of a data-dependent matrix, and a recent line of work has studied its performance. In this paper, we show how to optimally combine $\hat{\mathbf{x}}^L$ and $\hat{\mathbf{x}}^s$. At the heart of our analysis is the exact characterization of the empirical joint distribution of $(\mathbf{x}, \hat{\mathbf{x}}^L, \hat{\mathbf{x}}^s)$ in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of $\hat{\mathbf{x}}^L$ and $\hat{\mathbf{x}}^s$, given the limiting distribution of the signal $\mathbf{x}$. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form $\theta \hat{\mathbf{x}}^L + \hat{\mathbf{x}}^s$ and we derive the optimal combination coefficient. In order to establish the limiting distribution of $(\mathbf{x}, \hat{\mathbf{x}}^L, \hat{\mathbf{x}}^s)$, we design and analyze an approximate message passing algorithm whose iterates give $\hat{\mathbf{x}}^L$ and approach $\hat{\mathbf{x}}^s$. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately.
Introduction
In signal processing and machine learning, the "Generalized Linear Model" (GLM) problem involves recovering an unknown vector $\mathbf{x}$ from noisy, non-linear measurements $y_i \sim p(y | \langle \mathbf{x}, \mathbf{a}_i \rangle)$. This framework encompasses diverse applications, from phase retrieval in imaging to the analysis of simple neural networks.
Historically, two primary estimators have been used:
- Linear Estimators ($\hat{\mathbf{x}}^L$): These are weighted sums of sensing vectors. While easy to analyze, they often fail in scenarios like phase retrieval where signal sign information is lost.
- Spectral Estimators ($\hat{\mathbf{x}}^s$): These are derived from the principal eigenvector of a data-dependent matrix. They excel in phase retrieval but may perform poorly in other contexts, such as 1-bit compressed sensing.
Until now, there was no unified framework to optimally combine these complementary tools. This research provides the mathematical foundation to fuse them into a single, Bayes-optimal estimator.
Methodology
The study employs a rigorous high-dimensional analysis where the number of measurements $n$ and the signal dimension $d$ both tend to infinity at a fixed ratio $\delta = n/d$.
The AMP Framework
The core innovation lies in using Approximate Message Passing (AMP) as a theoretical tool. The authors designed an AMP algorithm whose iterates are mathematically guaranteed to approach both the linear and spectral estimators. By analyzing the "state evolution" of this algorithm, they derived the exact joint empirical distribution of the signal and the two estimators. This characterization reveals how errors in linear and spectral methods are correlated, enabling the application of Bayes' rule to find the optimal combination.
Validation
The theoretical predictions were validated using synthetic Monte Carlo simulations with Gaussian sensing matrices—the standard benchmark for high-dimensional recovery. The method was evaluated across different signal priors, including Gaussian and binary ($\pm 1$) distributions.
Key Insights
- Complementary Strengths: Linear estimators capture "first-order" information, while spectral estimators capture "second-order" structure.
- Non-Linear Fusion: For Gaussian signals, a simple linear combination $\theta \hat{\mathbf{x}}^L + \hat{\mathbf{x}}^s$ is optimal. However, for other distributions like binary signals, the optimal fusion is a non-linear component-wise function.
- Improved Initialization: The combined estimator provides a superior "warm start" for local recovery algorithms like Gradient Descent, leading to faster convergence and higher final accuracy.
Results and Discussion
The paper provides closed-form formulas for the asymptotic correlation (overlap) of the combined estimator. Numerical experiments demonstrate significant performance gains.
As shown in Figure 6(a), the combined estimator $\rho_*$ consistently outperforms both the linear ($\rho_L$) and spectral ($\rho_s$) estimators across various measurement rates $\delta$. In specific models, such as quadratic measurements, the fusion achieves a correlation boost of up to 30%. The method is also robust; if one estimator is ineffective, the fusion naturally prioritizes the better one while still leveraging signal priors for marginal gains.
Conclusion and Future Work
While this work establishes a powerful framework for optimal signal recovery, it currently relies on the assumption of Gaussian sensing matrices. Future research could extend these results to more structured matrices found in practical applications like MRI. Additionally, while the current method assumes knowledge of the measurement model and signal prior, developing a "blind" optimal combiner remains an open challenge. Further optimization of the preprocessing functions themselves could also yield additional performance improvements.
Summary updated