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 …

An oblivious subspace embedding (OSE) given some parameters ε, d is a distribution D over
matrices Π∈ R m× n such that for any linear subspace W⊆ R n with dim (W)= d, P Π~ D (∀ …

We give two different and simple constructions for dimensionality reduction in ℓ 2 via linear
mappings that are sparse: only an O (ε)-fraction of entries in each column of our embedding …

Consider an m*N matrix Φ with the restricted isometry property of order k and level δ; that is,
the norm of any k-sparse vector in R^N is preserved to within a multiplicative factor of 1±δ …

The problems of random projections and sparse reconstruction have much in common and
individually received much attention. Surprisingly, until now they progressed in parallel and …

Let Φ∈ Rm xn be a sparse Johnson-Lindenstrauss transform [52] with column sparsity s.
For a subset T of the unit sphere and ε∈(0, 1/2), we study settings for m, s to ensure EΦ …

We give a space-optimal streaming algorithm with update time O (log2 (1/ε) loglog (1/ε)) for
approximating the pth frequency moment, 0< p< 2, of a length-n vector updated in a data …

This survey article considers methods and algorithms for fast estimation of data
distance/similarity measures from formed real-valued vectors of small dimension. The …

In distributed statistical learning, $ N $ samples are split across $ m $ machines and a
learner wishes to use minimal communication to learn as well as if the examples were on a …

For every n-point subset X of Euclidean space and target distortion 1+ eps for 0< eps< 1, the
Sparse Johnson Lindenstrauss Transform (SJLT) of (Kane, Nelson, J. ACM 2014) provides a …