Lower bounds for local versions of dimension reductions
type: Item
instance of: scholarly article
title: Lower bounds for local versions of dimension reductions
zbMATH Open document ID: 1171.46008
author: Gideon Schechtman
author: Adi Shraibman
published in: Discrete \& Computational Geometry
publication date: 2009-05-13T00:00:00Z
review text: The paper is devoted to the following problem: given a graph \(G = (V ,E)\) on \(V = [n] = {1, 2, \dots, n}\), \(\varepsilon > 0\) and vectors \(x_1,\dots , x_n\in\mathbb{R}^n\), what is the minimal \(k\in \mathbb{N}\) such that there are vectors \(y_1,\dots, y_n\in \mathbb{R}^k\) satisfying \((1-\varepsilon)\| x_i -x_j\| \leq \| y_i -y_j\| \leq (1+\varepsilon)\| x_i-x_j\| \) for every \((i,j)\in E\)? In the case when \(G\) is the complete graph \(K_n\) on \(n\) vertices, this problem is addressed by the well-known result of \textit{W.\,B.\thinspace Johnson} and \textit{J.\,Lindenstrauss} [Contemp.\ Math.\ 26, 189--206 (1984; Zbl 0539.46017)] which asserts that in this case \(k\) can be taken to be \(O(\log n/(\varepsilon^2))\) and an example due to \textit{N.\,Alon} [Combin.\ Probab.\ Comput.\ 18, No.\,1--2, 3--15 (2009; doi:10.1017/S0963548307008917)] which shows that, for \(K_n\), this is basically the best possible; in this example, \(k\) must be \(\Omega(\log n/(\varepsilon^2 \log(1/\varepsilon)))\). The authors are mostly interested in the case when \(G\) is the graph induced by the \(m\) nearest neighbors of \(x_1,\dots , x_n\). That is, \((i,j)\in E\) if and only if \(x_j\) is among the \(m\) nearest neighbors to \(x_i\) or \(x_i\) is among the \(m\) nearest neighbors to \(x_j\). The problem in this case was suggested by [\textit{I.\,Abraham, Y.\,Batal} and \textit{O.\,Neiman}, in: Proceedings of the 39th annual ACM symposium on theory of computing (STOC'07), San Diego, June 11--13, 2007, 631--640 (2007; Zbl 1232.68160)], it is motivated by several applications discussed in their paper. The authors find an example (with \(m = 3\)) such that for each sufficiently small \(\varepsilon > 0\), \(k\) still needs to be \(\Omega(\log n)\). The authors do not obtain good dependence on \(\varepsilon\). More precise results are obtained in the case when we additionally require that the mapping \(x_i\mapsto y_i\) preserves the set of nearest neighbors.
Mathematics Subject Classification ID: 46B07
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 54E40
zbMATH DE Number: 5553467
zbMATH Keywords: Johnson-Lindenstrauss lemma
zbMATH Keywords: dimension reduction
zbMATH Keywords: nearest neighbors
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
full work available at URL: s00454-008-9068-8
OpenAlex ID: W2080339044
cites work: Local embeddings of metric spaces
cites work: Perturbed Identity Matrices Have High Rank: Proof and Applications
cites work: Q4219187
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: Expander graphs and their applications
DOI: 10.1007/S00454-008-9068-8
description: scientific article; zbMATH DE number 5553467