Dimensionsreduzierung bei Durchhang?

11

Das Johnson-Lindenstrauss-Lemma sagt ungefähr, dass für jede Sammlung von Punkten in eine Karte wobei so dass für alle : Es ist bekannt, dass ähnliche Aussagen für die Metrik nicht möglich sind , aber es ist bekannt, ob es eine Möglichkeit gibt, eine solche niedrigere zu Grenzen durch schwächere Garantien? Kann es beispielsweise eine Version des obigen Lemmas für $S$ $n$ $\mathbb{R}^d$ $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ $k = O(\log n/\epsilon^2)$ $x, y \in S$

(1 - ϵ) | | f (x) - f (y) | |_{2} \leq | | x - y | |_{2} \leq (1 + ϵ) | | f (x) - f (y) | |_{2}

$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$

ℓ_{1}

$\ell_1$

ℓ_{1}

$\ell_1$ Metrik, die nur verspricht, die Abstände der meisten Punkte beizubehalten, aber einige willkürlich verzerrt lassen könnte? Eine, die keine multiplikative Garantie für Punkte gibt, die "zu nah" sind?

ds.algorithms approximation-algorithms cg.comp-geom metrics embeddings Aaron Roth
quelle

9

Die Standardreferenz für ein derart positives Ergebnis ist Piotr Indyks Artikel über stabile Verteilungen:

http://people.csail.mit.edu/indyk/st-fin.ps

Er zeigt eine Dimensionsreduktionstechnik für bei der der Abstand zwischen einem nicht mit konstanter Wahrscheinlichkeit zunimmt (um mehr als Faktor ) und die Abstände nicht mit hoher Wahrscheinlichkeit abnehmen (um mehr als Faktor ) Wahrscheinlichkeit. Die Dimension der Einbettung ist in exponentiell . $\ell_1$ $1+\epsilon$ $1-\epsilon$ $1/\epsilon$

Es gibt wahrscheinlich Folgearbeiten, die mir nicht bekannt sind.

Moritz
quelle

8

Weitere Papier " Metrische Einbettungen mit entspannten Garantien" , das Ergebnisse zu (unter den Bedingungen einer "anmutig verschlechterten Verzerrung") und allgemeinen Einbettungen enthält. $\ell_1$ $\ell_p$

die praktischen Verfahren zur Dimensionsreduzierung in . $\ell_1$

spinxl39
quelle

7

Newman und Rabinovich haben kürzlich gezeigt, dass für n Punkte in eine Dimensionsreduktion auf Dimension . Unter Verwendung eines Satzes von Abraham et al. (Metrische Einbettung mit entspannten Garantien, wie oben erwähnt) Man kann eine Dimensionsreduzierung in der Dimension , die für einen Bruchteil der Paare funktioniert . $\ell_1$ $O(n/\epsilon)$ $O(1/(\delta\epsilon))$ $1-\delta$

Yair
quelle

4

Eine weitere Lockerung der Dimensionsreduktion besteht darin, dass in einem dimensionalen Unterraum von und von abhängt . Talagrand bewies, dass bei einem dimensionalen Unterraum von (er beweist es sogar für ) eine Karte für so dass für alle , $\ell_1$ $S$ $c$ $\mathbb{R}^d$ $k$ $c$ $c$ $V$ $\ell_1^d$ $L_1$ $f:\ell_1^d \rightarrow \ell_1^k$ $k = O(\epsilon^{-2}c\log c)$ $x, y \in V$ $(1-\epsilon)\|f(x) - f(y)\|_1 \leq \|x - y\|_1 \leq (1+\epsilon)\|f(x) - f(y)\|_1$ . Seine Einbettung ist ein einfaches randomisiertes Verfahren, das jedoch schrittweise abläuft und jeder Schritt mit konstanter Wahrscheinlichkeit erfolgreich ist. Nach jedem Schritt müssen Sie überprüfen, ob der Schritt tatsächlich erfolgreich war, und wiederholen, wenn dies nicht der Fall ist. Talagrands Einbettung fehlt also ein entscheidendes Merkmal von JLT: die Tatsache, dass aus einer von unabhängigen Verteilung ausgewählt werden kann . $f$ $S$

In jüngster Zeit haben Woodruff und Sohler ein analoges Ergebnis wie bei Talagrand bewiesen, aber mit dem zusätzlichen Merkmal, dass genau wie in JLT eine lineare Abbildung ist, die aus einer von unabhängigen Verteilung ausgewählt wird : Sie müssen eine Matrix auswählen, wobei Jeder Eintrag ist eine iid Cauchy-Zufallsvariable. Dies ist im Geiste von Indyks stabilen Projektionen: Cauchy ist 1-stabil. $f$ $S$ $k \times d$

Sasho Nikolov
quelle

Dimensionsreduzierung bei Durchhang?

Antworten: