Second order accurate distributed eigenvector computation for extremely\n large matrices

2009/08/02 by Noureddine El Karoui, Karoui, Noureddine El, Alexandre d’Aspremont +1 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.0908.0137

openalex publication_date 2009/08/02 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

We propose a second-order accurate method to estimate the eigenvectors of\nextremely large matrices thereby addressing a problem of relevance to\nstatisticians working in the analysis of very large datasets. More\nspecifically, we show that averaging eigenvectors of randomly subsampled\nmatrices efficiently approximates the true eigenvectors of the original matrix\nunder certain conditions on the incoherence of the spectral decomposition. This\nincoherence assumption is typically milder than those made in matrix completion\nand allows eigenvectors to be sparse. We discuss applications to spectral\nmethods in dimensionality reduction and information retrieval.\n

Cited by

• Estimating eigenvectors and eigenspaces of covariance matrices: Optimal Bounds and Conditions for Consistency

Related

• Spectral approximations in machine learning
• Fast One-Pass Sparse Approximation of the Top Eigenvectors of Huge Low-Rank Matrices? Yes, MAM^*!
• Estimating the Spectral Density of Large Implicit Matrices
• Spectrum estimation for large dimensional covariance matrices using random matrix theory
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank