Fast approximation of matrix coherence and statistical leverage

By Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff. 2011

583 citations recorded by the source corpus.

The statistical leverage scores of a data matrix are the squared row-norms of any matrix whose columns are obtained by orthogonalizing the columns of the data matrix; and, the coherence is the largest leverage score. These quantities play an important role in several machine learning algorithms because they capture the key structural nonuniformity of the data matrix that must be dealt with in developing efficient randomized algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n × d matrix A, with n ≫ d, and returns, as output, relative-error approximations to all n of the statistical leverage scores. The proposed algorithm runs in O(nd log n) time, as opposed to the O(nd2) time required by the naive algorithm that involves computing an orthogonal basis for the range of A. This resolves an open question from (Drineas et al., 2006) and (Mohri & Talwalkar, 2011); and our result leads to immediate improvements in coreset-based l2-regression, the estimation of the coherence of a matrix, and several related low-rank matrix problems. Interestingly, to achieve our result we judiciously apply random projections on both sides of A.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Fast Randomized Kernel Methods With Statistical Guarantees (2014, methodology): “…low-rank approximation of positive semideﬁnite matrices could be obtained in one of two related ways: either compute (with the fast algorithm of [5]) approximations to the leverage scores, and use those approximations as an importance sampling distribution in a random sampling algorithm; or…”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, background): “, n, where U ∈ Rn×d is the matrix of left singular vectors of M [6].”
ActiveClean: Interactive Data Cleaning For Statistical Modeling (2016, result): “This line of work builds on prior results in linear algebra that show that some matrix columns are more informative than others [12], and Active Learning which shows that some labels are more informative that others [31].”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, background): “See, e.g., work on CUR matrix decompositions [5, 6], work on the the fast approximation of the statistical leverage scores [7], and the recent review [8] for more details.”
Generalization Properties of Learning with Random Features (2016, methodology): “For this latter case, we borrow and extend ideas from [22, 16] and inspired from the theory of statical leverage scores [23].”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, background): “Alternatively, on can perform a random projection followed by uniform sampling in the randomly rotated space [20].”
Optimal subsampling for quantile regression in big data (2020, background): “This idea has attracted much attention with extensive literature such as Drineas et al. (2012); Dhillon et al. (2013); Yang et al. (2013); Ma et al. (2015); Wang et al. (2018).”
Simple and deterministic matrix sketching (2012, background): “The discussion on matrix leverage scores goes beyond the scope of this paper, see [22] for more information and references.”
Per-instance Differential Privacy and the Adaptivity of Posterior Sampling in Linear and Ridge regression (2017, methodology): “…measures the importance/uniqueness of a data point relative to the rest of the data set and it is used extensively in regression analysis [5] (for outlier detection and experiment design), compressed sensing (for adaptive sampling) [29] and numerical linear algebra (for fast matrix computation)[8].”
Continual Learning via Online Leverage Score Sampling (2019, methodology): “In recent applications [5, 37], it also emerges as a fundamental tool for constructing randomized matrix sketches.”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, methodology): “Here, we adopt the fast approximation algorithm for standard leverage scores, [6], to obtain an efficient approximation to our block partial leverage scores.”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “Using randomization, this can be solved in O ( nd log n + d 3 log d log n ) time [Drineas et al. 2012].”
LOCO: Distributing Ridge Regression with Random Projections (2014, methodology): “arning tasks (Ailon and Chazelle, 2009). Notably, structured random projections have been used to speed up approximate kernel expansions (Le et al., 2013), computation of statistical leverage scores (Drineas et al., 2011; McWilliams et al., 2014) and linear regression. For the latter, it can be show”
Per-instance Differential Privacy (2017, methodology): “Leverage score measures the importance/uniqueness of a data point relative to the rest of the data set and it is used extensively in regression analysis (Chatterjee & Hadi, 1986) (for outlier detection and experiment design), graph sparsification (for adaptive sampling) (Spielman & Srivastava, 2011)”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “Exact computation of leverage scores is expensive, so we also consider two sketches that use approximate leverage scores: the “power” scheme iteratively approximates the leverage scores of A and uses the approximate leverage scores obtained once a specified convergence condition has been met; and th”
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (2012, methodology): “See [20, 15] for details; and note that they can be generalized to `1 and other `p norms [10] as well as to arbitrary n×d matrices, with both n and d large [21, 15].”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, methodology): “Here we state the consequences of plugging our OSE’s into known previous work for various numerical linear algebra problems [8], [9], [11], [12], [14], [15], [22].”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “leverage scores, then by sampling O(nε−2 logn) edges of G and reweighting them, one obtains a spectral sparsiﬁer of G. One can use algorithms for approximating the leverage scores of general matrices [44], though more eﬃcient algorithms, 102 whose overall running time is near-linear in the number of”