# Sketching as a Tool for Numerical Linear Algebra

@article{Woodruff2014SketchingAA,
title={Sketching as a Tool for Numerical Linear Algebra},
author={David P. Woodruff},
journal={Found. Trends Theor. Comput. Sci.},
year={2014},
volume={10},
pages={1-157}
}
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… Expand
690 Citations

#### Paper Mentions

An Empirical Evaluation of Sketching for Numerical Linear Algebra
• Mathematics, Computer Science
• KDD
• 2018
This work investigates least squares regression, iteratively reweighted least squares, logistic regression, robust regression with Huber and Bisquare loss functions, leverage score computation, Frobenius norm low rank approximation, and entrywise $\ell_1$-low rank approximation. Expand
Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Computer Science, Mathematics
• SIAM J. Matrix Anal. Appl.
• 2017
A suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix that can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximation with a user-specified rank. Expand
A Very Sketchy Talk
We give an overview of dimensionality reduction methods, or sketching, for a number of problems in optimization, first surveying work using these methods for classical problems, which gives nearExpand
Deterministic matrix sketches for low-rank compression of high-dimensional simulation data
• Computer Science, Mathematics
• ArXiv
• 2021
Deterministic matrix sketches which generate coarse representations – compatible with the corresponding PDE solve – are considered in the computation of the singular value decomposition and matrix interpolative decomposition. Expand
Tighter bound of Sketched Generalized Matrix Approximation
• Mathematics, Computer Science
• ArXiv
• 2016
This paper finds new sketching techniques to reduce the size of the original data matrix to develop new matrix approximation algorithms, and derives a much tighter bound for the approximation than previous works. Expand
Iterative Hessian Sketch in Input Sparsity Time
• Computer Science, Mathematics
• ArXiv
• 2019
This paper adopts "Iterative Hessian Sketching" (IHS) and shows that the fast CountSketch and sparse Johnson-Lindenstrauss Transforms yield state-of-the-art accuracy guarantees under IHS, while drastically improving the time cost. Expand
Sketching for Geometric Problems
In this invited talk at the European Symposium on Algorithms (ESA), 2017, I will discuss a tool called sketching, which is a form of data dimensionality reduction, and its applications to severalExpand
Spectral estimation from simulations via sketching
• Computer Science, Mathematics
• ArXiv
• 2020
This work shows that sketching can be used to compress simulation data and still accurately estimate time autocorrelation and power spectral density, for a given compression ratio, the accuracy is much higher than using previously known methods. Expand
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
• Computer Science
• ArXiv
• 2021
This work proposes a new transform and shows that the claimed results from the previous version can be obtained using the new transform, and gives the first optimal algorithms, for the current matrix multiplication exponent, for constant factor regression and low rank approximation. Expand
Sparse Graph Based Sketching for Fast Numerical Linear Algebra
• Computer Science, Mathematics
• ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 2021
This paper explores two popular classes of sparse graphs, namely, expander graphs and magical graphs, and discusses the construction of sparse sketching matrices with reduced randomness using expanders based on error-correcting codes. Expand
{"ft_lang_label":"__label__en","ft_lang_prob":0.833305,"math_prob":0.8724719,"size":8400,"snap":"2021-31-2021-39","text_gpt3_token_len":1728,"char_repetition_ratio":0.15209624,"word_repetition_ratio":0.02138158,"special_character_ratio":0.18952382,"punctuation_ratio":0.078341015,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9902271,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-19T02:40:29Z\",\"WARC-Record-ID\":\"<urn:uuid:8375dfb5-3d82-4474-ab84-e1050bb3cc22>\",\"Content-Length\":\"425992\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:001fb347-bf80-4d1a-a5b7-c1693c3b4fa7>\",\"WARC-Concurrent-To\":\"<urn:uuid:ac33795f-8a32-46a6-bfab-943f57de7d36>\",\"WARC-IP-Address\":\"13.32.204.109\",\"WARC-Target-URI\":\"https://www.semanticscholar.org/paper/Sketching-as-a-Tool-for-Numerical-Linear-Algebra-Woodruff/e7da1f3c909b499c052b28a4eac90270fb933840\",\"WARC-Payload-Digest\":\"sha1:CEKIZVRUNKNF2ZI3Z7KEICZ2AHFB3D4T\",\"WARC-Block-Digest\":\"sha1:QAKVU4DRI7IHJH6GSIYGMDRQG6INYEDF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780056656.6_warc_CC-MAIN-20210919005057-20210919035057-00536.warc.gz\"}"}