The twin to random matrices, and elder sibling of vector random projections; doing linear algebra operations using randomised matrix projections. Useful for, e.g. randomised regression

Quite an old method, but extra hot recently.

Obligatory Igor Carron mention:

IBM has a research group in this although they seem to have gone silent since a good year in 2014.

Mart16 seems to be the best fresh review of the action.

TBD: make coherent.

To learn: Are people doing this with quasi monte carlo? SAME14 seems to be one; any others?

## Implementations

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

## Random regression

## Refs

- Achl03
- Achlioptas, D. (2003) Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
*Journal of Computer and System Sciences*, 66(4), 671–687. DOI. - AcMc07
- Achlioptas, D., & Mcsherry, F. (2007) Fast Computation of Low-rank Matrix Approximations.
*J. ACM*, 54(2). DOI. - AlMa14
- Alaoui, A. E., & Mahoney, M. W.(2014) Fast Randomized Kernel Methods With Statistical Guarantees.
*arXiv:1411.0306 [cs, Stat]*. - BiMa01
- Bingham, E., & Mannila, H. (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 (pp. 245–250). New York, NY, USA: ACM DOI.
- DrMa05
- Drineas, P., & Mahoney, M. W.(2005) On the Nyström method for approximating a Gram matrix for improved kernel-based learning.
*Journal of Machine Learning Research*, 6, 2153–2175. - EVBK16
- Erichson, N. B., Voronin, S., Brunton, S. L., & Kutz, J. N.(2016) Randomized Matrix Decompositions using R.
*arXiv:1608.02148 [cs, Stat]*. - HaMT09
- Halko, N., Martinsson, P.-G., & Tropp, J. A.(2009) Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.
*arXiv:0909.4061 [math]*. - KuSh16
- Kumar, N. K., & Shneider, J. (2016) Literature survey on low rank approximation of matrices.
*arXiv:1606.06511 [cs, Math]*. - LiHC06
- Li, P., Hastie, T. J., & Church, K. W.(2006) Very Sparse Random Projections. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 287–296). New York, NY, USA: ACM DOI.
- Maho10
- Mahoney, M. W.(2010) Randomized Algorithms for Matrices and Data.
*Foundations and Trends® in Machine Learning*, 3(2), 123–224. DOI. - Mart16
- Martinsson, P.-G. (2016) Randomized methods for matrix computations and analysis of high dimensional data.
*arXiv:1607.01649 [math]*. - MaVo15
- Martinsson, P.-G., & Voronin, S. (2015) A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices.
*arXiv:1503.07157 [math]*. - SAME14
- Sindhwani, V., Avron, H., Mahoney, M. W., & EDU, B. (2014) Quasi-Monte Carlo feature maps for shift-invariant kernels.
- Trop15
- Tropp, J. A.(2015) An Introduction to Matrix Concentration Inequalities.
*arXiv:1501.01571 [cs, Math, Stat]*. - VoMa14
- Voronin, S., & Martinsson, P.-G. (2014) Efficient Algorithms for CUR and Interpolative Matrix Decompositions.
*arXiv:1412.8447 [cs, Math]*. - VoMa15
- Voronin, S., & Martinsson, P.-G. (2015) RSVDPACK: An implementation of randomized algorithms for computing the singular value, interpolative, and CUR decompositions of matrices on multi-core and GPU architectures.
*arXiv:1502.05366 [cs, Math]*. - Wang15
- Wang, S. (2015) A Practical Guide to Randomized Matrix Computations with MATLAB Implementations.
*arXiv:1505.07570 [cs]*. - YaMM15
- Yang, J., Meng, X., & Mahoney, M. W.(2015) Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments.
*arXiv:1502.03032 [cs, Math, Stat]*. - YLMJ12
- Yang, T., Li, Y.-F., Mahdavi, M., Jin, R., & Zhou, Z.-H. (2012) Nyström method vs random fourier features: A theoretical and empirical comparison. In Advances in neural information processing systems (pp. 476–484).
- ZhTa11
- Zhou, T., & Tao, D. (2011) Godec: Randomized low-rank & sparse matrix decomposition in noisy case.