Spectral Estimators for Structured Generalized Linear Models via
  Approximate Message Passing
Yihan Zhang Hong Chang Ji Ramji Venkataramanan Marco Mondelli
We consider the problem of parameter estimation from observations given by a
generalized linear model. Spectral methods are a simple yet effective approach
for estimation: they estimate the parameter via the principal eigenvector of a
matrix obtained by suitably preprocessing the observations. Despite their wide
use, a rigorous performance characterization of spectral estimators, as well as
a principled way to preprocess the data, is available only for unstructured
(i.e., i.i.d. Gaussian and Haar) designs. In contrast, real-world design
matrices are highly structured and exhibit non-trivial correlations. To address
this problem, we consider correlated Gaussian designs which capture the
anisotropic nature of the measurements via a feature covariance matrix
$\Sigma$. Our main result is a precise asymptotic characterization of the
performance of spectral estimators in this setting. This then allows to
identify the optimal preprocessing that minimizes the number of samples needed
to meaningfully estimate the parameter. Remarkably, such an optimal spectral
estimator depends on $\Sigma$ only through its normalized trace, which can be
consistently estimated from the data. Numerical results demonstrate the
advantage of our principled approach over previous heuristic methods.
  Existing analyses of spectral estimators crucially rely on the rotational
invariance of the design matrix. This key assumption does not hold for
correlated Gaussian designs. To circumvent this difficulty, we develop a novel
strategy based on designing and analyzing an approximate message passing
algorithm whose fixed point coincides with the desired spectral estimator. Our
methodology is general, and opens the way to the precise characterization of
spiked matrices and of the corresponding spectral methods in a variety of
settings.