# Randomised linear algebra

August 16, 2016 — October 22, 2022

algebra
approximation
feature construction
functional analysis
geometry
high d
linear algebra
measure
metrics
model selection
probabilistic algorithms
probability
signal processing
sparser than thou

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.

## 1 Context

Obligatory Igor Carron mention: Random matrices are too damn large. Martinsson (2016) seems to be a fresh review of the action.

## 2 Log det and trace estimation

Machine Learning Trick of the Day (3): Hutchinson’s Trick— Shakir Mohammed

## 4 Randomisation in matrix factorization

See various matrix factorisation methods.

## 6 Hutchinson trace estimator

Shakir Mohamed mentions Hutchinson’s Trick, and was introduced to it, as I was, by Dr Maurizio Filippone. This trick also works with efficiently with the ensemble Kalman filter, where the randomised products are cheap.

Overview — imate Manual

## 8 Tools

### 8.1 imate

Overview — imate

The main purpose of ımate is to estimate the algebraic quantity $\operatorname{trace}(f(\mathbf{A}))$ where $$\mathbf{A}$$ is a square matrix, $$f$$ is a matrix function, and trace $$(\cdot)$$ is the trace operator. Imate can also compute variants of $$(1)$$, such as $\operatorname{trace}(\mathbf{B} f(\mathbf{A}))$ and $\operatorname{trace}(\mathbf{B} f(\mathbf{A}) \mathbf{C} f(\mathbf{A}))$ where $$\mathbf{B}$$ and $$\mathbf{C}$$ are matrices. Other variations include the cases where $$\mathbf{A}$$ is replaced by $$\mathbf{A}^{\top} \mathbf{A}$$ in the above expressions.

### 8.2 Misc

• R: rSVD, Randomised SVD in R
• Python/C++: IBM’s libskylark
• c: RSVDPACK implements low rank SVD, ID, and CUR factorizations of matrices, also does GPU calculations.
• MATLAB: RandMatrixMatlab

## 9 References

Achlioptas. 2003. Journal of Computer and System Sciences, Special Issue on PODS 2001,.
Achlioptas, and Mcsherry. 2007. J. ACM.
Alaoui, and Mahoney. 2014. arXiv:1411.0306 [Cs, Stat].
Bardenet, and Maillard. 2015.
Bingham, and Mannila. 2001. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’01.
Boutsidis, Drineas, Kambadur, et al. 2017. Linear Algebra and Its Applications.
Brossollet, Cappelli, Carron, et al. 2021.
Cavaillès, Boucher, Daudet, et al. 2022. Optics Express.
Choromanski, Rowland, and Weller. 2017. arXiv:1703.00864 [Stat].
Dasgupta. 2000. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence. UAI’00.
Dasgupta, and Gupta. 2003. Random Structures & Algorithms.
Dezfouli, and Bonilla. 2015. In Advances in Neural Information Processing Systems 28. NIPS’15.
Drineas, Kannan, and Mahoney. 2006a. SIAM Journal on Computing.
———. 2006b. SIAM Journal on Computing.
Drineas, and Mahoney. 2005. Journal of Machine Learning Research.
Edelman. 1989.
Erichson, Voronin, Brunton, et al. 2016. arXiv:1608.02148 [Cs, Stat].
Golub, and Meurant. 2010. Matrices, Moments and Quadrature with Applications.
Gottwald, and Reich. 2020. arXiv:2007.07383 [Physics, Stat].
Gower. 2016. arXiv:1612.06013 [Math].
Gower, and Richtárik. 2016. arXiv:1602.01768 [Cs, Math].
Halko, Martinsson, Shkolnisky, et al. 2011. SIAM Journal on Scientific Computing.
Halko, Martinsson, and Tropp. 2010.
Hesslow, Cappelli, Carron, et al. 2021. arXiv:2104.14429 [Cs, Stat].
Hutchinson. 1990. Communications in Statistics - Simulation and Computation.
Kapralov, Potluru, and Woodruff. 2016. arXiv:1606.05732 [Cs].
Krummenacher, McWilliams, Kilcher, et al. 2016. In Advances in Neural Information Processing Systems 29.
Kumar, and Shneider. 2016. arXiv:1606.06511 [Cs, Math].
Lahiri, Gao, and Ganguli. 2016. arXiv:1607.04331 [Cs, q-Bio, Stat].
Launay, Poli, Boniface, et al. 2020. In Advances in Neural Information Processing Systems.
Lee, and Seung. 2001. In Advances in Neural Information Processing Systems 13.
Liberty, Woolfe, Martinsson, et al. 2007. Proceedings of the National Academy of Sciences.
Li, Hastie, and Church. 2006. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’06.
Mahoney. 2010. Randomized Algorithms for Matrices and Data.
Martinsson. 2016. arXiv:1607.01649 [Math].
Martinsson, Rockhlin, and Tygert. 2006.
Martinsson, and Voronin. 2015. arXiv:1503.07157 [Math].
Meyer, Musco, Musco, et al. 2021.
Nakatsukasa. 2017. BIT Numerical Mathematics.
Pourkamali-Anaraki, and Becker. 2016. arXiv:1608.07597 [Stat].
Rabani, and Toledo. 2001. In PPSC.
Rahimi, and Recht. 2007. In Advances in Neural Information Processing Systems.
———. 2009. In Advances in Neural Information Processing Systems.
Refinetti, d’Ascoli, Ohana, et al. 2021. arXiv:2011.12428 [Cond-Mat, Stat].
Rokhlin, Szlam, and Tygert. 2009. SIAM J. Matrix Anal. Appl.
Rokhlin, and Tygert. 2008. Proceedings of the National Academy of Sciences.
Saibaba, Alexanderian, and Ipsen. 2017.
Shi, Sun, and Zhu. 2018. In.
Skorski. 2020.
Sterge, and Sriperumbudur. 2021. arXiv:2105.08875 [Cs, Math, Stat].
Tropp. 2015. An Introduction to Matrix Concentration Inequalities.
Tropp, Yurtsever, Udell, et al. 2016. arXiv:1609.00048 [Cs, Math, Stat].
Voronin, and Martinsson. 2014. arXiv:1412.8447 [Cs, Math].
Wang. 2015. arXiv:1505.07570 [Cs].
Woolfe, Liberty, Rokhlin, et al. 2008. Applied and Computational Harmonic Analysis.
Yang, Tianbao, Li, Mahdavi, et al. 2012. In Advances in Neural Information Processing Systems.
Yang, Jiyan, Meng, and Mahoney. 2015. arXiv:1502.03032 [Cs, Math, Stat].
Yang, Jiyan, Sindhwani, Avron, et al. 2014. arXiv:1412.8293 [Cs, Math, Stat].
Yu, Hsieh, Si, et al. 2012. In IEEE International Conference of Data Mining.
Zhang, Liu, Zhang, et al. 2017. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’17.
Zhou, and Tao. 2011. In Proceedings of the 28th International Conference on International Conference on Machine Learning. ICML’11.