{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T18:16:13Z","timestamp":1781288173955,"version":"3.54.1"},"reference-count":126,"publisher":"Emerald","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,10,29]]},"abstract":"<jats:p>This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the expensive computation can then be performed on the smaller matrix, thereby accelerating the solution for the original problem. In this survey we consider least squares as well as robust regression problems, low rank approximation, and graph sparsification. We also discuss a number of variants of these problems. Finally, we discuss the limitations of sketching methods.<\/jats:p>","DOI":"10.1561\/0400000060","type":"journal-article","created":{"date-parts":[[2014,10,29]],"date-time":"2014-10-29T12:17:00Z","timestamp":1414585020000},"page":"1-157","source":"Crossref","is-referenced-by-count":439,"title":["Sketching as a Tool for Numerical Linear Algebra"],"prefix":"10.1108","volume":"10","author":[{"given":"David P.","family":"Woodruff","sequence":"first","affiliation":[{"name":"IBM Research Almaden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2014,10,29]]},"reference":[{"issue":"4","key":"2026040314065390900_ref001","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","article-title":"Database-friendly random projections: Johnson- lindenstrauss with binary coins","volume":"66","author":"Achlioptas","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314065390900_ref002","doi-asserted-by":"crossref","DOI":"10.1145\/1132516.1132597","article-title":"Approximate nearest neighbors and the fast johnson-lindenstrauss transform","author":"Ailon","year":"2006","journal-title":"ACM Symposium on Theory of Computing (STOC)"},{"key":"2026040314065390900_ref003","article-title":"Fast dimension reduction using rademacher series on dual bch codes","author":"Ailon","year":"2008","journal-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)"},{"key":"2026040314065390900_ref004","author":"Andoni","year":"2012"},{"key":"2026040314065390900_ref005","first-page":"363","article-title":"Streaming algorithms via precision sampling","author":"AlexandrAlexandr","year":"2011","journal-title":"FOCS"},{"key":"2026040314065390900_ref006","first-page":"272279","article-title":"A fast random sampling algorithm for sparsifying matrices","author":"SanjeevSanjeev","year":"2006","journal-title":"APPROX-RANDOM"},{"key":"2026040314065390900_ref007","article-title":"PhD thesis, University of Lw\u00f4w, Lw\u00f4w, Poland","author":"Auerbach","year":"1930","journal-title":"On the Area of Convex Curves with Conjugate Diameters"},{"issue":"3","key":"2026040314065390900_ref008","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1137\/090767911","article-title":"Blendenpik: Supercharging lapack\u2019s least-squares solver","volume":"32","author":"HaimHaim","year":"2010","journal-title":"SIAM J. Scientific Computing"},{"key":"2026040314065390900_ref009","article-title":"Subspace embeddings for the polynomial kernel","author":"Haim","year":"2014","journal-title":"NIPS"},{"key":"2026040314065390900_ref010","first-page":"29943002","article-title":"Woodruff. Sketching structured matrices for faster nonlinear regression","author":"HaimHaim","year":"2013","journal-title":"NIPS"},{"issue":"1","key":"2026040314065390900_ref011","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.jcss.2007.04.016","article-title":"Online linear optimization and adaptive routing","volume":"74","author":"Awerbuch","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314065390900_ref012","article-title":"Limit of the smallest eigenvalue of a large dimensional sample covariance matrix","author":"Bai","journal-title":"The Annals of Probability 21"},{"key":"2026040314065390900_ref013","article-title":"Woodruff. Fast and communication efficient algorithms for distributd pca","author":"Maria-FlorinaMaria-Florina","year":"2014","journal-title":"NIPS"},{"key":"2026040314065390900_ref014","first-page":"255","volume-title":"Proceedings of the 41st annual ACM symposium on Theory of computing","author":"Batson","year":""},{"issue":"2","key":"2026040314065390900_ref015","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1145\/1067967.1067972","article-title":"Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices","volume":"31","author":"Berry","year":"2005","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"key":"2026040314065390900_ref016","author":"Blei"},{"key":"2026040314065390900_ref017","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02392835","article-title":"Approximation of zonoids by zonotopes","volume":"162","author":"Bourgain","year":"1989","journal-title":"Acta Math"},{"key":"2026040314065390900_ref018","article-title":"Toward a unified theory of sparse dimensionality reduction in euclidean space","author":"Bourgain","journal-title":"CoRR"},{"key":"2026040314065390900_ref019","article-title":"Near optimal column based matrix reconstruction","author":"ChristosChristos","year":"2013","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"2026040314065390900_ref020","first-page":"968","article-title":"An improved approximation algorithm for the column subset selection problem","author":"Christos","year":"2009","journal-title":"Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms (SODA)"},{"key":"2026040314065390900_ref021","first-page":"353","article-title":"Woodruff. Optimal cur matrix decompositions","author":"Boutsidis","year":"2014","journal-title":"STOC"},{"key":"2026040314065390900_ref022","author":"Brooks","year":"2009","journal-title":"The \u00a3 1 -norm best-fit hyperplane problem. Technical report, Optimization Online"},{"key":"2026040314065390900_ref023","author":"Brooks","year":"2010","journal-title":"A pure \u00a3 1-norm principal component analysis. Technical report, Optimization Online"},{"issue":"1","key":"2026040314065390900_ref024","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","article-title":"Finding frequent items in data streams","volume":"312","author":"MosesMoses","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"2026040314065390900_ref025","article-title":"Subgradient and sampling algorithms for \u00a3 1 regression","author":"Clarkson","year":"2005","journal-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314065390900_ref026","first-page":"466","article-title":"Woodruff. The fast cauchy transform and faster robust linear regression","author":"Clarkson","year":"2013","journal-title":"SODA"},{"key":"2026040314065390900_ref027","article-title":"Low rank approximation and regression in input sparsity time","author":"Clarkson","year":"2013","journal-title":"In STOC"},{"key":"2026040314065390900_ref028","doi-asserted-by":"crossref","DOI":"10.1145\/1536414.1536445","article-title":"Numerical linear algebra in the streaming model","author":"Clarkson","year":"2009","journal-title":"Proceedings of the 41st annual ACM symposium on Theory of computing (STOC)"},{"key":"2026040314065390900_ref029","article-title":"Dimensionality reduction for k-means clustering and low rank approximation","author":"MichaelMichael","year":"2014","journal-title":"Arxiv preprint arXiv:1410.6801"},{"key":"2026040314065390900_ref030","article-title":"Woodruff. Optimal approximate matrix product in terms of stable rank","author":"MichaelMichael","year":"2014","journal-title":"Manuscript"},{"key":"2026040314065390900_ref031","article-title":"Uniform sampling for matrix approximation","author":"Cohen","year":"2014","journal-title":"Arxiv preprint arXiv:1408.5099"},{"issue":"5","key":"2026040314065390900_ref032","doi-asserted-by":"crossref","first-page":"2060","DOI":"10.1137\/070696507","article-title":"Mahoney. Sampling algorithms and coresets for \u00a3p regression","volume":"38","author":"AnirbanAnirban","year":"2009","journal-title":"SIAM J. Comput."},{"key":"2026040314065390900_ref033","first-page":"341","article-title":"A sparse johnson: Lindenstrauss transform","author":"AnirbanAnirban","year":"2010","journal-title":"STOC"},{"key":"2026040314065390900_ref034","first-page":"641","volume-title":"Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"Deshpande","year":""},{"issue":"12","key":"2026040314065390900_ref035","first-page":"225","article-title":"Matrix approximation and projective clustering via volume sampling","volume":"2","author":"AmitAmit","year":"2006","journal-title":"Theory of Computing"},{"key":"2026040314065390900_ref036","doi-asserted-by":"crossref","DOI":"10.1137\/0149053","article-title":"Uncertainty principles and signal recovery","author":"Donoho","year":"1989","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"2026040314065390900_ref037","first-page":"223","article-title":"Pass efficient algorithms for approximating large matrices","author":"Drineas","year":"2003","journal-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"1","key":"2026040314065390900_ref038","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/S0097539704442702","article-title":"Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition","volume":"36","author":"Drineas","year":"2006","journal-title":"SIAM Journal of Computing"},{"key":"2026040314065390900_ref039","first-page":"316","article-title":"Subspace sampling and relative-error matrix approximation: Column-based methods","author":"Drineas","year":"2006","journal-title":"APPROX-RANDOM"},{"key":"2026040314065390900_ref040","article-title":"Subspace sampling and relative-error matrix approximation: Column-row-based methods","author":"Drineas","journal-title":"Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings"},{"issue":"2","key":"2026040314065390900_ref041","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1137\/07070471X","article-title":"Relative-error cur matrix decompositions","volume":"30","author":"Drineas","year":"2008","journal-title":"SIAM Journal Matrix Analysis and Applications"},{"key":"2026040314065390900_ref042","first-page":"11271136","article-title":"Sampling algorithms for \u00a32 regression and applications","author":"Drineas","year":"2006","journal-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314065390900_ref043","author":"Drineas","year":"2007","journal-title":"Faster least squares approximation, Technical Report, arXiv:0710.1435"},{"key":"2026040314065390900_ref044","first-page":"3475","article-title":"Fast approximation of matrix coherence and statistical leverage","volume":"13","author":"PetrosPetros","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"2026040314065390900_ref045","first-page":"316","article-title":"Subspace sampling and relative-error matrix approximation: Column-based methods","author":"Petros","year":"2006","journal-title":"APPROX-RANDOM"},{"key":"2026040314065390900_ref046","first-page":"304","article-title":"Subspace sampling and relative-error matrix approximation: Column-row-based methods","author":"Petros","year":"2006","journal-title":"ESA"},{"issue":"2","key":"2026040314065390900_ref047","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20089","article-title":"Spectral techniques applied to sparse random graphs","volume":"27","author":"Feige","year":"2005","journal-title":"Random Struct. Algorithms"},{"key":"2026040314065390900_ref048","article-title":"A unified framework for approximating and clustering data","author":"Feldman","year":"2011","journal-title":"Proc. 41th Annu. ACM Symp. on Theory of Computing (STOC), to appear"},{"key":"2026040314065390900_ref049","first-page":"630","article-title":"Woodruff. Coresets and sketches for high dimensional subspace approximation problems","author":"DanDan","year":"2010","journal-title":"SODA"},{"key":"2026040314065390900_ref050","article-title":"Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering","author":"DanDan","year":"2013","journal-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314065390900_ref051","first-page":"475","article-title":"Strauss. Approximate sparse recovery: optimizing time and measurements","author":"Gilbert","year":"2010","journal-title":"STOC"},{"key":"2026040314065390900_ref052","article-title":"Revisiting the nystrom method for improved large-scale machine learning","author":"Gittens","year":"2013","journal-title":"arXiv preprint arXiv:1303.1849"},{"key":"2026040314065390900_ref053","article-title":"van Loan","author":"Golub"},{"issue":"1-3","key":"2026040314065390900_ref054","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0024-3795(96)00301-1","article-title":"A theory of pseudoskeleton approximations","volume":"261","author":"Goreinov","year":"1997","journal-title":"Linear Algebra and its Applications"},{"issue":"4","key":"2026040314065390900_ref055","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF02358985","article-title":"Pseudoskeleton approximations by matrices of maximal volume","volume":"62","author":"Goreinov","year":"1997","journal-title":"Mathematical Notes"},{"key":"2026040314065390900_ref056","first-page":"76","article-title":"Strong rank revealing Cholesky factorization","volume":"17","author":"Gu","year":"2004","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"2026040314065390900_ref057","author":"Guruswami"},{"issue":"3","key":"2026040314065390900_ref058","doi-asserted-by":"crossref","first-page":"231","DOI":"10.4064\/sm-70-3-231-283","article-title":"The best constants in the khintchine inequality","volume":"70","author":"Haagerup","year":"1981","journal-title":"Studia Mathematica"},{"issue":"2","key":"2026040314065390900_ref059","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1137\/090771806","article-title":"Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions","volume":"53","author":"NathanNathan","year":"2011","journal-title":"SIAM Review"},{"key":"2026040314065390900_ref060","first-page":"121","article-title":"Woodruff. How robust are linear sketches to adaptive inputs","author":"Hardt","year":"2013","journal-title":"STOC"},{"key":"2026040314065390900_ref061","article-title":"Improved bound for rank revealing LU factorizations","author":"Hwang","journal-title":"Linear algebra and its applications"},{"key":"2026040314065390900_ref062","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/276698.276876","article-title":"Approximate nearest neighbors: towards removing the curse of dimensionality","author":"Indyk","year":"1998","journal-title":"Proceedings of the thirtieth annual ACM symposium on Theory of computing"},{"issue":"3","key":"2026040314065390900_ref063","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1145\/1147954.1147955","article-title":"Stable distributions, pseudorandom generators, embeddings, and data stream computation","volume":"53","author":"Indyk","year":"2006","journal-title":"J. ACM"},{"key":"2026040314065390900_ref064","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/1250790.1250881","article-title":"Uncertainty principles, extractors, and explicit embeddings of l2 into l1","author":"Indyk","year":"2007","journal-title":"STOC"},{"key":"2026040314065390900_ref065","article-title":"Suslina","author":"Ingster"},{"key":"2026040314065390900_ref066","author":"Johnson","year":"2003","journal-title":"Very tight embeddings of subspaces of lp, 1 = p &lt; 2, into \u00a3n. Geometric and Functional Analysis, 13(4):845-851"},{"issue":"1","key":"2026040314065390900_ref067","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2559902","article-title":"Sparser johnson-lindenstrauss transforms","volume":"61","author":"Kane","year":"2014","journal-title":"J. ACM"},{"key":"2026040314065390900_ref068","first-page":"1040","article-title":"Woodruff. Principal component analysis and higher correlations for distributed data","author":"RaviRavi","year":"2014","journal-title":"COLT"},{"key":"2026040314065390900_ref069","article-title":"Single pass spectral sparsification in dynamic streams","author":"Michael","journal-title":"CoRR"},{"key":"2026040314065390900_ref070","author":"Ke"},{"key":"2026040314065390900_ref071","first-page":"739","article-title":"Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming","author":"Ke","year":"2005","journal-title":"CVPR (1)"},{"key":"2026040314065390900_ref072","author":"Kushilevitz","year":"1997","journal-title":"Communication Complexity"},{"issue":"6","key":"2026040314065390900_ref073","doi-asserted-by":"crossref","first-page":"2315","DOI":"10.1214\/009117906000000421","article-title":"Estimates of moments and tails of Gaussian chaoses","volume":"34","author":"Latala","year":"2006","journal-title":"Ann. Probab."},{"issue":"5","key":"2026040314065390900_ref074","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1214\/aos\/1015957395","article-title":"Adaptive estimation of a quadratic functional by mo del selection","volume":"28","author":"Laurent","year":"2000","journal-title":"Ann. Statist."},{"key":"2026040314065390900_ref075","article-title":"Algorithms for non-negative matrix factorization","author":"Lee","year":"2001","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026040314065390900_ref076","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/978-3-642-15217-7_13","volume-title":"S\u00e9minaire de Probabilit\u00e9s XLIII","author":"Lehec","year":"2011"},{"key":"2026040314065390900_ref077","doi-asserted-by":"crossref","first-page":"207","DOI":"10.4064\/sm-63-2-207-212","article-title":"Finite dimensional subspaces of lp","volume":"63","author":"Lewis","year":"1978","journal-title":"Studia Math"},{"key":"2026040314065390900_ref078","first-page":"127","article-title":"Iterative row sampling","author":"Mu","year":"2013","journal-title":"FOCS"},{"key":"2026040314065390900_ref079","article-title":"On sketching matrix norms and the top singular vector","author":"Yi","year":"2014","journal-title":"SODA"},{"key":"2026040314065390900_ref080","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-74503-9","author":"Luenberger","year":"2008","journal-title":"Linear and nonlinear programming"},{"key":"2026040314065390900_ref081","article-title":"Row Sampling for Matrix Algorithms via a Non- Commutative Bernstein Bound","author":"Magdon-Ismail","year":"2010","journal-title":"Arxiv preprint arXiv:1008.0587"},{"key":"2026040314065390900_ref082","article-title":"Using a non-commutative bernstein bound to approximate some matrix algorithms in the spectral norm","author":"Magdon-Ismail","journal-title":"CoRR"},{"key":"2026040314065390900_ref083","article-title":"Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication","author":"Magen","year":"2011","journal-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)"},{"issue":"1","key":"2026040314065390900_ref084","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00454-007-1329-4","article-title":"Dimensionality reductions in l2 that preserve volumes and distance to affine spaces","volume":"38","author":"Magen","year":"2007","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"2026040314065390900_ref085","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1561\/2200000035","article-title":"Mahoney. Randomized algorithms for matrices and data","volume":"3","author":"W","year":"2011","journal-title":"Foundations and Trends in Machine Learning"},{"key":"2026040314065390900_ref086","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1073\/pnas.0803205106","article-title":"Cur matrix decompositions for improved data analysis","volume":"106","author":"Mahoney","year":"2009","journal-title":"Proceedings of the National Academy of Sciences (PNAS)"},{"issue":"3","key":"2026040314065390900_ref087","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1073\/pnas.0803205106","article-title":"Cur matrix decompositions for improved data analysis","volume":"106","author":"Mahoney","year":"2009","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2026040314065390900_ref088","first-page":"15","article-title":"Mangasarian. Arbitrary-norm separating plane","volume":"24","author":"L","year":"1997","journal-title":"Operations Research Letters"},{"key":"2026040314065390900_ref089","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","author":"Matousek","year":"2002","journal-title":"Lectures on Discrete Geometry"},{"issue":"1:15","key":"2026040314065390900_ref090","article-title":"A bound on the deviation probability for sums of nonnegative random variables","volume":"4","author":"Maurer","journal-title":"Journal of Inequalities in Pure and Applied Mathematics"},{"key":"2026040314065390900_ref091","article-title":"Mahoney. LSRN: A Parallel Iterative Solver for Strongly Over- or Under-Determined Systems","author":"Meng","journal-title":"ArXiv e-prints"},{"key":"2026040314065390900_ref092","first-page":"91","volume-title":"In STOC","author":"Meng","year":""},{"issue":"1","key":"2026040314065390900_ref093","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/jcss.1998.1577","article-title":"On data structures and asymmetric communication complexity","volume":"57","author":"Miltersen","year":"1998","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314065390900_ref094","author":"P","year":"2003","journal-title":"Minka. A comparison of numerical optimizers for logistic regression. Technical report, Microsoft"},{"issue":"C","key":"2026040314065390900_ref095","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0024-3795(02)00572-4","article-title":"Strong rank revealing LU factorizations","volume":"367","author":"Miranian","year":"2003","journal-title":"Linear Algebra and its Applications"},{"key":"2026040314065390900_ref096","author":"Muthukrishnan","year":"2005","journal-title":"Data streams: algorithms and applications"},{"key":"2026040314065390900_ref097","article-title":"Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings","author":"Nelson","year":"2013","journal-title":"In FOCS"},{"key":"2026040314065390900_ref098","first-page":"883","article-title":"Nguy\u00ean. Lower bounds for oblivious subspace embeddings","author":"Nelson","year":"2014","journal-title":"ICALP (1)"},{"key":"2026040314065390900_ref099","first-page":"101","article-title":"Nguyen. Sparsity lower bounds for dimensionality reducing maps","author":"Nelson","year":"2013","journal-title":"STOC"},{"key":"2026040314065390900_ref100","author":"Nguyen","year":"2013","journal-title":"Personal communication"},{"issue":"1-3","key":"2026040314065390900_ref101","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0024-3795(00)00120-8","article-title":"On the existence and computation of rank-revealing LU factorizations","volume":"316","author":"Pan","year":"2000","journal-title":"Linear Algebra and its Applications"},{"key":"2026040314065390900_ref102","author":"Regev","year":"2014","journal-title":"Personal communication"},{"issue":"36","key":"2026040314065390900_ref103","doi-asserted-by":"crossref","first-page":"13212","DOI":"10.1073\/pnas.0804869105","article-title":"A fast randomized algorithm for overdetermined linear least-squares regression","volume":"105","author":"Rokhlin","year":"2008","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2026040314065390900_ref104","article-title":"Non-asymptotic theory of random matrices: extreme singular values","author":"Rudelson","journal-title":"CoRR"},{"key":"2026040314065390900_ref105","article-title":"Improved approximation algorithms for large matrices via random projections","author":"Sarl\u00f4s","year":"2006","journal-title":"IEEE Symposium on Foundations of Computer Science (FOCS)"},{"key":"2026040314065390900_ref106","first-page":"159","article-title":"More on embedding subspaces of lp into","volume":"61","author":"Schechtman","year":"1987","journal-title":"Composition Math"},{"key":"2026040314065390900_ref107","first-page":"532","article-title":"Efficient subspace approximation algorithms","author":"Shyamalkumar","year":"2007","journal-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms"},{"key":"2026040314065390900_ref108","first-page":"755","article-title":"Woodruff. Subspace embeddings for the l1-norm with applications","author":"Sohler","year":"2011","journal-title":"STOC"},{"key":"2026040314065390900_ref109","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/1007352.1007372","article-title":"Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems","author":"Spielman","year":"2004","journal-title":"STOC"},{"issue":"4","key":"2026040314065390900_ref110","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1137\/08074489X","article-title":"Spectral sparsification of graphs","volume":"40","author":"Spielman","year":"2011","journal-title":"SIAM J. Comput."},{"key":"2026040314065390900_ref111","article-title":"Graph sparsifications by effective resistances","author":"Srivastava","year":"2008","journal-title":"Proceedings of the 40th ACM Symposium on Theory of Computing (STOC)"},{"key":"2026040314065390900_ref112","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s002110050451","article-title":"Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix","volume":"83","author":"Stewart","year":"1999","journal-title":"Numerische Mathematik"},{"issue":"2","key":"2026040314065390900_ref113","first-page":"363","article-title":"Embedding subspaces of 11 into \u00a3\"","volume":"108","author":"Talagrand","year":"1990","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2026040314065390900_ref114","author":"Tang","year":"2004","journal-title":"Fast Transforms Based on Structured Matrices With Applications to The Fast Multipole Method"},{"issue":"2","key":"2026040314065390900_ref115","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/100800774","article-title":"Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation","volume":"41","author":"Thorup","year":"2012","journal-title":"SIAM J. Comput."},{"key":"2026040314065390900_ref116","article-title":"Improved analysis of the subsampled randomized hadamard transform","author":"Tropp","year":"2011","journal-title":"Adv. Adapt. Data Anal., special issue, \u201cSparse Representation of Data and Images"},{"key":"2026040314065390900_ref117","article-title":"Tsybakov","author":"B"},{"issue":"1","key":"2026040314065390900_ref118","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02575706","article-title":"Mosaic-skeleton approximations","volume":"33","author":"Tyrtyshnikov","year":"1996","journal-title":"Calcolo"},{"issue":"4","key":"2026040314065390900_ref119","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s006070070031","article-title":"Incomplete cross approximation in the mosaic-skeleton method","volume":"64","author":"Tyrtyshnikov","year":"2000","journal-title":"Computing"},{"key":"2026040314065390900_ref120","first-page":"486","article-title":"On the sensitivity of shape fitting problems","author":"Varadarajan","year":"2012","journal-title":"FSTTCS"},{"key":"2026040314065390900_ref121","doi-asserted-by":"crossref","article-title":"Introduction to the non-asymptotic analysis of random matrices","author":"Vershynin","DOI":"10.1017\/CBO9780511794308.006"},{"key":"2026040314065390900_ref122","article-title":"Improving cur matrix decomposition and the nystrom approximation via adaptive sampling","author":"Wang","year":"2013","journal-title":"Journal of Machine Learning Research"},{"key":"2026040314065390900_ref123","article-title":"Woodruff. Low rank approximation lower bounds in rowupdate streams","author":"P","year":"2014","journal-title":"NIPS"},{"key":"2026040314065390900_ref124","article-title":"Subspace embeddings and \u00a3p- regression using exponential random variables","author":"Woodruff","year":"2013","journal-title":"CoRR"},{"key":"2026040314065390900_ref125","article-title":"Faster ridge regression via the subsampled randomized hadamard transform","author":"Lu","year":"2013","journal-title":"Proceedings of the Neural Information Processing Systems (NIPS) Conference"},{"key":"2026040314065390900_ref126","first-page":"846","article-title":"A matrix hyperbolic cosine algorithm and applications","author":"Zouzias","year":"2012","journal-title":"ICALP (1)"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/10\/1-2\/1\/11485699\/0400000060en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/10\/1-2\/1\/11485699\/0400000060en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:16Z","timestamp":1777489276000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/10\/1-2\/1\/1332206\/Sketching-as-a-Tool-for-Numerical-Linear-Algebra"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,29]]},"references-count":126,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,10,29]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000060","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,29]]}}}