# Randomised linear algebra

August 16, 2016 — October 22, 2022

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

- RaphaelArkadyMeyerNYU/HutchPlusPlus: Code for Hutch++: Optimal Stochastic Trace Estimation Saibaba, Alexanderian, and Ipsen (2017)

## 3 Random Fourier Features

## 4 Randomisation in matrix factorization

See various matrix factorisation methods.

## 5 Random regression

## 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.

## 7 Stochastic Lanczos Quadrature

## 8 Tools

### 8.1 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 (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)

## 9 References

*Journal of Computer and System Sciences*, Special Issue on PODS 2001,.

*J. ACM*.

*arXiv:1411.0306 [Cs, Stat]*.

*Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. KDD ’01.

*Linear Algebra and Its Applications*.

*arXiv:1703.00864 [Stat]*.

*Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence*. UAI’00.

*Random Structures & Algorithms*.

*Advances in Neural Information Processing Systems 28*. NIPS’15.

*SIAM Journal on Computing*.

*SIAM Journal on Computing*.

*Journal of Machine Learning Research*.

*arXiv:1608.02148 [Cs, Stat]*.

*Matrices, Moments and Quadrature with Applications*.

*arXiv:2007.07383 [Physics, Stat]*.

*arXiv:1612.06013 [Math]*.

*arXiv:1602.01768 [Cs, Math]*.

*SIAM Journal on Scientific Computing*.

*arXiv:2104.14429 [Cs, Stat]*.

*Communications in Statistics - Simulation and Computation*.

*arXiv:1606.05732 [Cs]*.

*Advances in Neural Information Processing Systems 29*.

*arXiv:1606.06511 [Cs, Math]*.

*arXiv:1607.04331 [Cs, q-Bio, Stat]*.

*Advances in Neural Information Processing Systems*.

*Advances in Neural Information Processing Systems 13*.

*Proceedings of the National Academy of Sciences*.

*Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. KDD ’06.

*Randomized Algorithms for Matrices and Data*.

*arXiv:1607.01649 [Math]*.

*arXiv:1503.07157 [Math]*.

*BIT Numerical Mathematics*.

*arXiv:1608.07597 [Stat]*.

*PPSC*.

*Advances in Neural Information Processing Systems*.

*Advances in Neural Information Processing Systems*.

*arXiv:2011.12428 [Cond-Mat, Stat]*.

*SIAM J. Matrix Anal. Appl.*

*Proceedings of the National Academy of Sciences*.

*arXiv:2105.08875 [Cs, Math, Stat]*.

*An Introduction to Matrix Concentration Inequalities*.

*arXiv:1609.00048 [Cs, Math, Stat]*.

*arXiv:1412.8447 [Cs, Math]*.

*arXiv:1505.07570 [Cs]*.

*Applied and Computational Harmonic Analysis*.

*Advances in Neural Information Processing Systems*.

*arXiv:1502.03032 [Cs, Math, Stat]*.

*arXiv:1412.8293 [Cs, Math, Stat]*.

*IEEE International Conference of Data Mining*.

*Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. KDD ’17.

*Proceedings of the 28th International Conference on International Conference on Machine Learning*. ICML’11.