Low-rank matrix approximations, such as the truncated singular value decomposition and
the rank-revealing QR decomposition, play a central role in data analysis and scientific …

Low rank approximation of matrices has been well studied in literature. Singular value
decomposition, QR decomposition with column pivoting, rank revealing QR factorization …

This survey describes probabilistic algorithms for linear algebraic computations, such as
factorizing matrices and solving linear systems. It focuses on techniques that have a proven …

This survey highlights the recent advances in algorithms for numerical linear algebra that
have come from the technique of linear sketching, whereby given a matrix, one first …

This tutorial text gives a unifying perspective on machine learning by covering both
probabilistic and deterministic approaches-which are based on optimization techniques …

We design a new distribution over m× n matrices S so that, for any fixed n× d matrix A of rank
r, with probability at least 9/10,∥ SAx∥ 2=(1±ε)∥ Ax∥ 2 simultaneously for all x∈ R d …

Randomized algorithms for very large matrix problems have received a great deal of
attention in recent years. Much of this work was motivated by problems in large-scale data …

We develop and analyze a method to reduce the size of a very large set of data points in a
high-dimensional Euclidean space R^d to a small set of weighted points such that the result …

We show how to approximate a data matrix A with a much smaller sketch~ A that can be
used to solve a general class of constrained k-rank approximation problems to within (1+ ε) …

We study the problem of estimating the trace of a matrix A that can only be accessed through
matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which …