65 citations · 262 across the 38 of their papers we have counts for
4 papers · 2 filters
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson, Huy L. Nguyen
An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it h…
Sparsity Lower Bounds for Dimensionality Reducing Maps
Jelani Nelson, Huy L. Nguyen
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the JL lemma which states that for any set of n vectors in…
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, Mary Wootters
In compressed sensing, the "restricted isometry property" (RIP) is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x in C^d from m linear measur…
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
Jelani Nelson, Huy Nguyen, David P. Woodruff
We study classic streaming and sparse recovery problems using deterministic linear sketches, including l1/l1 and linf/l1 sparse recovery problems (the latter also being known as l1…