Lemma malého zkreslení

Lemma malého zkreslení (také známé jako Johnson-Lindenstrauss lemma ) říká, že množinu bodů ve vícerozměrném prostoru lze mapovat do mnohem menšího prostoru takovým způsobem, že vzdálenosti mezi body zůstávají téměř nezměněny. Navíc takové zobrazení lze nalézt mezi ortogonálními projekcemi . $n$ $n$

Lema umožňuje komprimovat data reprezentovaná body ve vícerozměrném prostoru, a co je důležitější, zmenšit rozměr dat bez významné ztráty informace.

Toto lemma dokázali William Johnson a Yoram Lindenstrauss . [jeden]

Formulace

Nechte _ Pak pro libovolnou sadu bodů v a existuje lineární zobrazení takové, že $0<\varepsilon <1$ $X$ $n$ ${\mathbb R}^{N}$ ${\displaystyle m>{\tfrac {8\cdot \ln n}{\varepsilon ^{2))))$ ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{m))$

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

pro všechny . $u,v\in X$

Navíc náhodná ortogonální projekce do -rozměrného podprostoru splňuje podmínku s kladnou pravděpodobností. $F$ $m$

O důkazech

Jeden z důkazů je založen na koncentrační vlastnosti opatření .

Alternativní znění

Příbuzným lemmatem je Johnson-Lindenstraussovo distribuční lemma. Toto distributivní lemma říká, že pro jakékoli 0 < ε , δ < 1/2 a kladné celé číslo d existuje distribuce R k × d , ze které je extrahována matice A tak , že pro k = O ( ε −2 log(1/ δ )) a pro libovolný vektor jednotkové délky x ∈ R d platí následující tvrzení [2]

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

Odpovídající matice A se nazývají Johnson-Lindenstraussovy matice ( JL matice ) . Toto lemma v podstatě charakterizuje přesnost aproximace maticové projekce vícerozměrného rozdělení.

Spojení distributivní verze lemmatu s jeho původním ekvivalentem lze získat zadáním a pro nějakou dvojici u , v v X . ${\displaystyle x=(uv)/\|uv\|_{2))$ $\delta <1/n^{2}$

Možnost získat projekce nižší dimenze je velmi důležitým výsledkem naznačených lemmat, je však nutné, aby takové projekce bylo možné získat v minimálním čase. Operace násobení matice A vektorem x v distributivním lemmatu trvá O ( kd ). Proto byla provedena řada studií za účelem získání distribucí, pro které lze součin maticového vektoru vypočítat za méně než 0 ( kd ) čas.

Konkrétně v roce 2006 představili Eilon a Bernard Chazelle takzvanou rychlou Johnson-Lindenstraussovu transformaci (BPTL) , která vám umožňuje vypočítat součin maticového vektoru v čase pro jakoukoli konstantu . [3] ${\displaystyle d\log d+k^{2+\gamma ))$ $\gamma >0$

Speciální případ představují tenzorové náhodné projekce, pro které má vektor jednotkové délky x tenzorovou strukturu a promítající se JL matice A lze vyjádřit jako konečný součin několika matic se stejným počtem nezávislých řádků.

Tenzorové projekce vícerozměrných prostorů

Pro reprezentaci tenzorových projekcí používaných v BPDL ve vícerozměrném případě, jako kombinaci dvou matic JL se stejným počtem řádků, lze použít produkt pro dělení obličeje navržený v roce 1996 V.I. Slusarem . [4] [5] [6] [7] [8] [9] .

Uvažujme dvě JL-matice projekcí vícerozměrného prostoru: a . Jejich konečný produkt [4] [5] [6] [7] [8] má tvar: ${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].

Takto definované matice JL používají méně náhodných bitů a lze je rychle násobit vektory s tenzorovou strukturou díky následující identitě [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]

kde je prvek Hadamardův produkt . $\circ$

Přechod od promítací matice A ke konečnému součinu nám umožňuje nahradit původní násobení Hadamardovým součinem, který pracuje s maticemi nižší dimenze. V této souvislosti byla myšlenka konečného produktu použita v roce 2010 [10] k vyřešení problému rozdílného soukromí . Kromě toho byly podobné výpočty použity pro efektivní implementaci metody jádra v mnoha dalších algoritmech lineární algebry [11] .

V roce 2020 se ukázalo, že k vytvoření nízkorozměrných projekcí v konečném produktu stačí použít libovolné matice s náhodnými nezávislými řadami, nicméně silnější záruky dosažení malých zkreslení ve vysokorozměrných prostorech lze dosáhnout pomocí skutečného Gaussova Johnsona. -Lindenstraussovy matice [12] .

Pokud jsou matice nezávislé, obsahují prvky nebo Gaussovy matice, pak sloučená matice splňuje lemma Johnson-Lindenstraussova rozdělení, pokud je počet řádků alespoň ${\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] .

Pro velké je striktně splněno Johnson-Lindenstraussovo distributivní lemma, zatímco dolní mez aproximační chyby má exponenciální závislost [12] . K obejití tohoto omezení jsou navrženy alternativní konstrukce JL matic [12] . $\epsilon$ ${\displaystyle (\log 1/\delta )^{c))$

Poznámky

↑ Johnson, William B. & Lindenstrauss, Joram (1984), Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982) , v Beals, Richard; Beck, Anatole & Bellow, Alexandra a kol., Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982) , sv. 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. & Lindenstrauss, Joram (1984), Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982) , v Beals, Richard; Beck, Anatole & Bellow, Alexandra a kol., Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982) , sv. 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 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 (27. prosince 1996). “Koncové produkty v matricích v radarových aplikacích” (PDF) . Radioelektronika a komunikační systémy. – 1998, sv. 41; Číslo 3 : 50-53. Archivováno (PDF) z originálu dne 27.07.2020 . Staženo 2020-07-30 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ 1 2 Slyusar, VI (1997-05-20). „Analytický model digitálního anténního pole na bázi produktů face-splitting matrix“ (PDF) . Proč. ICATT-97, Kyjev : 108-109. Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-07-30 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ 1 2 3 Slyusar, VI (1997-09-15). „Nové operace maticového produktu pro aplikace radarů“ (PDF) . Proč. Přímé a inverzní problémy teorie elektromagnetických a akustických vln (DIPED-97), Lvov. : 73-74. Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-07-30 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ 1 2 Slyusar, VI (13. března 1998). „Rodina maticových produktů pro tváře a její vlastnosti“ (PDF) . Kybernetika a systémová analýza C/C of Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-07-30 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ 1 2 Slyusar, VI (2003). „Zobecněné obličejové produkty matic v modelech digitálních anténních polí s neidentickými kanály“ (PDF) . Radioelektronika a komunikační systémy . 46 (10): 9-17.
↑ Anna Esteve, Eva Boj & Josep Fortiana (2009): Interakční termíny v regresi založené na vzdálenosti, komunikace ve statistice – teorie a metody, 38:19, P. 3501 [1] Archivováno 26. dubna 2021 na Wayback Machine
↑ Kasiviswanathan, Shiva Prasad a kol. "Cena za soukromé zveřejnění kontingenčních tabulek a spekter náhodných matic s korelovanými řádky." Sborník příspěvků z 42. sympozia ACM na téma Teorie výpočetní techniky. 2010.
↑ Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Teoretická informatika 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). Oblivious Sketching of High-Degree Polynomial Kernels . Symposium ACM-SIAM o diskrétních algoritmech. Asociace pro výpočetní techniku. DOI : 10.1137/1.9781611975994.9 .

Literatura

Achlioptas, Dimitris (2003), Náhodné projekce vhodné pro databázi: Johnson-Lindenstrauss s binárními mincemi , Journal of Computer and System Sciences vol . 66(4): 671–687 , DOI 10.1016/S0022-0000(03)40025- Časopisová verze článku, který se dříve objevil na PODC 2001.
Dasgupta, Sanjoy & Gupta, Anupam (2003), Elementární důkaz Johnsonovy a Lindenstraussovy věty , Random Structures & Algorithms vol . 22 (1): 60–65, doi : 10.1002/rsa.10073 , < http:// cseweb.ucsd.edu/~dasgupta/papers/jl.pdf > .
Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), „ O průměrech vláken spojitých map “.