Kis Torzítás Lemma

A kis torzítási lemma (más néven Johnson-Lindenstrauss lemma ) kimondja, hogy egy többdimenziós térben egy ponthalmaz leképezhető egy sokkal kisebb térre oly módon, hogy a pontok közötti távolságok szinte változatlanok maradnak. Sőt, egy ilyen leképezés megtalálható az ortogonális vetületek között is . $n$ $n$

A lemma lehetővé teszi a többdimenziós térben lévő pontok által reprezentált adatok tömörítését, és ami még fontosabb, az adatok méretének csökkentését jelentős információvesztés nélkül.

A lemmát William Johnson és Yoram Lindenstrauss bizonyította . [egy]

Megfogalmazás

Hadd . Ekkor bármely és ponthalmazra létezik olyan lineáris leképezés , hogy $0<\varepszilon <1$ $x$ $n$ ${\mathbb R}^{N}$ ${\displaystyle m>{\tfrac {8\cdot \ln n}{\varepsilon ^{2))))$ ${\displaystyle f:\mathbb {R} ^{N}\jobbra \mathbb {R} ^{m))$

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

mindenkinek . $u,v\in X$

Ráadásul egy véletlenszerű merőleges vetítés egy -dimenziós altérre pozitív valószínűséggel teljesíti a feltételt. $f$ $m$

A bizonyítékokról

Az egyik bizonyíték a mérték koncentrációs tulajdonságán alapul .

Alternatív megfogalmazás

Egy rokon lemma a Johnson-Lindenstrauss eloszlási lemma. Ez az eloszlási lemma kimondja, hogy bármely 0 < ε , δ < 1/2 és d pozitív egész esetén létezik egy R k × d eloszlás , amelyből az A mátrixot úgy nyerjük ki , hogy k = O esetén ( ε −2 log(1/ δ ) )) és bármely x ∈ R d egységnyi hosszúságú vektorra igaz a következő állítás [2]

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

A megfelelő A mátrixokat Johnson-Lindenstrauss mátrixoknak ( JL mátrixoknak ) nevezik . Ez a lemma lényegében egy többváltozós eloszlás mátrixvetületének közelítésének pontosságát jellemzi.

A lemma disztributív változatának az eredeti megfelelőjével való kapcsolatát úgy kaphatjuk meg, hogy X -ben adunk meg és bizonyos u , v párokat . ${\displaystyle x=(uv)/\|uv\|_{2))$ $\delta <1/n^{2}$

A jelzett lemmák nagyon fontos eredménye az alacsonyabb dimenziójú vetületek beszerzésének lehetősége, de szükséges, hogy az ilyen vetületek a lehető legrövidebb időn belül elérhetők legyenek. Az A mátrix x vektorral való megszorzása a disztributív lemmában O ( kd ) időt vesz igénybe . Ezért számos tanulmányt végeztek olyan eloszlások meghatározására, amelyeknél a mátrix-vektor szorzat O ( kd ) időnél rövidebb idő alatt kiszámítható.

2006-ban Eilon és Bernard Chazelle bevezette az úgynevezett gyors Johnson-Lindenstrauss transzformációt (BPTL) , amely lehetővé teszi a mátrix-vektor szorzat időbeni kiszámítását bármely állandó esetén . [3] ${\displaystyle d\log d+k^{2+\gamma ))$ $\gamma >0$

Speciális esetet képviselnek a tenzoros véletlen vetületek, amelyekre az x egységhosszú vektor tenzorszerkezettel rendelkezik, és a vetületi A JL mátrixok több, azonos számú független sorral rendelkező mátrix végtermékével is kifejezhetők .

Többdimenziós terek tenzor vetületei

A BPDL-ben használt tenzorvetületek ábrázolására többdimenziós esetben, két azonos sorszámú JL-mátrix kombinációjaként, V. I. Slusar által 1996-ban javasolt arcfelosztási szorzat használható . [4] [5] [6] [7] [8] [9] .

Tekintsük egy többdimenziós tér vetületeinek két JL-mátrixát: és . A végtermékük [4] [5] [6] [7] [8] a következő: ${C}\in \mathbb {R} ^{3\times 3}$ ${D}\in \mathbb {R} ^{3\times 3}$ ${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].

Az így definiált JL mátrixok kevesebb véletlenszerű bitet használnak, és gyorsan megszorozhatók tenzorszerkezetű vektorokkal, köszönhetően a következő azonosságnak [6] :

(\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]

hol van az elemenkénti Hadamard szorzat . $\circ$

Az A vetületi mátrixról a végtermékre való átmenet lehetővé teszi, hogy az eredeti szorzást a Hadamard szorzattal helyettesítsük, amely kisebb dimenziójú mátrixokkal operál. Ebben az összefüggésben a végtermék ötletét 2010-ben [10] használták a különböző adatvédelmi probléma megoldására . Emellett számos más lineáris algebrai algoritmusban is alkalmaztak hasonló számításokat a kernel módszer hatékony megvalósítására [11] .

2020-ban kimutatták, hogy kis dimenziós vetületek létrehozásához a végtermékben elegendő bármilyen véletlenszerű, független sorokat tartalmazó mátrixot használni, azonban nagyobb garanciák a kis torzítások elérésére nagydimenziós terekben valós Gauss-Johnson segítségével érhetők el. -Lindenstrauss mátrixok [12] .

Ha a mátrixok függetlenek, elemeket vagy Gauss-mátrixokat tartalmaznak, akkor az összevont mátrix akkor teljesíti a Johnson-Lindenstrauss-eloszlás lemmáját, ha a sorok száma legalább ${\displaystyle C_{1},C_{2},\dots ,C_{c))$ $\pm 1$ ${\displaystyle C_{1}\bullet \dots \bullet C_{c))$

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

[12] .

Nagy esetén a Johnson-Lindenstrauss-eloszlási lemma szigorúan teljesül, míg a közelítési hiba alsó korlátja exponenciális függő [12] . A JL mátrixok alternatív konstrukcióit javasolják ennek a korlátozásnak a megkerülésére [12] . $\epsilon$ ${\displaystyle (\log 1/\delta )^{c))$

Jegyzetek

↑ Johnson, William B. és Lindenstrauss, Joram (1984), Konferencia a modern elemzésben és valószínűségben (New Haven, Conn., 1982) , in Beals, Richard; Beck, Anatole & Bellow, Alexandra et al., Conference in modern analysis and probability (New Haven, Conn., 1982) , 1. kötet. 26, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 189–206, ISBN 0-8218-5030-X , DOI 10.1090/conm/026/737400 .
↑ Johnson, William B. és Lindenstrauss, Joram (1984), Konferencia a modern elemzésben és valószínűségben (New Haven, Conn., 1982) , in Beals, Richard; Beck, Anatole & Bellow, Alexandra et al., Conference in modern analysis and probability (New Haven, Conn., 1982) , 1. kötet. 26, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 189–206 , ISBN 0-8218-5030-X , doi : 10.1090/conm/026/737400 , < https://archive.org/details/conferenceinmode0000conf/page/189 > .
↑ Ailon, Nir & Chazelle, Bernard (2006), Proceedings of the 38th Annual ACM Symposium on Theory of Computing , Proceedings of the 38th Annual ACM Symposium on Theory of Computing , New York: ACM Press, pp. 557–563, ISBN 1-59593-134-1 , DOI 10.1145/1132516.1132597 .
↑ 1 2 Slyusar, VI (1996. december 27.). „Végtermékek mátrixokban radar alkalmazásokban” (PDF) . Radioelectronics and Communications Systems. – 1998, Vol. 41; 3. szám : 50-53. Archivált (PDF) az eredetiből ekkor: 2020-07-27 . Letöltve: 2020-07-30 . Elavult használt paraméter |deadlink=( súgó )
↑ 1 2 Slyusar, VI (1997-05-20). „A digitális antennatömb analitikai modellje arcfelosztó mátrixtermékek alapján” (PDF) . Proc. ICATT-97, Kijev : 108-109. Archivált (PDF) az eredetiből ekkor: 2020-01-25 . Letöltve: 2020-07-30 . Elavult használt paraméter |deadlink=( súgó )
↑ 1 2 3 Slyusar, VI (1997-09-15). „Új mátrixműveletek termék radarok alkalmazásához” (PDF) . Proc. Az elektromágneses és akusztikus hullámelmélet direkt és inverz problémái (DIPED-97), Lviv. : 73-74. Archivált (PDF) az eredetiből ekkor: 2020-01-25 . Letöltve: 2020-07-30 . Elavult használt paraméter |deadlink=( súgó )
↑ 1 2 Slyusar, VI (1998. március 13.). „A mátrixok arctermékeinek családja és tulajdonságai” (PDF) . Kibernetika és rendszerelemzés C/C of Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Archivált (PDF) az eredetiből ekkor: 2020-01-25 . Letöltve: 2020-07-30 . Elavult használt paraméter |deadlink=( súgó )
↑ 1 2 Slyusar, VI (2003). „A nem azonos csatornákkal rendelkező digitális antennatömbök modelljei mátrixainak általánosított arcszorzatai” (PDF) . Rádióelektronika és kommunikációs rendszerek . 46 (10): 9-17.
↑ Anna Esteve, Eva Boj és Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics – Theory and Methods, 38:19, P. 3501 [1] Archiválva : 2021. április 26. a Wayback Machine -nél
↑ Kasiviswanathan, Shiva Prasad és mások. "A privát kiadású kontingenciatáblázatok ára és a véletlenszerű mátrixok spektrumai korrelált sorokkal." Proceedings of the negyvenkettedik ACM szimpózium on Theory of Computing. 2010.
↑ Woodruff, David P. "A vázlatkészítés mint eszköz a numerikus lineáris algebrához." Elméleti Számítástudomány 10.1-2 (2014): 1-157.
↑ 1 2 3 4 Ahle, Thomas; Kapralov, Michael; Knudsen, Jacob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Magas fokú polinom kernelek önfeledt vázlata . ACM-SIAM Szimpózium a diszkrét algoritmusokról. Számítógépek Szövetsége. DOI : 10,1137/1,9781611975994,9 .

Irodalom

Achlioptas, Dimitris (2003), Adatbázis-barát véletlen vetületek: Johnson-Lindenstrauss bináris érmékkel , Journal of Computer and System Sciences 66(4): 671–687 , DOI 10.1016/S0022-0000(03)40025 A PODC 2001-en korábban megjelent cikk folyóiratváltozata.
Dasgupta, Sanjoy és Gupta, Anupam (2003), Johnson és Lindenstrauss tételének elemi bizonyítása , Random Structures & Algorithms 22. kötet (1): 60–65, doi : 10.1002/rsa.10073 , < http:// cseweb.ucsd.edu/~dasgupta/papers/jl.pdf > .
Landweber, Péter; Lázár, Emanuel; Patel, Neel (2015), " A folytonos térképek szálátmérőjéről ".