Randomized algorithms for matrices and data

Abstract

Randomized algorithms for very large matrix problems have received a great deal of attention in recent years. Much of this work was motivated by problems in large-scale data analysis, and this work was performed by individuals from many different research communities. This monograph will provide a detailed overview of recent work on the theory of randomized matrix algorithms as well as the application of those ideas to the solution of practical problems in large-scale data analysis. An emphasis will be placed on a few simple core ideas that underlie not only recent theoretical advances but also the usefulness of these tools in large-scale data applications. Crucial in this context is the connection with the concept of statistical leverage. This concept has long been used in statistical regression diagnostics to identify outliers; and it has recently proved crucial in the development of improved worst-case matrix algorithms that are also amenable to high-quality numerical implementation and that are useful to domain scientists. Randomized methods solve problems such as the linear least-squares problem and the low-rank matrix approximation problem by constructing and operating on a randomized sketch of the input matrix. Depending on the specifics of the situation, when compared with the best previously-existing deterministic algorithms, the resulting randomized algorithms have worst-case running time that is asymptotically faster; their numerical implementations are faster in terms of clock-time; or they can be implemented in parallel computing environments where existing numerical algorithms fail to run at all. Numerous examples illustrating these observations will be described in detail.

Review article, 54 pages, 198 references. Version appearing as a monograph in Now Publishers' "Foundations and Trends in Machine Learning" series

References in corpus (13)

• Sparsity and Incoherence in Compressive Sampling
• Data Mining and Machine Learning in Astronomy
• Spectra of Sparse Random Matrices
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• Principal Component Analysis of SDSS Stellar Spectra
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• On sparse representations of linear operators and the approximation of matrix products
• LSRN: A Parallel Iterative Solver for Strongly Over- or Under-Determined Systems
• An algorithm for the principal component analysis of large data sets
• Algorithmic and Statistical Challenges in Modern Large-Scale Data Analysis are the Focus of MMDS 2008
• Computation in Large-Scale Scientific and Internet Data Applications is a Focus of MMDS 2010
• A fast randomized algorithm for orthogonal projection

Cited by in corpus (85)

• Sketching as a Tool for Numerical Linear Algebra
• An overview of low-rank matrix recovery from incomplete observations
• Fast approximation of matrix coherence and statistical leverage
• A Statistical Perspective on Algorithmic Leveraging
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Randomized QR with Column Pivoting
• Sharp analysis of low-rank kernel matrix approximations
• Sub-sampled Newton Methods with Non-uniform Sampling
• Optimal approximate matrix product in terms of stable rank
• Straggler Mitigation in Distributed Optimization Through Data Encoding
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
• The spectral norm error of the naive Nystrom extension
• Exact expressions for double descent and implicit regularization via surrogate random design
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• PyHessian: Neural Networks Through the Lens of the Hessian
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Fast MCMC sampling algorithms on polytopes
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Fast and Robust Least Squares Estimation in Corrupted Linear Models
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Completing Any Low-rank Matrix, Provably
• "Influence Sketching": Finding Influential Samples In Large-Scale Regressions
• A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares
• Matrix Factorization at Scale: a Comparison of Scientific Data Analytics in Spark and C+MPI Using Three Case Studies
• On the Nyström and Column-Sampling Methods for the Approximate Principal Components Analysis of Large Data Sets
• Faster Least Squares Optimization
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Improved Analyses of the Randomized Power Method and Block Lanczos Method
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
• Sample-Optimal Low-Rank Approximation of Distance Matrices
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Integrating multiple random sketches for singular value decomposition
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
• Randomized spectral co-clustering for large-scale directed networks
• How to reduce dimension with PCA and random projections?
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Scalable and Efficient Statistical Inference with Estimating Functions in the MapReduce Paradigm for Big Data
• Parallel MMF: a Multiresolution Approach to Matrix Computation
• CUR Low Rank Approximation of a Matrix at Sublinear Cost
• Estimating the inverse trace using random forests on graphs
• GPU Accelerated Sub-Sampled Newton's Method
• Subspace Iteration Randomization and Singular Value Problems
• Hessian-Aware Pruning and Optimal Neural Implant
• DUAL-LOCO: Distributing Statistical Estimation Using Random Projections
• Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis
• Incremental kernel PCA and the Nyström method
• Magging: maximin aggregation for inhomogeneous large-scale data
• Randomized Iterative Algorithms for Fisher Discriminant Analysis
• Distributed Averaging Methods for Randomized Second Order Optimization
• Robust sketching for multiple square-root LASSO problems
• The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
• Sketching for Kronecker Product Regression and P-splines
• Identifying Influential Entries in a Matrix
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Preconditioning in Expectation
• Randomized Dimension Reduction on Massive Data
• Relating Leverage Scores and Density using Regularized Christoffel Functions
• Learning Machines Implemented on Non-Deterministic Hardware
• Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
• Adaptive Randomized Dimension Reduction on Massive Data
• Incomplete Pivoted QR-based Dimensionality Reduction
• Scalable $M$-Channel Critically Sampled Filter Banks for Graph Signals
• Faster Coreset Construction for Projective Clustering via Low-Rank Approximation
• A Randomized Tensor Singular Value Decomposition based on the t-product
• Lazy stochastic principal component analysis
• Relations among Some Low Rank Subspace Recovery Models
• Diffusion Maps meet Nyström
• Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketches
• Solving $k$-means on High-dimensional Big Data
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Tight Bounds for ${\ell }_p$ Oblivious Subspace Embeddings
• Exploiting the Structure via Sketched Gradient Algorithms
• Pass-Efficient Randomized LU Algorithms for Computing Low-Rank Matrix Approximation
• Regularized ERM on random subspaces
• Fast Derandomized Low-rank Approximation and Extensions
• Statistical and Algorithmic Perspectives on Randomized Sketching for Ordinary Least-Squares -- ICML
• Coresets for Dependency Networks
• Model-specific Data Subsampling with Influence Functions
• Seeing the Forest from the Trees in Two Looks: Matrix Sketching by Cascaded Bilateral Sampling
• Pyramid: Enhancing Selectivity in Big Data Protection with Count Featurization
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Farthest sampling segmentation of triangulated surfaces
• Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations