Abstract
We study the problem of recovering an unknown signal $\boldsymbol x$ given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator $\hat{\boldsymbol x}^{\rm L}$ and a spectral estimator $\hat{\boldsymbol x}^{\rm 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{\boldsymbol x}^{\rm L}$ and $\hat{\boldsymbol x}^{\rm s}$. At the heart of our analysis is the exact characterization of the joint empirical distribution of $(\boldsymbol x, \hat{\boldsymbol x}^{\rm L}, \hat{\boldsymbol x}^{\rm s})$ in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of $\hat{\boldsymbol x}^{\rm L}$ and $\hat{\boldsymbol x}^{\rm s}$, given the limiting distribution of the signal $\boldsymbol x$. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form $\theta\hat{\boldsymbol x}^{\rm L}+\hat{\boldsymbol x}^{\rm s}$ and we derive the optimal combination coefficient. In order to establish the limiting distribution of $(\boldsymbol x, \hat{\boldsymbol x}^{\rm L}, \hat{\boldsymbol x}^{\rm s})$, we design and analyze an Approximate Message Passing (AMP) algorithm whose iterates give $\hat{\boldsymbol x}^{\rm L}$ and approach $\hat{\boldsymbol x}^{\rm s}$. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately.
Introduction
Recovering a hidden $d$-dimensional signal $\mathbf{x}$ from $n$ noisy measurements $y_i$ is a fundamental task in statistical inference. This problem is typically modeled using a Generalized Linear Model (GLM), where $y_i = f(\langle \mathbf{a}_i, \mathbf{x} \rangle)$ for some link function $f$. Applications range from phase retrieval to 1-bit compressed sensing.
Two primary approaches are commonly employed: linear estimators (weighted averages of sensing vectors) and spectral estimators (principal eigenvectors of data-dependent matrices). While linear estimators are computationally simple, they fail for even link functions. Spectral estimators are more robust in such cases but may underperform elsewhere. This paper provides a rigorous framework for the Bayes-optimal combination of these two estimators.
Methodology: AMP and State Evolution
The researchers utilize Approximate Message Passing (AMP) as a mathematical tool to characterize the joint empirical distribution of the signal and the two estimators in the high-dimensional limit ($n, d \to \infty$ at a fixed ratio $\delta = n/d$). By designing a specific AMP algorithm whose iterates converge to the spectral estimator while tracking the linear one, they derive "state evolution" equations. These equations reduce the complex vector estimation problem to a 1D scalar problem, enabling the use of Bayes' rule to find the optimal fusion strategy.
The Bayes-Optimal Combination
For the common case of Gaussian signals, the authors prove that the optimal combination is a weighted sum: $\hat{\mathbf{x}}^* = \theta \hat{\mathbf{x}}^L + \hat{\mathbf{x}}^s$. They provide an exact formula for the optimal coefficient $\theta^*$, which depends on the sampling ratio $\delta$.
Numerical Results and Performance
Numerical simulations validate the theoretical findings across various link functions and signal priors. The combined estimator consistently achieves higher overlap (correlation) with the true signal compared to using either method in isolation.
Key insights include:
- Significant Gains: In quadratic link functions, the combined estimator shows up to a 30% performance boost.
- Correlation Awareness: The optimal combination accounts for the cross-correlation between estimators, effectively subtracting redundant information.
- Warm Starts: The combined estimator provides a superior initialization for more complex iterative recovery algorithms, leading to faster convergence.
Conclusion and Limitations
This research provides a rigorous framework for combining linear and spectral estimators in GLMs. While powerful, the current framework assumes i.i.d. Gaussian sensing matrices. Extending this to broader classes of matrices remains an open question. Additionally, while the combination is optimal for given preprocessing functions, finding the globally optimal preprocessing functions for the combined estimator is a significant future challenge. Finally, the spectral component's computational cost (eigenvector calculation) may be a factor in extremely large-scale applications.
Summary updated