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

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

## Stochastic Lanczos Quadrature

## Tools

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

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

## References

*Journal of Computer and System Sciences*, Special Issue on PODS 2001, 66 (4): 671β87.

*J. ACM*54 (2).

*arXiv:1411.0306 [Cs, Stat]*, November.

*Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, 245β50. KDD β01. New York, NY, USA: ACM.

*Linear Algebra and Its Applications*533 (November): 95β117.

*arXiv:1703.00864 [Stat]*, March.

*Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence*, 143β51. UAIβ00. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

*Random Structures & Algorithms*22 (1): 60β65.

*Advances in Neural Information Processing Systems 28*, 1414β22. NIPSβ15. Cambridge, MA, USA: MIT Press.

*SIAM Journal on Computing*36 (1): 158β83.

*SIAM Journal on Computing*36 (1): 184β206.

*Journal of Machine Learning Research*6 (December): 2153β75.

*arXiv:1608.02148 [Cs, Stat]*, August.

*Matrices, Moments and Quadrature with Applications*. USA: Princeton University Press.

*arXiv:2007.07383 [Physics, Stat]*, July.

*arXiv:1612.06013 [Math]*, December.

*arXiv:1602.01768 [Cs, Math]*, February.

*SIAM Journal on Scientific Computing*33 (5): 2580β94.

*arXiv:2104.14429 [Cs, Stat]*, May.

*Communications in Statistics - Simulation and Computation*19 (2): 433β50.

*arXiv:1606.05732 [Cs]*, June.

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

*arXiv:1606.06511 [Cs, Math]*, June.

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

*Advances in Neural Information Processing Systems*, 33:15.

*Advances in Neural Information Processing Systems 13*, edited by T. K. Leen, T. G. Dietterich, and V. Tresp, 556β62. MIT Press.

*Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, 287β96. KDD β06. New York, NY, USA: ACM.

*Proceedings of the National Academy of Sciences*104 (51): 20167β72.

*Randomized Algorithms for Matrices and Data*. Vol. 3.

*arXiv:1607.01649 [Math]*, July.

*arXiv:1503.07157 [Math]*, March.

*BIT Numerical Mathematics*57 (4): 1137β52.

*arXiv:1608.07597 [Stat]*, August.

*PPSC*.

*Advances in Neural Information Processing Systems*, 1177β84. Curran Associates, Inc.

*Advances in Neural Information Processing Systems*, 1313β20. Curran Associates, Inc.

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

*SIAM J. Matrix Anal. Appl.*31 (3): 1100β1124.

*Proceedings of the National Academy of Sciences*105 (36): 13212β17.

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

*An Introduction to Matrix Concentration Inequalities*.

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

*arXiv:1412.8447 [Cs, Math]*, December.

*arXiv:1505.07570 [Cs]*, May.

*Applied and Computational Harmonic Analysis*25 (3): 335β66.

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

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

*Advances in Neural Information Processing Systems*, 476β84.

*IEEE International Conference of Data Mining*, 765β74.

*Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, 615β23. KDD β17. New York, NY, USA: ACM.

*Proceedings of the 28th International Conference on International Conference on Machine Learning*, 33β40. ICMLβ11. Madison, WI, USA: Omnipress.

## No comments yet. Why not leave one?