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

- RoTy08: (2008) A fast randomized algorithm for overdetermined linear least-squares regression.
*Proceedings of the National Academy of Sciences*, 105(36), 13212–13217. DOI - WLRT08: (2008) A fast randomized algorithm for the approximation of matrices.
*Applied and Computational Harmonic Analysis*, 25(3), 335–366. DOI - Wang15: (2015) A Practical Guide to Randomized Matrix Computations with MATLAB Implementations.
*ArXiv:1505.07570 [Cs]*. - RoST09: (2009) A Randomized Algorithm for Principal Component Analysis.
*SIAM J. Matrix Anal. Appl.*, 31(3), 1100–1124. DOI - MaRT06: (2006) A randomized algorithm for the approximation of matrices. DTIC Document
- PoBe16: (2016) A Randomized Approach to Efficient Kernel Clustering.
*ArXiv:1608.07597 [Stat]*. - MaVo15: (2015) A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices.
*ArXiv:1503.07157 [Math]*. - Hutc90: (1990) A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines.
*Communications in Statistics - Simulation and Computation*, 19(2), 433–450. DOI - LeSe01: (2001) Algorithms for Non-negative Matrix Factorization. In Advances in Neural Information Processing Systems 13 (pp. 556–562). MIT Press
- Trop15: (2015) An Introduction to Matrix Concentration Inequalities.
*ArXiv:1501.01571 [Cs, Math, Stat]*. - Achl03: (2003) Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
*Journal of Computer and System Sciences*, 66(4), 671–687. DOI - VoMa14: (2014) Efficient Algorithms for CUR and Interpolative Matrix Decompositions.
*ArXiv:1412.8447 [Cs, Math]*. - Zhao17: (2017) Fast Algorithms on Random Matrices and Structured Matrices.
- AcMc07: (2007) Fast Computation of Low-rank Matrix Approximations.
*J. ACM*, 54(2). DOI - AlMa14: (2014) Fast Randomized Kernel Methods With Statistical Guarantees.
*ArXiv:1411.0306 [Cs, Stat]*. - HaMT09: (2009) Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.
*ArXiv:0909.4061 [Math]*. - ZhTa11: (2011) Godec: Randomized low-rank & sparse matrix decomposition in noisy case.
- KaPW16: (2016) How to Fake Multiply by a Gaussian Matrix.
*ArXiv:1606.05732 [Cs]*. - YaMM15: (2015) Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments.
*ArXiv:1502.03032 [Cs, Math, Stat]*. - KuSh16: (2016) Literature survey on low rank approximation of matrices.
*ArXiv:1606.06511 [Cs, Math]*. - YLMJ12: (2012) Nyström method vs random fourier features: A theoretical and empirical comparison. In Advances in neural information processing systems (pp. 476–484).
- DrMa05: (2005) On the Nyström method for approximating a Gram matrix for improved kernel-based learning.
*Journal of Machine Learning Research*, 6, 2153–2175. - YSAM14: (2014) Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels.
*ArXiv:1412.8293 [Cs, Math, Stat]*. - BiMa01: (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
- LaGG16: (2016) Random projections of random manifolds.
*ArXiv:1607.04331 [Cs, q-Bio, Stat]*. - ZLZX17: (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 (pp. 615–623). New York, NY, USA: ACM DOI
- Maho10: (2010) Randomized Algorithms for Matrices and Data.
*Foundations and Trends® in Machine Learning*, 3(2), 123–224. DOI - LWMR07: (2007) Randomized algorithms for the low-rank approximation of matrices.
*Proceedings of the National Academy of Sciences*, 104(51), 20167–20172. DOI - EVBK16: (2016) Randomized Matrix Decompositions using R.
*ArXiv:1608.02148 [Cs, Stat]*. - SaAI16: (2016) Randomized Matrix-free Trace and Log-Determinant Estimators.
*ArXiv:1605.04893 [Math]*. - Mart16: (2016) Randomized methods for matrix computations and analysis of high dimensional data.
*ArXiv:1607.01649 [Math]*. - GoRi16: (2016) Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms.
*ArXiv:1602.01768 [Cs, Math]*. - TYUC16: (2016) Randomized single-view algorithms for low-rank matrix approximation.
*ArXiv:1609.00048 [Cs, Math, Stat]*. - KMKB16: (2016) Scalable Adaptive Stochastic Optimization Using Random Projections. In Advances in Neural Information Processing Systems 29 (pp. 1750–1758). Curran Associates, Inc.
- YHSD12: (2012) Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems. In IEEE International Conference of Data Mining (pp. 765–774). DOI
- DeBo15: (2015) Scalable Inference for Gaussian Process Models with Black-box Likelihoods. In Advances in Neural Information Processing Systems 28 (pp. 1414–1422). Cambridge, MA, USA: MIT Press
- Gowe16: (2016) Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices.
*ArXiv:1612.06013 [Math]*. - ChRW17: (2017) The Unreasonable Effectiveness of Random Orthogonal Embeddings.
*ArXiv:1703.00864 [Stat]*. - LiHC06: (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