See random matrices, vector random projections and many other related tricks Notes on doing linear algebra operations using randomised matrix projections. Useful for, e.g. randomised regression.
Context
Obligatory Igor Carron mention: Random matrices are too damn large. Martinsson (2016) seems to be a fresh review of the action.
Log det and trace estimation
Machine Learning Trick of the Day (3): Hutchinsonβs Trickβ Shakir Mohammed
- RaphaelArkadyMeyerNYU/HutchPlusPlus: Code for Hutch++: Optimal Stochastic Trace Estimation Saibaba, Alexanderian, and Ipsen (2017)
Random Fourier Features
Randomisation in matrix factorization
See various matrix factorisation methods.
Random regression
Tools
- R: rSVD, Randomised SVD in R (Erichson et al. 2016)
- Python/C++: IBMβs libskylark
- c: RSVDPACK implements low rank SVD, ID, and CUR factorizations of matrices, also does GPU calculations. (Martinsson and Voronin 2015; Voronin and Martinsson 2014)
- MATLAB: RandMatrixMatlab (Wang 2015)
References
Achlioptas, Dimitris. 2003. βDatabase-Friendly Random Projections: Johnson-Lindenstrauss with Binary Coins.β Journal of Computer and System Sciences, Special Issue on PODS 2001, 66 (4): 671β87.
Achlioptas, Dimitris, and Frank Mcsherry. 2007. βFast Computation of Low-Rank Matrix Approximations.β J. ACM 54 (2).
Alaoui, Ahmed El, and Michael W. Mahoney. 2014. βFast Randomized Kernel Methods With Statistical Guarantees.β arXiv:1411.0306 [Cs, Stat], November.
Bingham, Ella, and Heikki Mannila. 2001. βRandom Projection in Dimensionality Reduction: Applications to Image and Text Data.β In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 245β50. KDD β01. New York, NY, USA: ACM.
Boutsidis, Christos, Petros Drineas, Prabhanjan Kambadur, Eugenia-Maria Kontopoulou, and Anastasios Zouzias. 2017. βA Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix.β Linear Algebra and Its Applications 533 (November): 95β117.
Choromanski, Krzysztof, Mark Rowland, and Adrian Weller. 2017. βThe Unreasonable Effectiveness of Random Orthogonal Embeddings.β arXiv:1703.00864 [Stat], March.
Dasgupta, Sanjoy. 2000. βExperiments with Random Projection.β In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, 143β51. UAIβ00. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
Dasgupta, Sanjoy, and Anupam Gupta. 2003. βAn Elementary Proof of a Theorem of Johnson and Lindenstrauss.β Random Structures & Algorithms 22 (1): 60β65.
Dezfouli, Amir, and Edwin V. Bonilla. 2015. βScalable Inference for Gaussian Process Models with Black-Box Likelihoods.β In Advances in Neural Information Processing Systems 28, 1414β22. NIPSβ15. Cambridge, MA, USA: MIT Press.
Drineas, Petros, and Michael W. Mahoney. 2005. βOn the NystrΓΆm Method for Approximating a Gram Matrix for Improved Kernel-Based Learning.β Journal of Machine Learning Research 6 (December): 2153β75.
Erichson, N. Benjamin, Sergey Voronin, Steven L. Brunton, and J. Nathan Kutz. 2016. βRandomized Matrix Decompositions Using R.β arXiv:1608.02148 [Cs, Stat], August.
Gottwald, Georg A., and Sebastian Reich. 2020. βSupervised Learning from Noisy Observations: Combining Machine-Learning Techniques with Data Assimilation.β arXiv:2007.07383 [Physics, Stat], July.
Gower, Robert M. 2016. βSketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices.β arXiv:1612.06013 [Math], December.
Gower, Robert M., and Peter RichtΓ‘rik. 2016. βRandomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms.β arXiv:1602.01768 [Cs, Math], February.
Halko, Nathan, Per-Gunnar Martinsson, and Joel A. Tropp. 2010. βFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.β arXiv.
Hesslow, Daniel, Alessandro Cappelli, Igor Carron, Laurent Daudet, RaphaΓ«l Lafargue, Kilian MΓΌller, Ruben Ohana, Gustave Pariente, and Iacopo Poli. 2021. βPhotonic Co-Processors in HPC: Using LightOn OPUs for Randomized Numerical Linear Algebra.β arXiv:2104.14429 [Cs, Stat], May.
Hutchinson, M.F. 1990. βA Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines.β Communications in Statistics - Simulation and Computation 19 (2): 433β50.
Kapralov, Michael, Vamsi K. Potluru, and David P. Woodruff. 2016. βHow to Fake Multiply by a Gaussian Matrix.β arXiv:1606.05732 [Cs], June.
Krummenacher, Gabriel, Brian McWilliams, Yannic Kilcher, Joachim M Buhmann, and Nicolai Meinshausen. 2016. βScalable Adaptive Stochastic Optimization Using Random Projections.β In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 1750β58. Curran Associates, Inc.
Kumar, N. Kishore, and Jan Shneider. 2016. βLiterature Survey on Low Rank Approximation of Matrices.β arXiv:1606.06511 [Cs, Math], June.
Lahiri, Subhaneil, Peiran Gao, and Surya Ganguli. 2016. βRandom Projections of Random Manifolds.β arXiv:1607.04331 [Cs, q-Bio, Stat], July.
Launay, Julien, Iacopo Poli, FranΓ§ois Boniface, and Florent Krzakala. 2020. βDirect Feedback Alignment Scales to Modern Deep Learning Tasks and Architectures.β In Advances in Neural Information Processing Systems, 33:15.
Lee, Daniel D., and H. Sebastian Seung. 2001. βAlgorithms for Non-Negative Matrix Factorization.β In Advances in Neural Information Processing Systems 13, edited by T. K. Leen, T. G. Dietterich, and V. Tresp, 556β62. MIT Press.
Li, Ping, Trevor J. Hastie, and Kenneth W. Church. 2006. βVery Sparse Random Projections.β In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 287β96. KDD β06. New York, NY, USA: ACM.
Liberty, Edo, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert. 2007. βRandomized Algorithms for the Low-Rank Approximation of Matrices.β Proceedings of the National Academy of Sciences 104 (51): 20167β72.
Mahoney, Michael W. 2010. Randomized Algorithms for Matrices and Data. Vol. 3.
Martinsson, Per-Gunnar. 2016. βRandomized Methods for Matrix Computations and Analysis of High Dimensional Data.β arXiv:1607.01649 [Math], July.
Martinsson, Per-Gunnar, Vladimir Rockhlin, and Mark Tygert. 2006. βA Randomized Algorithm for the Approximation of Matrices.β DTIC Document.
Martinsson, Per-Gunnar, and Sergey Voronin. 2015. βA Randomized Blocked Algorithm for Efficiently Computing Rank-Revealing Factorizations of Matrices.β arXiv:1503.07157 [Math], March.
Meyer, Raphael A., Cameron Musco, Christopher Musco, and David P. Woodruff. 2021. βHutch++: Optimal Stochastic Trace Estimation.β arXiv.
Pourkamali-Anaraki, Farhad, and Stephen Becker. 2016. βA Randomized Approach to Efficient Kernel Clustering.β arXiv:1608.07597 [Stat], August.
Rahimi, Ali, and Benjamin Recht. 2007. βRandom Features for Large-Scale Kernel Machines.β In Advances in Neural Information Processing Systems, 1177β84. Curran Associates, Inc.
βββ. 2009. βWeighted Sums of Random Kitchen Sinks: Replacing Minimization with Randomization in Learning.β In Advances in Neural Information Processing Systems, 1313β20. Curran Associates, Inc.
Refinetti, Maria, StΓ©phane dβAscoli, Ruben Ohana, and Sebastian Goldt. 2021. βAlign, Then Memorise: The Dynamics of Learning with Feedback Alignment.β arXiv:2011.12428 [Cond-Mat, Stat], June.
Rokhlin, Vladimir, Arthur Szlam, and Mark Tygert. 2009. βA Randomized Algorithm for Principal Component Analysis.β SIAM J. Matrix Anal. Appl. 31 (3): 1100β1124.
Rokhlin, Vladimir, and Mark Tygert. 2008. βA Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression.β Proceedings of the National Academy of Sciences 105 (36): 13212β17.
Saibaba, Arvind K., Alen Alexanderian, and Ilse C. F. Ipsen. 2017. βRandomized Matrix-Free Trace and Log-Determinant Estimators.β arXiv.
Shi, Jiaxin, Shengyang Sun, and Jun Zhu. 2018. βA Spectral Approach to Gradient Estimation for Implicit Distributions.β In. arXiv.
Skorski, Maciej. 2020. βA Modern Analysis of Hutchinsonβs Trace Estimator.β arXiv.
Sterge, Nicholas, and Bharath Sriperumbudur. 2021. βStatistical Optimality and Computational Efficiency of NystrΓΆm Kernel PCA.β arXiv:2105.08875 [Cs, Math, Stat], May.
Tropp, Joel A. 2015. An Introduction to Matrix Concentration Inequalities.
Tropp, Joel A., Alp Yurtsever, Madeleine Udell, and Volkan Cevher. 2016. βRandomized Single-View Algorithms for Low-Rank Matrix Approximation.β arXiv:1609.00048 [Cs, Math, Stat], August.
Voronin, Sergey, and Per-Gunnar Martinsson. 2014. βEfficient Algorithms for CUR and Interpolative Matrix Decompositions.β arXiv:1412.8447 [Cs, Math], December.
Wang, Shusen. 2015. βA Practical Guide to Randomized Matrix Computations with MATLAB Implementations.β arXiv:1505.07570 [Cs], May.
Woolfe, Franco, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. 2008. βA Fast Randomized Algorithm for the Approximation of Matrices.β Applied and Computational Harmonic Analysis 25 (3): 335β66.
Yang, Jiyan, Xiangrui Meng, and Michael W. Mahoney. 2015. βImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments.β arXiv:1502.03032 [Cs, Math, Stat], February.
Yang, Jiyan, Vikas Sindhwani, Haim Avron, and Michael Mahoney. 2014. βQuasi-Monte Carlo Feature Maps for Shift-Invariant Kernels.β arXiv:1412.8293 [Cs, Math, Stat], December.
Yang, Tianbao, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. 2012. βNystrΓΆm Method Vs Random Fourier Features: A Theoretical and Empirical Comparison.β In Advances in Neural Information Processing Systems, 476β84.
Yu, Hsiang-Fu, Cho-Jui Hsieh, Si Si, and Inderjit S. Dhillon. 2012. βScalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems.β In IEEE International Conference of Data Mining, 765β74.
Zhang, Kai, Chuanren Liu, Jie Zhang, Hui Xiong, Eric Xing, and Jieping Ye. 2017. βRandomization or Condensation?: Linear-Cost Matrix Sketching Via Cascaded Compression Sampling.β In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 615β23. KDD β17. New York, NY, USA: ACM.
Zhao, Liang. 2017. βFast Algorithms on Random Matrices and Structured Matrices.β
Zhou, Tianyi, and Dacheng Tao. 2011. βGodec: Randomized Low-Rank & Sparse Matrix Decomposition in Noisy Case.β
No comments yet. Why not leave one?