Johnson–Lindenstrauss lemma

Inom matematik är Johnson–Lindenstrauss-lemmat ett resultat uppkallat efter William B. Johnson och Joram Lindenstrauss angående lågdistorsionsinbäddningar av punkter från högdimensionellt till lågdimensionellt euklidiskt rum . Lemmat säger att en uppsättning punkter i ett högdimensionellt utrymme kan bäddas in i ett utrymme med mycket lägre dimension på ett sådant sätt att avstånden mellan punkterna nästan bevaras . Kartan som används för inbäddningen är åtminstone Lipschitz och kan till och med tas som en ortogonal projektion .

Lemmat har tillämpningar inom komprimerad avkänning , mångfaldsinlärning , dimensionsreduktion och grafinbäddning . Mycket av den data som lagras och manipuleras på datorer, inklusive text och bilder, kan representeras som punkter i ett högdimensionellt utrymme (se vektorrumsmodellen för text). De väsentliga algoritmerna för att arbeta med sådan data tenderar dock att fastna mycket snabbt när dimensionen ökar. Det är därför önskvärt att reducera dimensionaliteten hos datan på ett sätt som bevarar dess relevanta struktur. Johnson–Lindenstrauss lemma är ett klassiskt resultat i denna riktning.

Lemmat är också tätt upp till en konstant faktor, dvs det finns en uppsättning punkter av storleken m som behöver dimension

$\Omega \left({\frac {\log(m)}{\varepsilon ^{2}}}\right)$

för att bevara avstånden mellan alla par av punkter inom en faktor på ( $\displaystyle (1\pm \varepsilon )}$ .

Lemma

Givet $0<\varepsilon <1$ , pekar en mängd $X$ av $m\in \mathbb {Z} _{\geq 1}$ in $\mathbb {R} ^{N}$ ( $N\in \mathbb {Z} _{\geq 0}$ ), och ett heltal $n>8(\ln m)/\varepsilon ^{2}$ , det finns en linjär karta $f:\mathbb {R } ^{N}\rightarrow \mathbb {R} ^{n}$ så att

$(1-\varepsilon )\|uv\| ^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|uv\|^{2}$

för alla $u,v\in X$ .

Formeln kan ordnas om:

$${\stil 1+\varepsilon )^{-1}\|f(u)-f(v)\|^{2}\leq \|uv\|^{2}\leq (1-\varepsilon )^{-1 }\|f(u)-f(v)\|^{2}}$$

Alternativt, för alla $\epsilon \in (0,1)$ och vilket heltal som helst $n\geq 15(\ln m)/ \varepsilon ^{2}$ det finns en linjär funktion $f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}$ så att begränsningen $f|_{X}$ är $(1+\varepsilon )$ - bi-Lipschitz .

Ett bevis på lemma tar ƒ för att vara en lämplig multipel av den ortogonala projektionen på ett slumpmässigt delrum av dimensionen $n$ i $\mathbb {R} ^{N}$ och utnyttjar fenomenet koncentration av åtgärd .

En ortogonal projektion kommer i allmänhet att minska det genomsnittliga avståndet mellan punkter, men lemmat kan ses som att det handlar om relativa avstånd , som inte förändras under skalning. I ett nötskal slår du tärningen och får en slumpmässig projektion, som kommer att minska medelavståndet, och sedan skalar du upp avstånden så att medelavståndet återgår till sitt tidigare värde. Om du fortsätter att kasta tärningen kommer du, i polynomisk slumpmässig tid, att hitta en projektion för vilken de (skalerade) avstånden uppfyller lemmat.

Alternativt uttalande

Ett relaterat lemma är det fördelningsmässiga JL-lemmat. Detta lemma anger att för alla $0<\varepsilon ,\delta <1/2$ och positivt heltal $d$ , finns det en fördelning över ${\ displaystyle \mathbb {R} ^{k\times d}}$ från vilken matrisen $A$ dras så att för $k=O (\varepsilon ^{-2}\log(1/\delta ))$ och för valfri enhetslängdsvektor $x\in \mathbb {R} ^{d}$ gäller påståendet nedan .

$P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta$

Man kan få JL-lemmat från distributionsversionen genom att sätta $x=(uv)/\|uv\|_{2}$ och $\delta <1/n^{2}$ för något par u , v båda i X . Sedan följer JL-lemmat av en union bunden över alla sådana par.

Påskyndar JL-transformen

Givet A tar beräkning av matrisvektorprodukten $O(kd)$ tid. Det har gjorts en del arbete med att härleda distributioner för vilka matrisvektorprodukten kan beräknas på mindre än $O(kd)$ tid.

Det finns två huvudsakliga arbetslinjer. Den första, Fast Johnson Lindenstrauss Transform (FJLT), introducerades av Ailon och Chazelle 2006. Denna metod möjliggör beräkning av matrisvektorprodukten på bara $d\log d+k ^{2+\gamma }$ för varje konstant $\gamma >0$ .

Ett annat tillvägagångssätt är att bygga en distribution som stöds över matriser som är glesa. Denna metod tillåter att endast en $\varepsilon$ bråkdel av posterna i matrisen behålls, vilket innebär att beräkningen kan göras på bara $kd\varepsilon$ tid. Dessutom, om vektorn bara har $b$ poster som inte är noll, tar Sparse JL tid ${\displaystyle kb\varepsilon } ,$ vilket kan vara mycket mindre än d $\displaystyle d\ log d}$ tid som används av Fast JL.

Tensoriserade slumpmässiga projektioner

Det är möjligt att kombinera två JL-matriser genom att ta den så kallade ansiktsdelningsprodukten , som definieras som radernas tensorprodukter (föreslogs av V. Slyusar 1996 för radar- och digitala antenner ). Mer direkt, låt ${C}\in \mathbb {R} ^{3\times 3}$ och ${D}\in \mathbb {R } ^{3\times 3}$ vara två matriser. Då är den ansiktsdelande produkten ${C}\bullet {D}$

${C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2 }\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].$

Denna idé om tensorisering användes av Kasiviswanathan et al. 2010 för differentierad integritet .

JL-matriser som definieras så här använder färre slumpmässiga bitar och kan appliceras snabbt på vektorer som har tensorstruktur, på grund av följande identitet:

$(\mathbf {C} \ bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_ {1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array} }\right]$ ,

där $\circ$ är den elementmässiga ( Hadamard ) produkten. Sådana beräkningar har använts för att effektivt beräkna polynomkärnor och många andra linjäralgebraalgoritmer [ .

År 2020 visades det att om matriserna $C_{1},C_{2},\dots ,C_{c}$ är oberoende $\pm 1$ eller Gaussiska matriser, den kombinerade matrisen $C_{1}\bullet \dots \bullet C_{c}$ uppfyller JL-lemmat om antalet rader är minst

$O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1 }({\tfrac {1}{c}}\log 1/\delta )^{c})$ .

För stora $\epsilon$ är detta lika bra som den helt slumpmässiga Johnson-Lindenstrauss, men en matchande nedre gräns i samma papper visar att detta exponentiella beroende av ( $\displaystyle (\log 1/\delta )^{c}}$ är nödvändigt. Alternativa JL-konstruktioner föreslås för att kringgå detta.

Se även

• Slumpmässig projektion
• Begränsad isometriegenskap

Vidare läsning

•   Achlioptas, Dimitris (2003), "Databasvänliga slumpmässiga projektioner: Johnson–Lindenstrauss med binära mynt", Journal of Computer and System Sciences , 66 (4): 671–687, doi : 10.1016/S0022-0000(03)00025 4 , MR 2005771 . Journalversion av en tidning som tidigare förekommit på PODC 2001.
• Baraniuk, Richard ; Davenport, Mark; DeVore, Ronald ; Wakin, Michael (2008), "A simple proof of the restricted isometry property for random matrices", Constructive Approximation , 28 (3): 253–263, doi : 10.1007/s00365-007-9003-x , hdl /: 21831 MR 2453366 .   _
•   Dasgupta, Sanjoy; Gupta, Anupam (2003), "An elementary proof of a theorem of Johnson and Lindenstrauss" (PDF) , Random Structures & Algorithms , 22 (1): 60–65, doi : 10.1002/rsa.10073 , MR 1943855 .
• Landweber, Peter ; Lazar, Emanuel A.; Patel, Neel (2016). "Om fiberdiametrar för kontinuerliga kartor". American Mathematical Monthly . 123 : 392-397. arXiv : 1503.07597 .
• Slyusar, VI (1997-05-20). "Analytisk modell av den digitala antennuppsättningen på basis av ansiktsdelande matrisprodukter" ( PDF) . Proc. ICATT-97, Kiev : 108–109.
• Slyusar, VI (13 mars 1998). "En familj av ansiktsprodukter av matriser och dess egenskaper" (PDF) . Cybernetik och systemanalys C/C av Kibernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379–384. doi : 10.1007/BF02733426 .