Sketching as a Tool for Numerical Linear Algebra
By David P. Woodruff. 2014
1,373 citations recorded by the source corpus.
This survey highlights the recent advances in algorithms for numericallinear algebra that have come from the technique of linear sketching,whereby given a matrix, one first compresses it to a much smaller matrixby multiplying it by a (usually) random matrix with certain properties.Much of the expensive computation can then be performed onthe smaller matrix, thereby accelerating the solution for the originalproblem. In this survey we consider least squares as well as robust regressionproblems, low rank approximation, and graph sparsification.We also discuss a number of variants of these problems. Finally, wediscuss the limitations of sketching methods.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training, Numerical Methods & Scientific Computing
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
- Peter Richtárik
- Nicolas Loizou
- Jakub Konecný
- Martin Jaggi
- Simon Lacoste-Julien
- Francis R. Bach
- Sebastian U. Stich
- H. Brendan McMahan
In Computational Theory and Mathematics
- Nicolas Loizou
- David P. Woodruff
- Jakub Konecný
- Peter Richtárik
- H. Brendan McMahan
- Francis R. Bach
- Shusen Wang
- Peilin Zhong
In Optimization & Training
- Peter Richtárik
- Nicolas Loizou
- Jakub Konecný
- Simon Lacoste-Julien
- Martin Jaggi
- Francis R. Bach
- H. Brendan McMahan
- Sebastian U. Stich
In Numerical Methods & Scientific Computing
- Nicolas Loizou
- Jakub Konecný
- Joel A. Tropp
- Francis R. Bach
- Cameron Musco
- Christopher Musco
- Dmitry Babichev
- Chandrashekar Lakshminarayanan
Citations in the corpus
- Federated Learning: Strategies for Improving Communication Efficiency (2016, methodology): “Such sketching methods have application in many domains [20].”
- Scalable and Differentially Private Distributed Aggregation in the Shuffled Model (2019, background): “for combining data from many sources in order to analyze it. However, research in the area of data stream algorithms has uncovered many non-trivial algorithms that are small linear sketches, see e.g. [8, 16]. Linear sketches over the integers (or over a finite field) can be implemented using secure ag”
- Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, background): “These splits correspond to sev eral “sketches” of the matrixK [9], adapted to subsampling of K, but other sketches could be considered.”
- Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “then encodes the update in a (lossy) compressed form before sending to the server. The server decodes the updates before doing the aggregation. Such sketching methods have application in many domains [184]. This technique corresponds to the general focus of previous sections of this chapter. We prop”
- Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1 (2019, methodology): “In our communicationefficient method, we propose that the matrix is approximated via sketching [41], using quantities that are already computed, i.”
- Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In numerical linear algebra, sketching is one of the most popular techniques used for the evaluation of an approximate solution of large dimensional linear systems Ax = b where A ∈ Rm×n and b ∈ R [197].”
- An Introduction to Matrix Concentration Inequalities (2015, neutral): “The survey [80] explains how to implement this method in practice, while the two monographs [120, 193] cover more theoretical aspects.”
- Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “Note that B∗ = PA minimizes ‖A − B‖F amongst all matrices B whose columns lie in the column span of Q [45].”
- Dictionary learning for integrative, multimodal, and massively scalable single-cell analysis (2022, neutral): “56,78, this optimization problem is analogous to matrix regression and has a closed-form solution for calculating D X and D Y , where † represents the pseudoinverse of the matrix.”
- A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression (2019, background): “The key idea is the matrix sketching, which finds a smaller matrix which preserves some task-specific information in the original matrix and does the computation on the smaller matrix (Drineas and Mahoney 2016; Mahoney 2011; Woodruff 2014).”
- Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, methodology): “(Woodruff, 2014) Table 9.”
- Continual Learning via Online Leverage Score Sampling (2019, methodology): “Here we adopt a cost effective simple randomization technique - leverage score sampling, which has been used extensively in solving large scale linear least squares and low rank approximation problems [2, 5, 37].”
- Low rank approximation with entrywise l1-norm error (2017, background): “, [90] for a survey), we could choose a random matrix S and solve minV ‖SU ∗V − SA‖1 = minV ∑d i=1 ‖ (SU ∗)Vi − SAi ‖1.”