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 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 …

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 …

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+ ε) …

Given a set F of n positive functions over a ground set X, we consider the problem of
computing x* that minimizes the expression∑ f∈ Ff (x), over x∈ X. A typical application is …

Several results appeared that show significant reduction in time for matrix multiplication,
singular value decomposition as well as linear (lscr 2) regression, all based on data …

The Nyström method is an efficient technique to generate low-rank matrix approximations
and is used in several large-scale learning applications. A key aspect of this method is the …

Many data analysis applications deal with large matrices and involve approximating the
matrix using a small number of “components.” Typically, these components are linear …