The Living Thing / Notebooks : Randomised algorithms

Sacrificing precision/certainty for speed, using randomness.

Some sub-fields of this are big enough to have their own sections:

Compressed sensing, Monte Carlo methods, particle filters, and random features, stochastic gradient descent monte carlo methods for particular sampling-of-functionals…

Randomised Linear Algebra

Michael Mahoney gave a course on this.

Other computer science structures


Alaoui, A. E., & Mahoney, M. W.(2014) Fast Randomized Kernel Methods With Statistical Guarantees. arXiv:1411.0306 [cs, Stat].
Drineas, P., & Mahoney, M. W.(2016) RandNLA: randomized numerical linear algebra. Communications of the ACM, 59(6), 80–90. DOI.
Fountoulakis, K., Cheng, X., Shun, J., Roosta-Khorasani, F., & Mahoney, M. W.(2016) Exploiting Optimization for Local Graph Clustering. arXiv:1602.01886 [math].
Halko, N., Martinsson, P.-G., & Tropp, J. A.(2009) Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. arXiv:0909.4061 [math].
Lopez-Paz, D., Sra, S., Smola, A., Ghahramani, Z., & Schölkopf, B. (2014) Randomized Nonlinear Component Analysis. arXiv:1402.0119 [cs, Stat].
Mahoney, M. W.(2010) Randomized Algorithms for Matrices and Data. Foundations and Trends® in Machine Learning, 3(2), 123–224. DOI.
Mahoney, M. W., Orecchia, L., & Vishnoi, N. K.(2009) A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally. arXiv:0912.0681 [cs].
Martinsson, P.-G., & Voronin, S. (2015) A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices. arXiv:1503.07157 [math].
Oymak, S., & Tropp, J. A.(2015) Universality laws for randomized dimension reduction, with applications. arXiv:1511.09433 [cs, Math, Stat].
Tropp, J. A., Wakin, M. B., Duarte, M. F., Baron, D., & Baraniuk, R. G.(2006) Random Filters for Compressive Sampling and Reconstruction. In Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (Vol. 3, pp. 872–875). DOI.
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: Subroutines for computing partial singular value decompositions via randomized sampling on single core, 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].
Zhou, T., & Tao, D. (2011) Godec: Randomized low-rank & sparse matrix decomposition in noisy case.