Spectral Methods for Data Science: A Statistical Perspective

Abstract

Spectral methods have emerged as a simple yet surprisingly effective approach for extracting information from massive, noisy and incomplete data. In a nutshell, spectral methods refer to a collection of algorithms built upon the eigenvalues (resp. singular values) and eigenvectors (resp. singular vectors) of some properly designed matrices constructed from data. A diverse array of applications have been found in machine learning, data science, and signal processing. Due to their simplicity and effectiveness, spectral methods are not only used as a stand-alone estimator, but also frequently employed to initialize other more sophisticated algorithms to improve performance. While the studies of spectral methods can be traced back to classical matrix perturbation theory and methods of moments, the past decade has witnessed tremendous theoretical advances in demystifying their efficacy through the lens of statistical modeling, with the aid of non-asymptotic random matrix theory. This monograph aims to present a systematic, comprehensive, yet accessible introduction to spectral methods from a modern statistical perspective, highlighting their algorithmic implications in diverse large-scale applications. In particular, our exposition gravitates around several central questions that span various applications: how to characterize the sample efficiency of spectral methods in reaching a target level of statistical accuracy, and how to assess their stability in the face of random noise, missing data, and adversarial corruptions? In addition to conventional ${\ell }_2$ perturbation analysis, we present a systematic ${\ell }_{\infty }$ and ${\ell }_{2,\infty }$ perturbation theory for eigenspace and singular subspaces, which has only recently become available owing to a powerful "leave-one-out" analysis framework.

Cited by in corpus (18)

• Stability and Super-resolution of MUSIC and ESPRIT for Multi-snapshot Spectral Estimation
• Uncertainty-Guided Mixup for Semi-Supervised Domain Adaptation without Source Data
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• A useful criterion on studying consistent estimation in community detection
• A Spectral Method for Identifiable Grade of Membership Analysis with Binary Responses
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Finding mixed memberships in categorical data
• Optimal tuning-free convex relaxation for noisy matrix completion
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Factor-Driven Network Informed Restricted Vector Autoregression
• Mixed membership estimation for categorical data with weighted responses
• Hub Detection in Gaussian Graphical Models
• Overlapping community detection in weighted networks