Entrywise eigenvector analysis of random matrices with low expected rank

DOI10.1214/19-AOS1854MaRDI QIDQ2196228zbMATH OpenOpenAlexFDO

Authors Emmanuel Abbe, Kaizheng Wang, Yiqiao Zhong, Jianqing Fan

Publication date 28 August 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.09565, https://projecteuclid.org/euclid.aos/1594972825

community detection eigenvector perturbation low-rank structures matrix completion random matrices spectral analysis synchronization

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Estimation in multivariate analysis (62H12) Factor analysis and principal components; correspondence analysis (62H25)

Abstract: Recovering low-rank structures via eigenvector perturbation analysis is a common problem in statistical machine learning, such as in factor analysis, community detection, ranking, matrix completion, among others. While a large variety of bounds are available for average errors between empirical and population statistics of eigenvectors, few results are tight for entrywise analyses, which are critical for a number of problems such as community detection. This paper investigates entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low-rank, which helps settle the conjecture in Abbe et al. (2014b) that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. The key is a first-order approximation of eigenvectors under the

e l l_{i} n f t y

norm:

u_k approx frac{A u_k^*}{lambda_k^*},

where

u_{k}

and

u_{k}^{*}

are eigenvectors of a random matrix

A

and its expectation

m a t h b b E A

, respectively. The fact that the approximation is both tight and linear in

A

facilitates sharp comparisons between

u_{k}

and

u_{k}^{*}

. In particular, it allows for comparing the signs of

u_{k}

and

u_{k}^{*}

even if

| u_{k} - u_{k}^{*} |_{i n f t y}

is large. The results are further extended to perturbations of eigenspaces, yielding new

e l l_{i} n f t y

-type bounds for synchronization (

m a t h b b Z_{2}

-spiked Wigner model) and noisy matrix completion.

Review text

This paper is a study on the analysis of eigenvector disturbance, which is a common problem in statistical machine learning. Many estimation problems in statistics involve low-rank matrix estimators that are NP-hard to calculate, and many of these estimators are solutions to nonconvex programs. The authors investigate entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low rank, which helps to settle a conjecture that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. They investigate entry behaviors, self-spaces, for random matrices with low expected rank. The \( \ell_\infty \) distance between the eigenvectors of a random matrix and its expected counterparts may not be the correct to look at; input errors can be distributed asymmetrically. Let \(A\) be a random matrix, \(A^{\ast}=\mathbb{E}(A)\) and \(E = A - A^{\ast}\) be the ``error of \(A\), \(A\) symmetric, \(u_k\), respectively \(u_k^{\ast}\), be the eigenvector corresponding to the \(k\)-th largest eigenvalue of \(A\), respectively \(A^{\ast}\). If \(E\) is moderate, hence \(u_k=\displaystyle\frac{Au_k^{\ast}}{\lambda_k}\approx\displaystyle\frac{Au_k^{\ast}}{\lambda_k^{\ast}}=u_k^{\ast}+\frac{Eu_k^{\ast}}{\lambda_k^{\ast}}\). This perturbation analysis leads to new and sharp theoretical guarantees. To obtain such results, the authors characterize the concentration properties of \( A \) and structural assumptions in their expectation \( A^{\ast} \). For the exact recovery problem in the stochastic block model, the vanilla spectral algorithm reaches the theoretical limit of the information and coincides with the MLE estimator whenever it is successful. Therefore, MLE and SDP have no advantage over the spectral method in terms of exact recovery if the model is correct.

Recommendations

Cites work

Cited in

(96)

Describes a project that uses

Uses Software

Wirtinger Flow

This page was built for publication: Entrywise eigenvector analysis of random matrices with low expected rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196228)