en>Tonyxty: /* An illustrative example: a monoidal category */Removed link in title

2014-12-03T06:09:17Z

An illustrative example: a monoidal category: Removed link in title

en>AnomieBOT: Dating maintenance tags: {{Technical}}

2012-06-07T13:34:43Z

Dating maintenance tags: {{Technical}}

New page

In mathematics, the '''Johnson–Lindenstrauss lemma''' is a result named after [[William B. Johnson (mathematician)|William B. Johnson]] and [[Joram Lindenstrauss]] concerning low-distortion [[embedding]]s of points from high-dimensional into low-dimensional [[Euclidean space]]. The lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. The map used for the embedding is at least [[Lipschitz continuity|Lipschitz]], and can even be taken to be an [[orthogonal projection]].

The lemma has uses in [[compressed sensing]], [[manifold learning]], [[dimensionality reduction]], and [[graph embedding]]. Much of the data stored and manipulated on computers, including text and images, can be represented as points in a high-dimensional space (see [[vector space model]] for the case of text). However, the essential algorithms for working with such data tend{{citation needed|date=December 2012}} to become bogged down very quickly as dimension increases. It is therefore desirable to reduce the dimensionality of the data in a way that preserves its relevant structure. The Johnson–Lindenstrauss lemma is a classic result in this vein.

Also the lemma is tight up to a factor log(1/''ε''), i.e. there exists a set of points of size ''m'' that needs dimension

: <math> \Omega\left(\frac{\log(m)}{\varepsilon^2\log (1/\varepsilon)}\right)</math>

in order to preserve the distances between all pair of points. See 4.

== Lemma ==
Given 0 < ''ε'' < 1, a set ''X'' of ''m'' points in '''R'''''N'', and a number {{nowrap|''n'' > 8 ln(''m'') / ''ε'' 2}}, there is a linear map ''ƒ'' : '''R'''''N'' → '''R'''''n'' such that

: <math>(1-\varepsilon)\|u-v\|^2 \leq \|f(u) - f(v)\|^2 \leq (1+\varepsilon)\|u-v\|^2</math>

for all ''u'', ''v'' ∈ ''X''.

One proof of the lemma takes ''ƒ'' to be a suitable multiple of the orthogonal projection onto a random subspace of dimension ''n'' in '''R'''''N'', and exploits the phenomenon of [[concentration of measure]].

Obviously an orthogonal projection will, in general, reduce the average distance between points, but the lemma can be viewed as dealing with ''relative distances'', which do not change under scaling. In a nutshell, you roll the dice and obtain a random projection, which will reduce the average distance, and then you scale up the distances so that the average distance returns to its previous value. If you keep rolling the dice, you will, in polynomial random time, find a projection for which the (scaled) distances satisfy the lemma.

== References ==
*{{citation
| last1 = Johnson | first1 = William B. | author1-link = William B. Johnson (mathematician)| last2 = Lindenstrauss | first2 = Joram | author2-link = Joram Lindenstrauss
| contribution = Extensions of Lipschitz mappings into a Hilbert space
| doi = 10.1090/conm/026/737400
| location = Providence, RI
| mr = 737400
| pages = 189–206
| publisher = American Mathematical Society
| series = Contemporary Mathematics
| title = Conference in Modern Analysis and Probability (New Haven, Conn., 1982)
| volume = 26
| year = 1984}}.
*{{citation
| last1 = Dasgupta | first1 = Sanjoy
| last2 = Gupta | first2 = Anupam
| doi = 10.1002/rsa.10073
| issue = 1
| journal = Random Structures & Algorithms
| mr = 1943859
| pages = 60–65
| title = An elementary proof of a theorem of Johnson and Lindenstrauss
| url = http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf
| volume = 22
| year = 2003}}.
*{{citation
| last = Achlioptas | first = Dimitris
| doi = 10.1016/S0022-0000(03)00025-4
| issue = 4
| journal = [[Journal of Computer and System Sciences]]
| mr = 2005771
| pages = 671–687
| title = Database-friendly random projections: Johnson-Lindenstrauss with binary coins
| volume = 66
| year = 2003}}. Journal version of a paper previously appearing at PODC 2001.
*{{citation
| last1 = Baraniuk | first1 = Richard | author1-link = Richard Baraniuk
| last2 = Davenport | first2 = Mark
| last3 = DeVore | first3 = Ronald | author3-link = Ronald DeVore
| last4 = Wakin | first4 = Michael
| doi = 10.1007/s00365-007-9003-x
| issue = 3
| journal = [[Constructive Approximation]]
| mr = 2453366
| pages = 253–263
| title = A simple proof of the restricted isometry property for random matrices
| url = http://dsp.rice.edu/files/cs/JL_RIP.pdf
| volume = 28
| year = 2008}}.
*{{citation
| last = Alon | first = Noga | author-link = Noga Alon
| doi = 10.1016/S0012-365X(03)00227-9
| issue = 1-3
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| mr = 2025940
| pages = 31–53
| title = Problems and results in extremal combinatorics. I
| url = http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pdf
| volume = 273
| year = 2003}}.

{{DEFAULTSORT:Johnson-Lindenstrauss lemma}}
[[Category:Lemmas]]

{{geometry-stub}}

Coherence condition - Revision history

en>Tonyxty: /* An illustrative example: a monoidal category */Removed link in title

en>AnomieBOT: Dating maintenance tags: {{Technical}}