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 paper describes a suite of algorithms for constructing low-rank approximations of an
input matrix from a random linear image, or sketch, of the matrix. These methods can …

This paper considers inference of causal structure in a class of graphical models called
conditional DAGs. These are directed acyclic graph (DAG) models with two kinds of …

Randomized numerical linear algebra-RandNLA, for short-concerns the use of
randomization as a resource to develop improved algorithms for large-scale linear algebra …

We modify Talagrand's generic chaining method to obtain upper bounds for all p-th
moments of the supremum of a stochastic process. These bounds lead to an estimate for the …

We study the ℓ1-low rank approximation problem, where for a given nxd matrix A and
approximation factor α≤ 1, the goal is to output a rank-k matrix  for which‖ A-Â‖ 1≤ α …

We present a new algorithm for finding a near optimal low-rank approximation of a matrix A
in O (n nz (A)) time. Our method is based on a recursive sampling scheme for computing a …

This paper argues that randomized linear sketching is a natural tool for on-the-fly
compression of data matrices that arise from large-scale scientific simulations and data …

A random m× n matrix S is an oblivious subspace embedding (OSE) with parameters є> 0,
δ∈(0, 1/3) and d≤ m≤ n, if for any d-dimensional subspace W⊆ R n, P (∀ x∈ W (1+ є)− 1 …