Isometrische Einbettung von L2 in L1

27

Es ist bekannt, dass es bei einer Punkt-Teilmenge von d 2 ( dh bei n Punkten in R d mit euklidischem Abstand) möglich ist, sie isometrisch in ( n ) einzubettenn2dnRd.1(n2)

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

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

Bei einer Menge von n Punkten in R d und ϵ > 0 gibt es eine Abbildung f : X R ( nXnRdϵ>0 berechenbar (möglicherweise unter Verwendung von Zufälligkeit) im Zeitpolynom innund logarithmisch in1/ϵ,so dass für jedesx,yXgiltf:XR(n2)n1/ϵx,yX

||f(x)f(y)||1||xy||2(1+ϵ)||f(x)f(y)||1

(Anmerkung: Mir ist bekannt, dass eine Abbildung mit Verzerrung mit hoher Wahrscheinlichkeit im Zeitpolynom in n und 1 / ϵ gefunden werden kann, indem auf O ( ϵ - 2log n ) zufällige Linien projiziert wird, ich jedoch nicht sicher, ob die Anzahl der Dimensionen konstruktiv auf ( n) reduziert werden kann(1+ϵ)n1/ϵO(ϵ2logn) oder sogarO(n2),wenn1/ϵviel größer alsn ist, und ich weiß nicht, ob es eine polynomielle Zeitmethode gibt, um den Fall zu behandeln, in dem1/ϵinnexponentiell ist.)(n2)O(n2)1/ϵn1/ϵn

Luca Trevisan
quelle
1
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
1
Diese Referenz scheint verwandt zu sein: Pjotr ​​Indyk, "Unsicherheitsprinzipien, Extraktoren und explizite Einbettungen von l2 in l1", Proc. STOC'07.
Martin Schwarz
2
@ David: ist die Anzahl der Punkte. Ich habe die Stelle korrigiert, an der ich n für die Bemaßung verwendet habe. Dass n Punkte im euklidischen Raum (beliebiger Dimension) isometrisch in ( n ) eingebettet werden könnennnnwird hier bewiesen:www-math.mit.edu/~goemans/18409-2006/lec1.pdf.Sondern nicht-konstruktiv (Carathéodory Theoremum von endlicheraber großer Dimension Dimension(n1(n2) mit willkürlich kleinem Fehler und einem Kompaktheitsargument, um von willkürlich kleinem Fehler zu Null-Fehler zu gelangen.)(n2)
Luca Trevisan
1
@Martin: danke für den Hinweis. Piotrs Aufsatz beschäftigt sich mit dem schwierigeren Problem, (nicht nur eine feste Menge von n Punkten) auf m 1 abzubilden . Für dieses Problem glaube ich , dass es ein offenes Problem ist auch, konstruktiv zu erreichen, m = p o l y ( d , 1 / ε ) und Verzerrung ( 1 + ε ) . (Piotr erhält m = d O ( log d ) und ϵ = 12dn1mm=poly(d,1/ϵ)(1+ϵ)m=dO(logd) .)ϵ=1/d
Luca Trevisan
1
@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

Antworten:

7

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 d polynomisch aussieht .1/ϵd

dCCCCCCCC

1

pqnKpqKiKpqKKipqKi1pqKiK2pq

nnpq1pqO(nd)i=0d(ni)

1O(nd)1(n2)1(n2)1(n2)(n2)11(n2)

(n2)(n2)1O(nd)d2n2(n2)(n2)

David Eppstein
quelle