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?
- 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)
See randomised regression
- 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