Jelani Nelson

activity

20082023

most citedOptimal approximate matrix product in terms of stable rank

65 citations · 262 across the 38 of their papers we have counts for

collaborators

Showing 2016Show all

5 papers · 1 filter

cs.IT2016

Optimality of the Johnson-Lindenstrauss Lemma

Kasper Green Larsen, Jelani Nelson

For any integers $d, n \geq 2$ and $1/ (min {n, d})^{0.4999} < ε < 1$ , we show the existence of a set of $n$ vectors $X \subset R^{d}$ such that any embedding $f:X\…

cs.IT2016

A note on reductions between compressed sensing guarantees

Tom Morgan, Jelani Nelson

In compressed sensing, one wishes to acquire an approximately sparse high-dimensional signal $x \in R^{n}$ via $m ≪ n$ noisy linear measurements, then later approximately rec…

cs.DS2016

Heavy hitters via cluster-preserving clustering

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen +1

In turnstile $ℓ_{p}$ $ε$ -heavy hitters, one maintains a high-dimensional $x \in R^{n}$ subject to $update (i, Δ)$ causing $x_{i} \leftarrow x_{i} + Δ$ , where $i\i…

cs.DS2016★ 10 cited

BPTree: an $ℓ_{2}$ heavy hitters algorithm using constant memory

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin +3

The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list $i_{1}, i_{2}, \dots, i_{m} \in [n]$ and the goal is to…

cs.LG2016★ 8 cited

An improved analysis of the ER-SpUD dictionary learning algorithm

Jarosław Błasiok, Jelani Nelson

In "dictionary learning" we observe $Y = A X + E$ for some $Y \in R^{n \times p}$ , $A \in R^{m \times n}$ , and $X \in R^{m \times p}$ . The matrix $Y$ is observed,…

Optimality of the Johnson-Lindenstrauss Lemma

A note on reductions between compressed sensing guarantees

Heavy hitters via cluster-preserving clustering

BPTree: an ℓ2​ heavy hitters algorithm using constant memory

An improved analysis of the ER-SpUD dictionary learning algorithm

BPTree: an $ℓ_{2}$ heavy hitters algorithm using constant memory