Isometrische Einbettung von L2 in L1

Es ist bekannt, dass es bei einer Punkt-Teilmenge von ( dh bei Punkten in mit euklidischem Abstand) möglich ist, sie isometrisch in ) einzubetten $n$ $\ell_2^d$ $n$ ${\mathbb R}^d$ . $\ell^{n\choose 2}_1$

Ist die Isometrie in (möglicherweise randomisierter) Polynomzeit berechenbar?

Da es endliche Präzisionsprobleme gibt, ist die genaue Frage

Bei einer Menge von Punkten in und gibt es eine Abbildung $X$ $n$ ${\mathbb R}^d$ $\epsilon >0$ berechenbar (möglicherweise unter Verwendung von Zufälligkeit) im Zeitpolynom inund logarithmisch inso dass für jedesgilt $f: X \to {\mathbb R}^{n\choose 2}$ $n$ $1/\epsilon$ $x,y\in X$

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

(Anmerkung: Mir ist bekannt, dass eine Abbildung mit Verzerrung mit hoher Wahrscheinlichkeit im Zeitpolynom in und indem auf zufällige Linien projiziert wird, ich jedoch nicht sicher, ob die Anzahl der Dimensionen konstruktiv auf reduziert werden kann $(1+\epsilon)$ $n$ $1/\epsilon$ $O(\epsilon^{-2} \cdot \log n)$ oder sogarwennviel größer als, und ich weiß nicht, ob es eine polynomielle Zeitmethode gibt, um den Fall zu behandeln, in deminexponentiell ist.) $n\choose 2$ $O(n^2)$ $1/\epsilon$ $n$ $1/\epsilon$ $n$

cg.comp-geom metrics embeddings Luca Trevisan
quelle

das ist eine sehr schöne frage. @Luca, hast du den Verdacht, dass es schwer sein könnte? (Natürlich war mein erster Gedanke, über 'Hamming meets Euclid' zu schauen, und dann sah ich die Identität des Fragestellers :)

Suresh Venkat

Diese Referenz scheint verwandt zu sein: Pjotr Indyk, "Unsicherheitsprinzipien, Extraktoren und explizite Einbettungen von l2 in l1", Proc. STOC'07.

Martin Schwarz

@ David:

ist die Anzahl der Punkte. Ich habe die Stelle korrigiert, an der ich

für die Bemaßung verwendet habe. Dass

Punkte im euklidischen Raum (beliebiger Dimension) isometrisch in

) eingebettet werden können

n

$n$

n

$n$

n

$n$

wird hier bewiesen:www-math.mit.edu/~goemans/18409-2006/lec1.pdf.Sondern nicht-konstruktiv (Carathéodory Theoremum von endlicheraber großer Dimension Dimension

ℓ_{1}^{(\binom{n}{2})}

$\ell_1^{n \choose 2}$

mit willkürlich kleinem Fehler und einem Kompaktheitsargument, um von willkürlich kleinem Fehler zu Null-Fehler zu gelangen.)

(\binom{n}{2})

${n \choose 2}$

Luca Trevisan

@Martin: danke für den Hinweis. Piotrs Aufsatz beschäftigt sich mit dem schwierigeren Problem,

(nicht nur eine feste Menge von

Punkten) auf

abzubilden . Für dieses Problem glaube ich , dass es ein offenes Problem ist auch, konstruktiv zu erreichen,

und Verzerrung

. (Piotr erhält

und

ℓ_{2}^{d}

$\ell_2^d$

n

$n$

ℓ_{1}^{m}

$\ell_1^m$

m = p o l y (d, 1 / ϵ)

$m = poly(d,1/\epsilon)$

(1 + ϵ)

$(1+\epsilon)$

m = d^{O (\log d)}

$m = d^{O(\log d)}$

ϵ = 1 / d

$\epsilon = 1/d$

Luca Trevisan

@LucaTrevisan: Bezüglich der Härte der Einbettung in l1 ist dies wahr (es wird in Kapitel 1 oder 2 des Buches von Deza und Laurent erwähnt - ich denke über MAX CUT)

Suresh Venkat

Suresh hat mich gebeten, meine obigen Kommentare zu einer Antwort zusammenzufassen. Ich bin mir jedoch nicht sicher, ob es eine Antwort auf die ursprüngliche Frage ist, da es nicht offensichtlich ist, wie man sie zu einer Polynomzeit macht, wenn die Dimension des eingegebenen euklidischen Raums nicht konstant ist. Es hat zumindest den Vorteil, dass Probleme mit großen vermieden werden, wie in der ursprünglichen Frage angegeben, da es keine Annäherung enthält und für die Konstante polynomisch aussieht . $1/\epsilon$ $d$

$d$ $C$ $C$ $C$ $C$ $C$ $C$ $C$ $C$

$\ell_1$

$p$ $q$ $n$ $K$ $pq$ $K_i$ $K$ $p$ $q$ $K$ $K_i$ $p$ $q$ $K_i$ $\ell_1$ $p$ $q$ $K_i$ $K$ $\ell_2$ $p$ $q$

$n$ $n$ $p$ $q$ $\ell_1$ $p$ $q$ $O(n^d)$ $\sum_{i=0}^d{n\choose i}$

$\ell_1^{O(n^d)}$ $\ell_1^{n\choose 2}$ $\ell_1$ $n\choose 2$ $\ell_1$ $n\choose 2$ $n\choose 2$ $\ell_1$ $\ell_1^{n\choose 2}$

$n\choose 2$ $n\choose 2$ $\ell_1$ $O(n^d)$ $d$ $2^n-2$ $n\choose 2$ $n\choose 2$

David Eppstein
quelle

Isometrische Einbettung von L2 in L1

Antworten: