Kasper Green Larsen

activity

20112026

most citedFast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D

48 citations · 181 across the 49 of their papers we have counts for

collaborators

Showing cs.ITShow all

2 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.IT2014★ 33 cited

The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Kasper Green Larsen, Jelani Nelson

For any $n > 1$ and $0 < ε < 1/2$ , we show the existence of an $n^{O (1)}$ -point subset $X$ of $R^{n}$ such that any linear map from $(X, ℓ_{2})$ to $ℓ_{2}^{m}$ with disto…