Faster least squares approximation

By Petros Drineas, Michael W. Mahoney, S. Muthu Muthukrishnan, Tamás Sarlós. Numerische Mathematik, 2007

506 citations recorded by the source corpus.

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets n be the number of constraints and d be the number of variables, with $${n \gg d}$$. Then, existing exact methods find a solution vector in O(nd2) time. We present two randomized algorithms that provide accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if n is sufficiently larger than d, the approximate solution can be computed in O(nd ln d) time.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/9c47a465e02cd7c3470559d772dd6328ba8b77cc

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 Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “For recent advances in the area of sketching we suggest [197, 66, 37, 122, 44, 155].”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “It has many applications (cf. [58, 3, 20]), including providing another method for approximating the L 2 norm of a frequency vector of a stream of data items.”
A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression (2019, background): “Although the theories in (Avron, Clarkson, and Woodruff 2016; Clarkson and Woodruff 2013; Drineas, Mahoney, and Muthukrishnan 2006; Drineas et al. 2011) showed that this approximate solution, denote ˜ w , is not far from the ERM solution w erm in the (cid:96) 2 norm sense, it magniﬁes either the…”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Our technique is also closely related to randomized linear algebra and sketching techniques [14, 6, 17], used for dimensionality reduction of large convex optimization problems.”
Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems (2014, unknown): “[20, 21, 22, 23, 24].”
Randomized Iterative Methods for Linear Systems (2015, background): “While classical iterative methods are deterministic, recent breakthroughs suggest that randomization can play a powerful role in the design and analysis of efficient algorithms [38, 19, 22, 9, 41, 18, 21, 29] which are in many situations competitive or better than existing deterministic methods.”
A sparse Johnson: Lindenstrauss transform (2010, unknown): “…applications including nearest-neighbor search [2, 19], compressed sensing [11], data stream computations [5], computational geometry [13], numerical linear algebra [14,17,26,28], machine learning [8,33], graph sparsiﬁcation [30], and more; see the monograph [32] for further applications.”
Randomized Extended Kaczmarz for Solving Least Squares (2012, methodology): “…generic two step procedure: ﬁrst randomly (and efﬁciently) project the linear system into sufﬁciently many dimensions, and second return the solution of the down-sampled linear system as an approximation to the original optimal solution [DMM06, Sar06, CW09, NDT09, MZ11, DMMS11], see also [CW12].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “The proof of Drineas et al. [2011] proceeds by choosing a subspace embedding (cid:20) 1 , computing (cid:20) 1 A , then computing a change of basis matrix R so that (cid:20) 1 AR has orthonormal columns.”
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (2012, background): “[17]), and T p( ;n′, d) = O((n′d2 + poly(d)) log(n′/ )), for general p (see Mitchell [25]).”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, background): “Given a fast routine for matrix-vector multiplication, the sketch SM for a data matrix M ∈ Rn×d can be formed in O(n d logm) time (for instance, see the papers [3, 2, 14]).”
Handbook of Big Data (2016, background): “Most fundamentally, it should be observed that increasing n , the number of cases, and increasing p , the number of variables, each has very diﬀerent and in some ways opposite eﬀects on statistical analysis.”
An investigation of Newton-Sketch and subsampled Newton methods (2017, background): “[7] Petros Drineas, Michael W Mahoney, S Muthukrishnan, and Tamás Sarlós.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, unknown): “Methods based on randomized linear algebra, sketching and suitable subsampling [17, 18, 11] are able to find the solution with precision in time that isO((nd+min(n, d)(3)) log(L/λ )), so essentially independently of the condition number, because of the logarithmic complexity in λ.”
TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES (2011, methodology): “f the law of large numbers for sums of rank-one matrices. This result has found many applications, including column-subset selection [RV07] and the fast approximate solution of least-squares problems [DMMS11]. The NCKI and its corollaries do not always yield sharp results because parasitic logarithm”
Numerical linear algebra in the streaming model (2009, background): “1 is not far that of from Theorem 12 of [23], or that in [14].”