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

- BlinkDB is a massively parallel, approximate query engine for running interactive SQL queries on large volumes of data. It allows users to trade-off query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars. To achieve this, BlinkDB uses two key ideas: (1) An adaptive optimization framework that builds and maintains a set of multi-dimensional samples from original data over time, and (2) A dynamic sample selection strategy that selects an appropriately sized sample based on a query’s accuracy and/or response time requirements […]
- Probabilistic data structures, e.g.
- Bloom filters
- Count-min sketch
- for go

## Refs

- AlMa14
- Alaoui, A. E., & Mahoney, M. W.(2014) Fast Randomized Kernel Methods With Statistical Guarantees.
*arXiv:1411.0306 [cs, Stat]*. - DrMa16
- Drineas, P., & Mahoney, M. W.(2016) RandNLA: randomized numerical linear algebra.
*Communications of the ACM*, 59(6), 80–90. DOI. - FCSR16
- Fountoulakis, K., Cheng, X., Shun, J., Roosta-Khorasani, F., & Mahoney, M. W.(2016) Exploiting Optimization for Local Graph Clustering.
*arXiv:1602.01886 [math]*. - 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]*. - LSSG14
- Lopez-Paz, D., Sra, S., Smola, A., Ghahramani, Z., & Schölkopf, B. (2014) Randomized Nonlinear Component Analysis.
*arXiv:1402.0119 [cs, Stat]*. - Maho10
- Mahoney, M. W.(2010) Randomized Algorithms for Matrices and Data.
*Foundations and Trends® in Machine Learning*, 3(2), 123–224. DOI. - MaOV09
- 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]*. - MaVo15
- Martinsson, P.-G., & Voronin, S. (2015) A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices.
*arXiv:1503.07157 [math]*. - OyTr15
- Oymak, S., & Tropp, J. A.(2015) Universality laws for randomized dimension reduction, with applications.
*arXiv:1511.09433 [cs, Math, Stat]*. - TWDB06
- 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.
- 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: Subroutines for computing partial singular value decompositions via randomized sampling on single core, 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]*. - ZhTa11
- Zhou, T., & Tao, D. (2011) Godec: Randomized low-rank & sparse matrix decomposition in noisy case.