The Living Thing / Notebooks : Randomised linear algebra

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?


Random regression

See randomised regression


Achlioptas, D. (2003) Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4), 671–687. DOI.
Achlioptas, D., & Mcsherry, F. (2007) Fast Computation of Low-rank Matrix Approximations. J. ACM, 54(2). DOI.
Alaoui, A. E., & Mahoney, M. W.(2014) Fast Randomized Kernel Methods With Statistical Guarantees. arXiv:1411.0306 [cs, Stat].
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.
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.
Erichson, N. B., Voronin, S., Brunton, S. L., & Kutz, J. N.(2016) Randomized Matrix Decompositions using R. arXiv:1608.02148 [cs, Stat].
Halko, N., Martinsson, P.-G., & Tropp, J. A.(2009) Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. arXiv:0909.4061 [math].
Kumar, N. K., & Shneider, J. (2016) Literature survey on low rank approximation of matrices. arXiv:1606.06511 [cs, Math].
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.
Mahoney, M. W.(2010) Randomized Algorithms for Matrices and Data. Foundations and Trends® in Machine Learning, 3(2), 123–224. DOI.
Martinsson, P.-G. (2016) Randomized methods for matrix computations and analysis of high dimensional data. arXiv:1607.01649 [math].
Martinsson, P.-G., & Voronin, S. (2015) A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices. arXiv:1503.07157 [math].
Sindhwani, V., Avron, H., Mahoney, M. W., & EDU, B. (2014) Quasi-Monte Carlo feature maps for shift-invariant kernels.
Tropp, J. A.(2015) An Introduction to Matrix Concentration Inequalities. arXiv:1501.01571 [cs, Math, Stat].
Voronin, S., & Martinsson, P.-G. (2014) Efficient Algorithms for CUR and Interpolative Matrix Decompositions. arXiv:1412.8447 [cs, Math].
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].
Wang, S. (2015) A Practical Guide to Randomized Matrix Computations with MATLAB Implementations. arXiv:1505.07570 [cs].
Yang, J., Meng, X., & Mahoney, M. W.(2015) Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments. arXiv:1502.03032 [cs, Math, Stat].
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).
Zhou, T., & Tao, D. (2011) Godec: Randomized low-rank & sparse matrix decomposition in noisy case.