The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Jelani Nelson - One of the best experts on this subject based on the ideXlab platform.
-
Optimality of the Johnson-Lindenstrauss Lemma
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any d, n ≥ 2 and 1/(min{n, d})0.4999
-
optimality of the johnson Lindenstrauss lemma
arXiv: Information Theory, 2016Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} < \varepsilon<1$, we show the existence of a set of $n$ vectors $X\subset \mathbb{R}^d$ such that any embedding $f:X\rightarrow \mathbb{R}^m$ satisfying $$ \forall x,y\in X,\ (1-\varepsilon)\|x-y\|_2^2\le \|f(x)-f(y)\|_2^2 \le (1+\varepsilon)\|x-y\|_2^2 $$ must have $$ m = \Omega(\varepsilon^{-2} \lg n). $$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of $\varepsilon$ of interest, since there is always an isometric embedding into dimension $\min\{d, n\}$ (either the identity map, or projection onto $\mathop{span}(X)$). Previously such a lower bound was only known to hold against linear maps $f$, and not for such a wide range of parameters $\varepsilon, n, d$ [LN16]. The best previously known lower bound for general $f$ was $m = \Omega(\varepsilon^{-2}\lg n/\lg(1/\varepsilon))$ [Wel74, Lev83, Alo03], which is suboptimal for any $\varepsilon = o(1)$.
-
Optimality of the Johnson-Lindenstrauss Lemma
arXiv: Information Theory, 2016Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} < \varepsilon
-
Toward a unified theory of sparse dimensionality reduction in Euclidean space
Geometric and Functional Analysis, 2015Co-Authors: Jean Bourgain, Sjoerd Dirksen, Jelani NelsonAbstract:Let $${\Phi\in\mathbb{R}^{m\times n}}$$ Φ ∈ R m × n be a sparse Johnson–Lindenstrauss transform (Kane and Nelson in J ACM 61(1):4, 2014 ) with s non-zeroes per column. For a subset T of the unit sphere, $${\varepsilon\in(0,1/2)}$$ ε ∈ ( 0 , 1 / 2 ) given, we study settings for m , s required to ensure $$\mathop{\mathbb{E}}_\Phi \sup_{x\in T}\left|\|\Phi x\|_2^2 - 1\right| < \varepsilon,$$ E Φ sup x ∈ T ‖ Φ x ‖ 2 2 - 1 < ε , i.e. so that $${\Phi}$$ Φ preserves the norm of every $${x\in T}$$ x ∈ T simultaneously and multiplicatively up to $${1+\varepsilon}$$ 1 + ε . We introduce a new complexity parameter, which depends on the geometry of T , and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon’s theorem, which was concerned with a dense $${\Phi}$$ Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson–Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson–Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.
-
the johnson Lindenstrauss lemma is optimal for linear dimensionality reduction
arXiv: Information Theory, 2014Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any $n>1$ and $0<\varepsilon<1/2$, we show the existence of an $n^{O(1)}$-point subset $X$ of $\mathbb{R}^n$ such that any linear map from $(X,\ell_2)$ to $\ell_2^m$ with distortion at most $1+\varepsilon$ must have $m = \Omega(\min\{n, \varepsilon^{-2}\log n\})$. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma, improving the previous lower bound of Alon by a $\log(1/\varepsilon)$ factor.
Kasper Green Larsen - One of the best experts on this subject based on the ideXlab platform.
-
on using toeplitz and circulant matrices for johnson Lindenstrauss transforms
Algorithmica, 2020Co-Authors: Casper Benjamin Freksen, Kasper Green LarsenAbstract:The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping \(f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m\) such that for any vector \(x \in {\mathbb {R}}^n\), f preserves its norm to within \((1 {\pm } \varepsilon )\) with probability \(1 - \delta \) if \(m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))\). Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal \(m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))\) dimensions has an embedding time of \({\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))\). An exciting approach towards improving this, due to Hinrichs and Vybiral, is to use a random \(m \times n\) Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in \({\mathcal {O}}(n \lg m)\) time. The big question is of course whether \(m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))\) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybiral shows that \(m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))\) dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring \(m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))\) for the Toeplitz approach to work.
-
On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms
Algorithmica, 2019Co-Authors: Casper Benjamin Freksen, Kasper Green LarsenAbstract:The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping $$f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m$$ f : R n → R m such that for any vector $$x \in {\mathbb {R}}^n$$ x ∈ R n , f preserves its norm to within $$(1 {\pm } \varepsilon )$$ ( 1 ± ε ) with probability $$1 - \delta $$ 1 - δ if $$m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))$$ m = Θ ( ε - 2 lg ( 1 / δ ) ) . Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal $$m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))$$ m = O ( ε - 2 lg ( 1 / δ ) ) dimensions has an embedding time of $${\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))$$ O ( n lg n + ε - 2 lg 3 ( 1 / δ ) ) . An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random $$m \times n$$ m × n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in $${\mathcal {O}}(n \lg m)$$ O ( n lg m ) time. The big question is of course whether $$m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))$$ m = O ( ε - 2 lg ( 1 / δ ) ) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that $$m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))$$ m = O ( ε - 2 lg 2 ( 1 / δ ) ) dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring $$m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))$$ m = Ω ( ε - 2 lg 2 ( 1 / δ ) ) for the Toeplitz approach to work.
-
on using toeplitz and circulant matrices for johnson Lindenstrauss transforms
arXiv: Functional Analysis, 2017Co-Authors: Casper Benjamin Freksen, Kasper Green LarsenAbstract:The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given $N$, for any set of $N$ vectors $X \subset \mathbb{R}^n$, there exists a mapping $f : X \to \mathbb{R}^m$ such that $f(X)$ preserves all pairwise distances between vectors in $X$ to within $(1 \pm \varepsilon)$ if $m = O(\varepsilon^{-2} \lg N)$. Much effort has gone into developing fast embedding algorithms, with the Fast Johnson-Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal $m = O(\varepsilon^{-2}\lg N)$ dimensions has an embedding time of $O(n \lg n + \varepsilon^{-2} \lg^3 N)$. An exciting approach towards improving this, due to Hinrichs and Vybiral, is to use a random $m \times n$ Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in $O(n \lg m)$ time. The big question is of course whether $m = O(\varepsilon^{-2} \lg N)$ dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybiral shows that $m = O(\varepsilon^{-2}\lg^2 N)$ dimensions suffices. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exists a set of $N$ vectors requiring $m = \Omega(\varepsilon^{-2} \lg^2 N)$ for the Toeplitz approach to work.
-
Optimality of the Johnson-Lindenstrauss Lemma
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any d, n ≥ 2 and 1/(min{n, d})0.4999
-
optimality of the johnson Lindenstrauss lemma
arXiv: Information Theory, 2016Co-Authors: Kasper Green Larsen, Jelani NelsonAbstract:For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} < \varepsilon<1$, we show the existence of a set of $n$ vectors $X\subset \mathbb{R}^d$ such that any embedding $f:X\rightarrow \mathbb{R}^m$ satisfying $$ \forall x,y\in X,\ (1-\varepsilon)\|x-y\|_2^2\le \|f(x)-f(y)\|_2^2 \le (1+\varepsilon)\|x-y\|_2^2 $$ must have $$ m = \Omega(\varepsilon^{-2} \lg n). $$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of $\varepsilon$ of interest, since there is always an isometric embedding into dimension $\min\{d, n\}$ (either the identity map, or projection onto $\mathop{span}(X)$). Previously such a lower bound was only known to hold against linear maps $f$, and not for such a wide range of parameters $\varepsilon, n, d$ [LN16]. The best previously known lower bound for general $f$ was $m = \Omega(\varepsilon^{-2}\lg n/\lg(1/\varepsilon))$ [Wel74, Lev83, Alo03], which is suboptimal for any $\varepsilon = o(1)$.
Edo Liberty - One of the best experts on this subject based on the ideXlab platform.
-
an almost optimal unrestricted fast johnson Lindenstrauss transform
Symposium on Discrete Algorithms, 2011Co-Authors: Nir Ailon, Edo LibertyAbstract: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 remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Veshynin [2008] for sparse reconstruction which uses Dudley’s theorem for bounding Gaussian processes. Our main result states that any set of N = exp(O(n)) real vectors in n dimensional space can be linearly mapped to a space of dimension k = O(log N polylog(n)), while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time O(n log n) on each vector. This improves on the best known bound N = exp(O(n1/2)) achieved by Ailon and Liberty [2009] and N = exp(O(n1/3)) by Ailon and Chazelle [2010]. The dependence in the distortion constant however is suboptimal, and since the publication of an early version of the work, the gap between upper and lower bounds has been considerably tightened obtained by Krahmer and Ward [2011]. For constant distortion, this settles the open question posed by these authors up to a polylog(n) factor while considerably simplifying their constructions.
-
almost optimal unrestricted fast johnson Lindenstrauss transform
arXiv: Data Structures and Algorithms, 2010Co-Authors: Nir Ailon, Edo LibertyAbstract: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 remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Vershynin for sparse reconstruction which uses Dudley's theorem for bounding Gaussian processes. Our main result states that any set of $N = \exp(\tilde{O}(n))$ real vectors in $n$ dimensional space can be linearly mapped to a space of dimension $k=O(\log N\polylog(n))$, while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time $O(n\log n)$ on each vector. This improves on the best known $N = \exp(\tilde{O}(n^{1/2}))$ achieved by Ailon and Liberty and $N = \exp(\tilde{O}(n^{1/3}))$ by Ailon and Chazelle. The dependence in the distortion constant however is believed to be suboptimal and subject to further investigation. For constant distortion, this settles the open question posed by these authors up to a $\polylog(n)$ factor while considerably simplifying their constructions.
Daniel M Kane - One of the best experts on this subject based on the ideXlab platform.
-
sparser johnson Lindenstrauss transforms
Journal of the ACM, 2014Co-Authors: Daniel M Kane, Jelani NelsonAbstract:We give two different and simple constructions for dimensionality reduction in e2 via linear mappings that are sparse: only an O(e)-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1 + e with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where e2 dimensionality reduction is used.
-
sparser johnson Lindenstrauss transforms
Symposium on Discrete Algorithms, 2012Co-Authors: Daniel M Kane, Jelani NelsonAbstract:We give two different Johnson-Lindenstrauss distributions, each with column sparsity s = Θ(e−1 log(1/δ)) and embedding into optimal dimension k = O(e−2 log(1/δ)) to achieve distortion 1±e with probability 1−δ. That is, only an O(e)-fraction of entries are non-zero in each embedding matrix in the supports of our distributions. These are the first distributions to provide o(k) sparsity for all values of e,δ. Previously the best known construction obtained s = Θ(e-1 log2 (1/δ))1 [Dasgupta-Kumar-Sarlos, STOC 2010]2. In addition, one of our distributions can be sampled from a seed of O(log(1/δ) log d) uniform random bits. Some applications that use Johnson-Lindenstrauss embeddings as a black box, such as those in approximate numerical linear algebra ([Sarlos, FOCS 2006], [Clarkson-Woodruff, STOC 2009]), require exponentially small δ. Our linear dependence on log(1/δ) in the sparsity is thus crucial in these applications to obtain speedup.
-
SODA - Sparser Johnson-Lindenstrauss transforms
2012Co-Authors: Daniel M Kane, Jelani NelsonAbstract:We give two different Johnson-Lindenstrauss distributions, each with column sparsity s = Θ(e−1 log(1/δ)) and embedding into optimal dimension k = O(e−2 log(1/δ)) to achieve distortion 1±e with probability 1−δ. That is, only an O(e)-fraction of entries are non-zero in each embedding matrix in the supports of our distributions. These are the first distributions to provide o(k) sparsity for all values of e,δ. Previously the best known construction obtained s = Θ(e-1 log2 (1/δ))1 [Dasgupta-Kumar-Sarlos, STOC 2010]2. In addition, one of our distributions can be sampled from a seed of O(log(1/δ) log d) uniform random bits. Some applications that use Johnson-Lindenstrauss embeddings as a black box, such as those in approximate numerical linear algebra ([Sarlos, FOCS 2006], [Clarkson-Woodruff, STOC 2009]), require exponentially small δ. Our linear dependence on log(1/δ) in the sparsity is thus crucial in these applications to obtain speedup.
-
almost optimal explicit johnson Lindenstrauss families
International Workshop and International Workshop on Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques, 2011Co-Authors: Daniel M Kane, Raghu Meka, Jelani NelsonAbstract:The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson-Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 e] ≤ δ, with seed-length r = O(log d + log(1/δ) ċ log (log(1/δ/e)). In particular, for δ = 1/ poly(d) and fixed e > 0, we obtain seed-length O((log d)(log log d)). Previous constructions required Ω(log2 d) random bits to obtain polynomially small error. We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/δ)/e2) on the embedding dimension. Previously, Jayram and Woodruff [10] used communication complexity techniques to show a similar bound.
-
APPROX-RANDOM - Almost optimal explicit Johnson-Lindenstrauss families
Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques, 2011Co-Authors: Daniel M Kane, Raghu Meka, Jelani NelsonAbstract:The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson-Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 e] ≤ δ, with seed-length r = O(log d + log(1/δ) ċ log (log(1/δ/e)). In particular, for δ = 1/ poly(d) and fixed e > 0, we obtain seed-length O((log d)(log log d)). Previous constructions required Ω(log2 d) random bits to obtain polynomially small error. We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/δ)/e2) on the embedding dimension. Previously, Jayram and Woodruff [10] used communication complexity techniques to show a similar bound.
Nir Ailon - One of the best experts on this subject based on the ideXlab platform.
-
an almost optimal unrestricted fast johnson Lindenstrauss transform
Symposium on Discrete Algorithms, 2011Co-Authors: Nir Ailon, Edo LibertyAbstract: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 remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Veshynin [2008] for sparse reconstruction which uses Dudley’s theorem for bounding Gaussian processes. Our main result states that any set of N = exp(O(n)) real vectors in n dimensional space can be linearly mapped to a space of dimension k = O(log N polylog(n)), while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time O(n log n) on each vector. This improves on the best known bound N = exp(O(n1/2)) achieved by Ailon and Liberty [2009] and N = exp(O(n1/3)) by Ailon and Chazelle [2010]. The dependence in the distortion constant however is suboptimal, and since the publication of an early version of the work, the gap between upper and lower bounds has been considerably tightened obtained by Krahmer and Ward [2011]. For constant distortion, this settles the open question posed by these authors up to a polylog(n) factor while considerably simplifying their constructions.
-
almost optimal unrestricted fast johnson Lindenstrauss transform
arXiv: Data Structures and Algorithms, 2010Co-Authors: Nir Ailon, Edo LibertyAbstract: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 remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Vershynin for sparse reconstruction which uses Dudley's theorem for bounding Gaussian processes. Our main result states that any set of $N = \exp(\tilde{O}(n))$ real vectors in $n$ dimensional space can be linearly mapped to a space of dimension $k=O(\log N\polylog(n))$, while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time $O(n\log n)$ on each vector. This improves on the best known $N = \exp(\tilde{O}(n^{1/2}))$ achieved by Ailon and Liberty and $N = \exp(\tilde{O}(n^{1/3}))$ by Ailon and Chazelle. The dependence in the distortion constant however is believed to be suboptimal and subject to further investigation. For constant distortion, this settles the open question posed by these authors up to a $\polylog(n)$ factor while considerably simplifying their constructions.
