The DOI matches its Crossref record; 149 of the 149 references it cites were found in a registry or an index.
Randomized Algorithms for Matrices and Data
Abstract
Randomized algorithms for very large matrix problems have received a great deal of attention in recent years.Much of this work was motivated by problems in large-scale data analysis, largely since matrices are popular structures with which to model data drawn from a wide range of application domains, and this work was performed by individuals from many different research communities.While the most obvious benefit of randomization is that it can lead to faster algorithms, either in worst-case asymptotic theory and/or numerical implementation, there are numerous other benefits that are at least as important.For example, the use of randomization can lead to simpler algorithms that are easier to analyze or reason about when applied in counterintuitive settings; it can lead to algorithms with more interpretable output, which is of interest in applications where analyst time rather than just computational time is of interest; it can lead implicitly to regularization and more robust output; and randomized algorithms can often be organized to exploit modern computational architectures better than classical numerical methods.This monograph will provide a detailed overview of recent work on the theory of randomized matrix algorithms as well as the application of those ideas to the solution of practical problems in large-scale data analysis.Throughout this review, an emphasis will be placed on a few simple core ideas that underlie not only recent theoretical advances but also the usefulness of these tools in large-scale data applications.Crucial in this context is the connection with the concept of statistical leverage.This concept has long been used in statistical regression diagnostics to identify outliers; and it has recently proved crucial in the development of improved worst-case matrix algorithms that are also amenable to high-quality numerical implementation and that are useful to domain scientists.This connection arises naturally when one explicitly decouples the effect of randomization in these matrix algorithms from the underlying linear algebraic structure.This decoupling also permits much finer control in the application of randomization, as well as the easier exploitation of domain knowledge.Most of the review will focus on random sampling algorithms and random projection algorithms for versions of the linear least-squares problem and the low-rank matrix approximation problem.These two problems are fundamental in theory and ubiquitous in practice.Randomized methods solve these problems by constructing and operating on a randomized sketch of the input matrix Afor random sampling methods, the sketch consists of a small number of carefully-sampled and rescaled columns/rows of A, while for random projection methods, the sketch consists of a small number of linear combinations of the columns/rows of A. Depending on the specifics of the situation, when compared with the best previously-existing deterministic algorithms, the resulting randomized algorithms have worst-case running time that is asymptotically faster; their numerical implementations are faster in terms of clock-time; or they can be implemented in parallel computing environments where existing numerical algorithms fail to run at all.Numerous examples illustrating these observations will be described in detail.
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
Equation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Roweis, S. T., & Saul, L. K. (2000) · Science · doi:10.1126/science.290.5500.2323 · Cited by 14,965
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
Indexing by latent semantic analysis
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9 · Cited by 12,751
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673
Genome-wide association study of 14,000 cases of seven common diseases and 3,000 shared controls
The Wellcome Trust Case Control Consortium, Management Committee, Burton, P. R., Clayton, D. G., Cardon, L. R., Craddock, N., Deloukas, P., Duncanson, A., Kwiatkowski, D. P., McCarthy, M. I., et al. (2007) · Nature · doi:10.1038/nature05911 · Cited by 9,442
Population Structure and Eigenanalysis
Patterson, N., Price, A. L., & Reich, D. (2006) · PLoS Genetics · doi:10.1371/journal.pgen.0020190 · Cited by 5,280
Power and Centrality: A Family of Measures
Bonacich, P. (1987) · American Journal of Sociology · doi:10.1086/228631 · Cited by 5,165
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
A fast algorithm for particle simulations
Greengard, L., & Rokhlin, V (1987) · Journal of Computational Physics · doi:10.1016/0021-9991(87)90140-9 · Cited by 4,868
An Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
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
(1996) · Choice Reviews Online · doi:10.5860/choice.34-2458 · Cited by 3,732
Regression Analysis by Example.
Kmenta, J., Chatterjee, S., & Price, B. (1980) · Journal of the American Statistical Association · doi:10.2307/2287213 · Cited by 3,198
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
A measure of betweenness centrality based on random walks
Newman, M. E. J. (2005) · Social Networks · doi:10.1016/j.socnet.2004.11.009 · Cited by 2,461
Sparsity and incoherence in compressive sampling
Candès, E., & Romberg, J. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,075
A Genome-Wide Transcriptional Analysis of the Mitotic Cell Cycle
Cho, R. J., Campbell, M. J., Winzeler, E. A., Steinmetz, L., Conway, A., Wodicka, L., Wolfsberg, T. G., Gabrielian, A. E., Landsman, D., Lockhart, D. J., et al. (1998) · Molecular Cell · doi:10.1016/s1097-2765(00)80114-8 · Cited by 2,046
Singular value decomposition for genome-wide expression data processing and modeling
Alter, O., Brown, P. O., & Botstein, D. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.97.18.10101 · Cited by 1,971
On the distribution of the largest eigenvalue in principal components analysis
Johnstone, I. M. (2001) · The Annals of Statistics · doi:10.1214/aos/1009210544 · Cited by 1,949
On the evolution of random graphs
Erdös, P., & Rényi, A. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.38 · Cited by 1,757
Using the Nyström Method to Speed Up Kernel Machines
Williams, C. K. I., & Seeger, M. (2000) · Cited by 1,646
Mining knowledge-sharing sites for viral marketing
Richardson, M., & Domingos, P. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775057 · Cited by 1,612
Genes mirror geography within Europe
Novembre, J., Johnson, T., Bryc, K., Kutalik, Z., Boyko, A. R., Auton, A., Indap, A., King, K. S., Bergmann, S., Nelson, M. R., et al. (2008) · Nature · doi:10.1038/nature07331 · Cited by 1,479
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
Random projection in dimensionality reduction: applications to image and text data
Bingham, E., & Mannila, H. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502546 · Cited by 1,274
Singular Value Decomposition and Principal Component Analysis
Wall, M. E., Rechtsteiner, A., & Rocha, L. M. (2005) · A Practical Approach to Microarray Data Analysis · doi:10.1007/0-306-47815-3_5 · Cited by 1,215
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
The Hat Matrix in Regression and ANOVA
Hoaglin, D. C., & Welsch, R. E. (1978) · The American Statistician · doi:10.1080/00031305.1978.10479237 · Cited by 912
A new version of the Fast Multipole Method for the Laplace equation in three dimensions
Greengard, L., & Rokhlin, V. (1997) · Acta Numerica · doi:10.1017/s0962492900002725 · Cited by 879
Influential Observations, High Leverage Points, and Outliers in Linear Regression
Chatterjee, S., & Hadi, A. S. (1986) · Statistical Science · doi:10.1214/ss/1177013622 · Cited by 826
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning
Petros Drineas, B., & Mahoney, M. W. (2005) · doi:10.5555/1046920.1194916 · Cited by 795
Self-citationAlgorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355993.356000 · Cited by 792
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
Self-citationEfficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
Gu, M., & Eisenstat, S. C. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917055 · Cited by 677
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
Menozzi, P., Piazza, A., & Cavalli-Sforza, L. (1978) · Science · doi:10.1126/science.356262 · Cited by 638
The eigenvalues of random symmetric matrices
Füredi, Z., & Komlós, J. (1981) · Combinatorica · doi:10.1007/bf02579329 · Cited by 633
Graph mining: Laws, generators, and algorithms
Chakrabarti, D., & Faloutsos, C. (2006) · ACM Computing Surveys · doi:10.1145/1132952.1132954 · Cited by 609
Random projection for high dimensional data clustering: a cluster ensemble approach
Fern, X. Z., & Brodley, C. E. (2003) · Cited by 595
Regression Analysis by Example
SRJ, Chatterjee, S., Hadi, A. S., & Price, B. (2000) · Journal of the American Statistical Association · doi:10.2307/2669806 · Cited by 574
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559
Latent Semantic Indexing: A Probabilistic Analysis
Papadimitriou, C. H., Raghavan, P., Tamaki, H., & Vempala, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1711 · Cited by 556
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442696 · Cited by 552
Self-citationRank revealing QR factorizations
Chan, T. F. (1987) · Linear Algebra and its Applications · doi:10.1016/0024-3795(87)90103-0 · Cited by 521
Linear least squares solutions by householder transformations
Businger, P., & Golub, G. H. (1965) · Numerische Mathematik · doi:10.1007/bf01436084 · Cited by 508
Quick Approximation to Matrices and Applications
Frieze, A., & Kannan, R. (1999) · Combinatorica · doi:10.1007/s004930050052 · Cited by 502
Sensitivity Analysis in Linear Regression
Chatterjee, S., & Hadi, A. S. (1988) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316764 · Cited by 502
Fast monte-carlo algorithms for finding low-rank approximations
Frieze, A., Kannan, R., & Vempala, S. (2004) · Journal of the ACM · doi:10.1145/1039488.1039494 · Cited by 500
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
Clustering Large Graphs via the Singular Value Decomposition
Petros Drineas, B., FRIEZE, A. M., Kannan, R., Vempala, S., & Vinay, V. (2004) · Machine Learning · doi:10.1023/b:mach.0000033113.59016.96 · Cited by 487
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442684 · Cited by 487
Self-citationThe 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
Self-citationFaster least squares approximation
Petros Drineas, B., Mahoney, M. W., Muthukrishnan, S., & Sarlós, T. (2010) · Numerische Mathematik · doi:10.1007/s00211-010-0331-6 · Cited by 429
Self-citationA Randomized Algorithm for Principal Component Analysis
Rokhlin, V., Szlam, A., & Tygert, M. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/080736417 · Cited by 422
Sensitivity Analysis in Linear Regression.
Thomas, W., Chatterjee, S., & Hadi, A. S. (1989) · Journal of the American Statistical Association · doi:10.2307/2289957 · Cited by 406
Construction and Arithmetics of H -Matrices
Grasedyck, L., & Hackbusch, W. (2003) · Computing · doi:10.1007/s00607-003-0019-1 · Cited by 402
Dimensionality reduction by random mapping: fast similarity computation for clustering
Kaski, S. (2002) · 1998 IEEE International Joint Conference on Neural Networks Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36227) · doi:10.1109/ijcnn.1998.682302 · Cited by 388
Data mining and machine learning in astronomy
BALL, N. M., & BRUNNER, R. J. (2010) · International Journal of Modern Physics D · doi:10.1142/s0218271810017160 · Cited by 383
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
Random Vectors in the Isotropic Position
Rudelson, M. (1999) · Journal of Functional Analysis · doi:10.1006/jfan.1998.3384 · Cited by 371
Efficient Computing of Regression Diagnostics
Velleman, P. F., & Welsch, R. E. (1981) · The American Statistician · doi:10.1080/00031305.1981.10479362 · Cited by 367
A randomized algorithm for the decomposition of matrices
Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.02.003 · Cited by 352
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442702 · Cited by 310
Self-citationPCA-Correlated SNPs for Structure Identification in Worldwide Human Populations
Paschou, P., Ziv, E., Burchard, E. G., Choudhry, S., Rodriguez-Cintron, W., Mahoney, M. W., & Drineas, P. (2007) · PLoS Genetics · doi:10.1371/journal.pgen.0030160 · Cited by 302
Self-citationNumerical 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
Numerical Methods for Electronic Structure Calculations of Materials
Saad, Y., Chelikowsky, J. R., & Shontz, S. M. (2010) · SIAM Review · doi:10.1137/060651653 · Cited by 301
Improved Nyström low-rank approximation and error analysis
Zhang, K., Tsang, I. W., & Kwok, J. T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390311 · Cited by 299
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
Fast computation of low-rank matrix approximations
Achlioptas, D., & Mcsherry, F. (2007) · Journal of the ACM · doi:10.1145/1219092.1219097 · Cited by 292
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
Self-citationDorogovtsev, S. N., Goltsev, A. V., Mendes, J. F. F., & Samukhin, A. N. (2003) · Physical Review E · doi:10.1103/physreve.68.046109 · Cited by 280
A fast randomized algorithm for the approximation of matrices
Woolfe, F., Liberty, E., Rokhlin, V., & Tygert, M. (2008) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.12.002 · Cited by 280
Spectral Methods for Dimensionality Reduction
Saul, L. K., Weinberger, K. Q., Sha, F., Ham, J., & Lee, D. D. (2006) · Semi-Supervised Learning · doi:10.7551/mitpress/6173.003.0022 · Cited by 272
A Randomized Algorithm for the Approximation of Matrices
Martinsson, P.-G., Rockhlin, V., & Tygert, M. (2006) · doi:10.21236/ada458932 · Cited by 268
Yip, C. W., Connolly, A. J., Vanden Berk, D. E., Ma, Z., Frieman, J. A., SubbaRao, M., Szalay, A. S., Richards, G. T., Hall, P. B., Schneider, D. P., et al. (2004) · The Astronomical Journal · doi:10.1086/425626 · Cited by 267
Reiher, W. (1966) · Biometrische Zeitschrift · doi:10.1002/bimj.19660080314 · Cited by 255
Spectra and eigenvectors of scale-free networks
Goh, K.-I., Kahng, B., & Kim, D. (2001) · Physical Review E · doi:10.1103/physreve.64.051903 · Cited by 236
Clustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction
Zhang, K., & Kwok, J. T. (2010) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2010.2064786 · Cited by 219
Density of states of a sparse random matrix
Rodgers, G. J., & Bray, A. J. (1988) · Physical Review B · doi:10.1103/physrevb.37.3557 · Cited by 215
Talwalkar, A., Kumar, S., & Rowley, H. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587670 · Cited by 207
Spectral Classification of Galaxies: an Orthogonal Approach
Connolly, A. J., Szalay, A. S., Bershady, M. A., Kinney, A. L., & Calzetti, D. (1995) · The Astronomical Journal · doi:10.1086/117587 · Cited by 202
Experiments with random projections for machine learning
Fradkin, D., & Madigan, D. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956812 · Cited by 201
Distributions of Galaxy Spectral Types in the Sloan Digital Sky Survey
Yip, C. W., Connolly, A. J., Szalay, A. S., Budavári, T., SubbaRao, M., Frieman, J. A., Nichol, R. C., Hopkins, A. M., York, D. G., Okamura, S., et al. (2004) · The Astronomical Journal · doi:10.1086/422429 · Cited by 200
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
Adaptive Sampling and Fast Low-Rank Matrix Approximation
Deshpande, A., & Vempala, S. (2006) · Lecture Notes in Computer Science · doi:10.1007/11830924_28 · Cited by 186
An estimator for the diagonal of a matrix
Bekas, C., Kokiopoulou, E., & Saad, Y. (2007) · Applied Numerical Mathematics · doi:10.1016/j.apnum.2007.01.003 · Cited by 185
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
Face recognition experiments with random projection
Goel, N., Bebis, G., & Nefian, A. (2005) · SPIE Proceedings · doi:10.1117/12.605553 · Cited by 182
Graph Effective Resistance and Distributed Control: Spectral Properties and Applications
Barooah, P., & Hespanha, J. P. (2006) · Proceedings of the 45th IEEE Conference on Decision and Control · doi:10.1109/cdc.2006.377619 · Cited by 181
Sampling algorithms for l2 regression and applications
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2006) · Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 · doi:10.1145/1109557.1109682 · Cited by 172
Self-citationOn variants of the Johnson–Lindenstrauss lemma
Matoušek, J. (2008) · Random Structures & Algorithms · doi:10.1002/rsa.20218 · Cited by 167
Spectral methods in machine learning and new strategies for very large datasets
Belabbas, M.-A., & Wolfe, P. J. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0810600105 · Cited by 158
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
On Rank-Revealing Factorisations
Chandrasekaran, S., & Ipsen, I. C. F. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479891223781 · Cited by 155
Unsupervised feature selection for principal components analysis
Boutsidis, C., Mahoney, M. W., & Petros Drineas, B. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401903 · Cited by 151
Self-citationGalaxy types in the Sloan Digital Sky Survey using supervised artificial neural networks
Ball, N. M., Loveday, J., Fukugita, M., Nakamura, O., Okamura, S., Brinkmann, J., & Brunner, R. (2004) · Monthly Notices of the Royal Astronomical Society · doi:10.1111/j.1365-2966.2004.07429.x · Cited by 149
Selection of Genetic Markers for Association Analyses, Using Linkage Disequilibrium and Haplotypes
Meng, Z., Zaykin, D. V., Xu, C., Wagner, M. J., & Ehm, M. G. (2003) · The American Journal of Human Genetics · doi:10.1086/376561 · Cited by 148
Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition
Hong, Y., & Pan, C.-T. (1992) · Mathematics of Computation · doi:10.1090/s0025-5718-1992-1106970-4 · Cited by 146
Dasgupta, A., Kumar, R., & Sarlós, T. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806737 · Cited by 143
Unsupervised Feature Selection for the k-means Clustering Problem
Boutsidis, C., Petros Drineas, B., & Mahoney, M. W. (2009) · Cited by 139
Self-citationSpectra of sparse random matrices
Kühn, R. (2008) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/41/29/295002 · Cited by 136
Rank and null space calculations using matrix decomposition without column interchanges
Foster, L. V. (1986) · Linear Algebra and its Applications · doi:10.1016/0024-3795(86)90115-1 · Cited by 130
Sampling Techniques for the Nystrom Method
Kumar, S., Mohri, M., & Talwalkar, A. (2009) · Cited by 124
Colibri: fast mining of large static and dynamic graphs
Tong, H., Papadimitriou, S., Sun, J., Yu, P. S., & Faloutsos, C. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401973 · Cited by 123
Less is More: Compact Matrix Decomposition for Large Sparse Graphs
Sun, J., Xie, Y., Zhang, H., & Faloutsos, C. (2007) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972771.33 · Cited by 121
An artificial neural network approach to the classification of galaxy spectra
Folkes, S. R., Lahav, O., & Maddox, S. (1996) · Monthly Notices of the Royal Astronomical Society · doi:10.1093/mnras/283.2.651 · Cited by 120
Finding Haplotype Tagging SNPs by Use of Principal Components Analysis
Lin, Z., & Altman, R. B. (2004) · The American Journal of Human Genetics · doi:10.1086/425587 · Cited by 119
Diffusion in a sparsely connected space: A model for glassy relaxation
Bray, A. J., & Rodgers, G. J. (1988) · Physical review. B, Condensed matter · doi:10.1103/physrevb.38.11461 · Cited by 116
SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
Lin, L., Yang, C., Meza, J. C., Lu, J., Ying, L., & Weinan, E. (2011) · ACM Transactions on Mathematical Software · doi:10.1145/1916461.1916464 · Cited by 116
Ancestry informative markers for fine-scale individual assignment to worldwide populations
Paschou, P., Lewis, J., Javed, A., & Petros Drineas, B. (2010) · Journal of Medical Genetics · doi:10.1136/jmg.2010.078212 · Cited by 114
Horne, B. D., & Camp, N. J. (2003) · Genetic Epidemiology · doi:10.1002/gepi.10292 · Cited by 111
Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities
Dankulov, M. M., & Tadić, B. (2009) · Physical Review E · doi:10.1103/physreve.80.026123 · Cited by 111
Chan, T. F.-C., & Hansen, P. C. (1990) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0911029 · Cited by 96
Fast construction of hierarchical matrix representation from matrix–vector multiplication
Lin, L., Lu, J., & Lexing Ying, B. (2011) · Journal of Computational Physics · doi:10.1016/j.jcp.2011.02.033 · Cited by 96
Tracing Sub-Structure in the European American Population with PCA-Informative Markers
Paschou, P., Petros Drineas, B., Lewis, J., Nievergelt, C. M., Nickerson, D. A., Smith, J. D., Ridker, P. M., Chasman, D. I., Krauss, R. M., & Ziv, E. (2008) · PLoS Genetics · doi:10.1371/journal.pgen.1000114 · Cited by 93
Fast Computation of Fourier Integral Operators
Candès, E. J., Demanet, L., & Ying, L. (2007) · SIAM Journal on Scientific Computing · doi:10.1137/060671139 · Cited by 90
A Robust Classification of Galaxy Spectra: Dealing with Noisy and Incomplete Data
Connolly, A. J., & Szalay, A. S. (1999) · The Astronomical Journal · doi:10.1086/300839 · Cited by 84
Graph spectra as a systematic tool in computational biology
Banerjee, A., & Jost, J. (2009) · Discrete Applied Mathematics · doi:10.1016/j.dam.2008.06.033 · Cited by 81
Vector algebra in the analysis of genome-wide expression data
Kuruvilla, F. G., Park, P. J., & Schreiber, S. L. (2002) · Genome biology · doi:10.1186/gb-2002-3-3-research0011 · Cited by 70
Ailon, N., & Chazelle, B. (2010) · Communications of the ACM · doi:10.1145/1646353.1646379 · Cited by 68
Stable and Efficient Gaussian Process Calculations
Foster, L. V., Waagen, A., Aijaz, N., Hurley, M., Luis, A., Rinsky, J., Satyavolu, C. J., Way, M. J., Gazis, P. R., & Srivastava, A. N. (2009) · Cited by 59
Testing for the Inclusion of Variables in Linear Regression by a Randomisation Technique
Draper, N. R., & Stoneman, D. M. (1966) · Technometrics · doi:10.2307/1266641 · Cited by 57
Dense Fast Random Projections and Lean Walsh Transforms
Liberty, E., Ailon, N., & Singer, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_40 · Cited by 52
Tensor-CUR decompositions for tensor-based data
Mahoney, M. W., Maggioni, M., & Petros Drineas, B. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150440 · Cited by 51
Self-citationWay, M. J., Foster, L. V., Gazis, P. R., & Srivastava, A. N. (2009) · The Astrophysical Journal · doi:10.1088/0004-637x/706/1/623 · Cited by 50
Petros Drineas, B., Lewis, J., & Paschou, P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011892 · Cited by 48
Structure-Preserving and Rank-Revealing QR-Factorizations
Bischof, C. H., & Hansen, P. C. (1991) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0912073 · Cited by 47
The Johnson-Lindenstrauss Transform: An Empirical Study
Venkatasubramanian, S., & Wang, Q. (2011) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972917.16 · Cited by 45
Some issues in dense linear algebra for multicore and special purpose architecturesPreprint
Baboulin, M., Dongarra, J. J., & Tomov, S. Z. (2008) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · Cited by 45
Brunner, R. J., Djorgovski, S. G., Prince, T. A., & Szalay, A. S. (2002) · Massive computing · doi:10.1007/978-1-4615-0005-6_27 · Cited by 45
PRINCIPAL COMPONENT ANALYSIS OF SLOAN DIGITAL SKY SURVEY STELLAR SPECTRA
McGurk, R., Kimball, A. E., & Ivezić, Ž. (2010) · The Astronomical Journal · doi:10.1088/0004-6256/139/3/1261 · Cited by 43
Sparser Johnson-Lindenstrauss Transforms
Kane, D. M., & Nelson, J. (2012) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973099.94 · Cited by 35
Subset Selection Algorithms: Randomized vs. Deterministic
Broadbent, M., Brown, M., & Penner, K. (2010) · SIAM Undergraduate Research Online · doi:10.1137/09s010435 · Cited by 32
Eriksson-Bique, S. D., Solbrig, M., Stefanelli, M., Warkentin, S., Abbey, R., & Ipsen, I. C. F. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/10080659x · Cited by 29
Chaillat, S., & Biros, G. (2012) · Journal of Computational Physics · doi:10.1016/j.jcp.2012.02.006 · Cited by 24
Fast Low-Rank Approximation for Covariance Matrices
Belabbas, M.-A., & Wolfe, P. J. (2007) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2007.4498023 · Cited by 19
Subsampling Algorithms for Semidefinite ProgrammingPreprint
d’Aspremont, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0803.1990 · Cited by 19
On sparse representations of linear operators and the approximation of matrix products
Belabbas, M.-A., & Wolfe, P. J. (2008) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2008.4558532 · Cited by 17
Efficient Genomewide Selection of PCA-Correlated tSNPs for Genotype Imputation
Javed, A., Petros Drineas, B., Mahoney, M. W., & Paschou, P. (2011) · Annals of Human Genetics · doi:10.1111/j.1469-1809.2011.00673.x · Cited by 13
Self-citationFast approximation of matrix coherence and statistical leveragePreprint
Petros Drineas, B., Magdon‐Ismail, M., Mahoney, M. W., & Woodruff, D. P. (2011) · arXiv (Cornell University) · Cited by 13
Self-citationRapid factorization of structured matrices via randomized samplingPreprint
Martinsson, P. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0806.2339 · Cited by 10
Parameterisation of Galaxy Spectra in the 2dF Galaxy Redshift Survey
Madgwick, D. S., Lahav, O., Taylor, K., & the dFGRS Team (2006) · Springer eBooks · doi:10.1007/10849171_39 · Cited by 5
Cited by
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955
Inference in artificial intelligence with deep optics and photonics
Wetzstein, G., Ozcan, A., Gigan, S., Fan, S., Englund, D., Soljačić, M., Denz, C., Miller, D. A. B., & Psaltis, D. (2020) · Nature · doi:10.1038/s41586-020-2973-6 · Cited by 1,031
Computational Advertising: Techniques for Targeting Relevant Ads
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 866
RASL: Robust Alignment by Sparse and Low-Rank Decomposition for Linearly Correlated Images
Peng, Y., Ganesh, A., Wright, J., Xu, W., & Ma, Y. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.282 · Cited by 817
Stochastic Configuration Networks: Fundamentals and Algorithms
Wang, D., & Li, M. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2734043 · Cited by 727
Metadata
- Authors
- MAHONEY, M.
- Venue
- Chapman & Hall/CRC Data Mining and Knowledge Discovery Series
- Publisher
- Chapman and Hall/CRC
- Published
- 2012-03-29
- ISSN
- 2154-5286 (ISSN-L)
- OpenAlex
- W1999352252
- Cited by
- 409
- References
- 149
- FWCI
- 111.61
- Type
- book chapter
- Language
- en
- Open access
- closed
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.