Fast approximation of matrix coherence and statistical leverage

Abstract

The statistical leverage scores of a matrix $A$ are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nyström-based low-rank matrix approximation as well as in large-scale statistical data analysis applications more generally; moreover, they are of interest since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary $n\times d$ matrix $A$, with $n\gg d$, and that returns as output relative-error approximations to all $n$ of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of $n$ and $d$) in $O(nd\log n)$ time, as opposed to the $O(n{d}^2)$ time required by the naïve algorithm that involves computing an orthogonal basis for the range of $A$. Our analysis may be viewed in terms of computing a relative-error approximation to an underconstrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with $n\approx d$, and the extension to streaming environments.

29 pages; conference version is in ICML; journal version is in JMLR

References in corpus (2)

• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Streaming Algorithms from Precision Sampling

Cited by in corpus (32)

• Sketching as a Tool for Numerical Linear Algebra
• Fast Resampling of 3D Point Clouds via Graphs
• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• OverSketch: Approximate Matrix Multiplication for the Cloud
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• CUR Algorithm for Partially Observed Matrices
• BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees
• A literature survey of matrix methods for data science
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Low Rank Approximation and Regression in Input Sparsity Time
• Sensing Matrix Design and Sparse Recovery on the Sphere and the Rotation Group
• Randomized methods to characterize large-scale vortical flow network
• Self-Expressive Decompositions for Matrix Approximation and Clustering
• A determinantal point process for column subset selection
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
• Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Binary matrix factorization on special purpose hardware
• A Sketched Finite Element Method for Elliptic Models
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Faster Subset Selection for Matrices and Applications
• Sharper Bounds for Regularized Data Fitting
• Identifying Influential Entries in a Matrix
• Compressed and Penalized Linear Regression
• Lower bounds for oblivious subspace embeddings
• Analysis of Nystrom method with sequential ridge leverage scores
• On the asymptotic properties of a bagging estimator with a massive dataset
• Regularized ERM on random subspaces
• Fast Fourier-Based Generation of the Compression Matrix for Deterministic Compressed Sensing