The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Computational Advertising: Techniques for Targeting Relevant Ads
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · Cited by 7,952
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Linear and nonlinear programming.
(1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90092-3 · Cited by 4,805
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Seung, D., & Lee, L.-W. (2001) · Cited by 4,753
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Linear and Nonlinear Programming
Luenberger, D. G., & Ye, Y. (2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-74503-9 · Cited by 2,804
Introduction to Nonparametric Estimation
Tsybakov, A. B. (2009) · Springer Series in Statistics · doi:10.1007/b13794 · Cited by 2,486
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,433
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Uncertainty Principles and Signal Recovery
Donoho, D. L., & Stark, P. B. (1989) · SIAM Journal on Applied Mathematics · doi:10.1137/0149053 · Cited by 1,054
Adaptive estimation of a quadratic functional by model selection
Laurent, B., & Massart, P. (2000) · The Annals of Statistics · doi:10.1214/aos/1015957395 · Cited by 995
CUR matrix decompositions for improved data analysis
Mahoney, M. W., & Drineas, P. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0803205106 · Cited by 773
Spielman, D. A., & Teng, S.-H. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007372 · Cited by 769
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Har-Peled, S., Indyk, P., & Motwani, R. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a014 · Cited by 693
Improved Approximation Algorithms for Large Matrices via Random Projections
Sarlos, T. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.37 · Cited by 646
Ke, Q., & Kanade, T. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.309 · Cited by 578
Limit of the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix
Bai, Z. D., & Yin, Y. Q. (1993) · The Annals of Probability · doi:10.1214/aop/1176989118 · Cited by 519
A theory of pseudoskeleton approximations
Goreinov, S. A., Tyrtyshnikov, E. E., & Замарашкин, Н. Л. (1997) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(96)00301-1 · Cited by 498
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 479
Relative-Error $CUR$ Matrix Decompositions
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/07070471x · Cited by 461
Randomized Algorithms for Matrices and Data
MAHONEY, M. (2012) · Chapman & Hall/CRC Data Mining and Knowledge Discovery Series · doi:10.1201/b11822-37 · Cited by 409
Spectral Sparsification of Graphs
Spielman, D. A., & Teng, S.-H. (2011) · SIAM Journal on Computing · doi:10.1137/08074489x · Cited by 409
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Indyk, P. (2006) · Journal of the ACM · doi:10.1145/1147954.1147955 · Cited by 402
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132597 · Cited by 379
A unified framework for approximating and clustering data
Feldman, D., & Langberg, M. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993712 · Cited by 368
The best constants in the Khintchine inequality
Haagerup, U. (1981) · Studia Mathematica · doi:10.4064/sm-70-3-231-283 · Cited by 338
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442702 · Cited by 310
Numerical linear algebra in the streaming model
Clarkson, K. L., & Woodruff, D. P. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536445 · Cited by 301
Self-citationNon-asymptotic Theory of Random Matrices: Extreme Singular Values
Rudelson, M., & Vershynin, R. (2011) · Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) · doi:10.1142/9789814324359_0111 · Cited by 296
An improved approximation algorithm for the column subset selection problem
Boutsidis, C., Mahoney, M. W., & Petros Drineas, B. (2009) · doi:10.5555/1496770.1496875 · Cited by 286
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Cohen, M. B., Elder, S., Musco, C., Musco, C., & Persu, M. (2015) · Proceedings of the forty-seventh annual ACM symposium on Theory of Computing · doi:10.1145/2746539.2746569 · Cited by 276
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, B., Magdon‐Ismail, M., Mahoney, M. W., & Woodruff, D. P. (2012) · Journal of Machine Learning Research · doi:10.5555/2503308.2503352 · Cited by 268
Self-citationIncomplete Cross Approximation in the Mosaic-Skeleton Method
Tyrtyshnikov, E. (2000) · Computing · doi:10.1007/s006070070031 · Cited by 249
A comparison of numerical optimizers for logistic regression
Minka, T. P. (2004) · Cited by 235
Randomized Algorithms for Matrices and Data
Mahoney, M. W. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000035 · Cited by 232
Spectral techniques applied to sparse random graphs
Feige, U., & Ofek, E. (2005) · Random Structures & Algorithms · doi:10.1002/rsa.20089 · Cited by 221
Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
Ailon, N., & Liberty, E. (2009) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9110-x · Cited by 194
A fast randomized algorithm for overdetermined linear least-squares regression
Rokhlin, V., & Tygert, M. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0804869105 · Cited by 183
Online linear optimization and adaptive routing
Awerbuch, B., & Kleinberg, R. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.04.016 · Cited by 177
Arbitrary-norm separating plane
Mangasarian, O. L. (1999) · Operations Research Letters · doi:10.1016/s0167-6377(98)00049-2 · Cited by 172
Near-Optimal Column-Based Matrix Reconstruction
Boutsidis, C., Drineas, P., & Magdon-Ismail, M. (2014) · SIAM Journal on Computing · doi:10.1137/12086755x · Cited by 169
On the existence and computation of rank-revealing LU factorizations
Pan, C.-T. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00120-8 · Cited by 156
Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive SamplingPreprint
WangShusen, & ZhangZhihua (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.4207 · Cited by 152
Dasgupta, A., Kumar, R., & Sarlós, T. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806737 · Cited by 143
Sampling Algorithms and Coresets for $\ell_p$ Regression
Dasgupta, A., Petros Drineas, B., Harb, B., Kumar, R., & Mahoney, M. W. (2009) · SIAM Journal on Computing · doi:10.1137/070696507 · Cited by 112
A pure L1 -norm principal component analysis
Brooks, J. P., Dulá, J. H., & Boone, E. L. (2012) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2012.11.007 · Cited by 103
Faster Ridge Regression via the Subsampled Randomized Hadamard Transform
Lu, Y., Dhillon, P. S., Foster, D. P., & Ungar, L. (2013) · ScholarlyCommons (University of Pennsylvania) · Cited by 91
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
Petros Drineas, B., Mahoney, M. W., & Muthukrishnan, S. (2006) · Lecture notes in computer science · doi:10.1007/11830924_30 · Cited by 90
A Fast Random Sampling Algorithm for Sparsifying Matrices
Arora, S., Hazan, E., & Kale, S. (2006) · Lecture notes in computer science · doi:10.1007/11830924_26 · Cited by 84
Thorup, M., & Zhang⋆, Y. (2012) · SIAM Journal on Computing · doi:10.1137/100800774 · Cited by 81
Coresets and sketches for high dimensional subspace approximation problems
Feldman, D., Monemizadeh, M., Sohler, C., & Woodruff, D. P. (2010) · doi:10.5555/1873601.1873654 · Cited by 69
Self-citationSubspace embeddings for the L 1 -norm with applications
Sohler, C., & Woodruff, D. P. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993736 · Cited by 62
Self-citationSparsity lower bounds for dimensionality reducing maps
Nelson, J., & NguyÅn, H. L. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488622 · Cited by 51
A bound on the deviation probability for sums of non-negative random variables.
Maurer, A. (2003) · Cited by 47
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Bourgain, J., Dirksen, S., & Nelson, J. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746541 · Cited by 25
Low Rank Approximation Lower Bounds in Row-Update Streams
Woodruff, D. P. (2014) · neural information processing systems · Cited by 22
Self-citation
Cited by
Dictionary learning for integrative, multimodal and scalable single-cell analysis
Hao, Y., Stuart, T., Kowalski, M. H., Choudhary, S., Hoffman, P., Hartman, A., Srivastava, A., Molla, G., Madad, S., Fernandez-Granda, C., et al. (2024) · Nature Biotechnology · doi:10.1038/s41587-023-01767-y · Cited by 5,631
Federated Learning: Strategies for Improving Communication Efficiency
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., & Bacon, D. (2016) · arXiv · doi:10.48550/arxiv.1610.05492 · Cited by 3,766
Rodríguez-Barroso, N., Jiménez-López, D., Luzón, M. V., Herrera, F., & Martínez-Cámara, E. (2023) · Information Fusion · doi:10.1016/j.inffus.2022.09.011 · Cited by 296
Tang, E. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.060503 · Cited by 140
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model
Ghazi, B., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1906.08320 · Cited by 62
Metadata
- Authors
- Woodruff, D. P.
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2014
- Volume
- 10
- Issue
- 1-2
- Pages
- 1-157
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W2157988812
- Cited by
- 866
- References
- 61
- FWCI
- 58.61
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
