Embedding isometrik dari L2 ke L1

27

Hal ini diketahui bahwa diberi n bagian-titik dari 2d (yang, diberikan n poin di Rd dengan jarak Euclidean) adalah mungkin untuk menanamkan mereka isometrically di .1(n2)

Apakah isometri dapat dihitung pada waktu polinomial (mungkin, acak)?

Karena ada masalah ketepatan hingga, pertanyaan tepatnya adalah

Diberikan satu set X dari n poin dalam Rd dan ϵ>0 , adakah pemetaan f:XR(n2) computable (mungkin, menggunakan keacakan) di polinomial waktu dalam n dan logaritmik dalam 1/ϵ sedemikian rupa sehingga untuk setiap x,yX kita memiliki

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

(Catatan: Saya sadar bahwa pemetaan dengan distorsi (1+ϵ) dapat ditemukan dengan probabilitas tinggi dalam polinomial waktu dalam n dan 1/ϵ dengan memproyeksikan pada O(ϵ2logn) garis acak, tetapi saya tidak yakin apakah jumlah dimensi dapat dikurangi secara konstruktif menjadi (n2) atau bahkan O(n2) ketika 1/ϵ jauh lebih besar dari n , dan saya tidak tahu apakah ada adalah metode waktu polinomial untuk menangani kasus di mana 1/ϵ bersifat eksponensial dalam n .)

Luca Trevisan
sumber
1
ini pertanyaan yang sangat bagus. @ Luca, apakah Anda curiga ini mungkin sulit? (tentu saja pikiran pertama saya adalah untuk melihat 'Hamming memenuhi Euclid', dan kemudian saya melihat identitas si penanya :)
Suresh Venkat
1
Referensi ini tampaknya terkait: Pjotr ​​Indyk, "Prinsip ketidakpastian, ekstraktor, dan embeddings eksplisit l2 ke l1", Proc. STOC'07.
Martin Schwarz
2
@ David: adalah jumlah poin, saya mengoreksi tempat saya menggunakan untuk dimensi. Bahwa titik dalam ruang Euclidean (dari dimensi apa pun) dapat disematkan secara isometrik di terbukti di sini: www-math.mit.edu/ ~ goemans / 18409-2006 / lec1.pdf, tetapi bukan -konstruktif. (Teorema Carathéodory berubah dari dimensi terbatas tetapi besar ke dimensi dengan kesalahan kecil yang sewenang-wenang, dan argumen kekompakan untuk berubah dari kesalahan kecil sewenang-wenang menjadi kesalahan nol.)n n ( nnnn(n1(n2)(n2)
Luca Trevisan
1
@ Martin: terima kasih untuk referensi. Makalah Piotr berkaitan dengan masalah yang lebih sulit dalam memetakan semua (bukan hanya satu set poin) menjadi . Untuk masalah ini, saya percaya bahwa ini adalah masalah terbuka bahkan untuk mencapai, secara konstruktif, dan distorsi . (Piotr mendapat dan .) n m 1 m = p o l y ( d , 1 / ϵ ) ( 1 + ϵ ) m = d O ( log d ) ϵ = 1 / d2dn1mm=poly(d,1/ϵ)(1+ϵ)m=dO(logd)ϵ=1/d
Luca Trevisan
1
@LucaTrevisan: re: kekerasan embedding di l1, ini benar (disebutkan dalam Bab 1 atau 2 dari buku Deza and Laurent - Saya pikir melalui MAX CUT)
Suresh Venkat

Jawaban:

7

Suresh meminta saya untuk mengumpulkan komentar saya di atas menjadi jawaban, jadi ini dia. Saya tidak begitu yakin ini merupakan jawaban untuk pertanyaan awal, karena tidak jelas bagaimana membuatnya menjadi waktu polinomial ketika dimensi ruang input Euclidean tidak konstan. Itu setidaknya memiliki keuntungan menghindari masalah dengan sebagai pertanyaan awal, karena itu tidak melibatkan perkiraan, dan terlihat polinomial untuk konstanta .d1/ϵd

Pokoknya: dari geometri integral, ada ukuran standar pada set pesawat hiperplastik di ruang Euclide dimensional yang tidak berubah di bawah kongruensi Euclidean. Ia memiliki sifat bahwa panjang kurva panjang berbanding lurus dengan ukuran hyperplanes yang melintasi (dengan multiplisitas, yang berarti bahwa jika hyperplane melintasi dua kali maka ia berkontribusi dua kali terhadap total ukuran hyperplanes yang melintasi ). Khususnya jika adalah segmen garis maka komplikasi multiplisitas tidak muncul dan kita dapat menormalkan ukuran pada hyperplanes yang melintasi menjadi persis panjangC C C C C C C CdCCCCCCC. (Hyperplanes yang mengandung memiliki ukuran nol, jadi jangan khawatir tentang multiplisitas tak terbatas.)C

Sekarang, diberikan satu set n poin dalam ruang dimensi-d, buat koordinat untuk masing-masing partisi poin menjadi dua himpunan bagian yang disebabkan oleh hyperplane yang tidak melewati salah satu poin. Berikan poin di satu sisi nilai koordinat partisi nol dan poin di sisi lain nilai koordinat partisi sama dengan ukuran himpunan pesawat terbang yang mendorong partisi itu.1

Jika dan adalah dua dari dua poin, misalkan adalah himpunan bidang hiperplanes yang melintasi segmen , dan biarkan adalah himpunan bagian dari dibentuk oleh setiap kemungkinan partisi hyperplane yang memiliki di satu sisi dan di sisi lainnya. Maka adalah persatuan yang terpisah dari , dan perbedaan koordinat antara dan hanyalah ukuran dari himpunan bagian . Oleh karena itu, jarak antara koordinat danpn K p q K i K p q K K i p q K i 1qnKpqKiKpqKKipqKi1q K i K 2 p qpq (jumlah dari ukuran ) adalah ukuran dari , yang hanya merupakan jarak asli antara dan .KiK2pq

Untuk geometer komputasi, deskripsi alternatif dari konstruksi yang sama mungkin bermanfaat: gunakan dualitas projektif untuk mengubah input poin menjadi hyperplanes, dan memisahkan hyperplanes menjadi poin. Ukuran geometri integral pada set hyperplanes kemudian ditransformasikan menjadi ukuran yang lebih standar pada set point, jarak antara dan dualizes dengan ukuran wedge ganda antara dua hyperplanes, dan pengaturan hyperplane mempartisi wedge ganda ini menjadi sel yang lebih kecil . Nilai koordinat untuk suatu titik adalah ukuran salah satu sel dalam pengaturan (jika hyperplane ganda di bawah sel koordinat) atau nol (jika hyperplane ganda di atas sel). Oleh karena itu,np q 1 p q O ( n d ) d i = 0 ( nnpq1 jarak antara dan hanyalah jumlah dari ukuran sel dalam irisan ganda, yang sama dengan ukuran keseluruhan irisan ganda. Sudut pandang ganda ini juga memudahkan untuk menghitung dimensi penyisipan yang ditemukan dengan cara ini: hanya jumlah sel dalam pengaturan hyperplane, yaitu , atau lebih tepatnya paling banyak .pqO(nd)i=0d(ni)

Sejauh ini, ini memberikan embedding sepenuhnya deterministik dan tepat di . Tapi kami ingin dimensi yang lebih kecil, . Di sinilah komentar Luca tentang teorema Carathéodory masuk. Himpunan metrik membentuk kerucut polihedral di ruang -dimensi dari semua fungsi dari pasangan titik yang tidak berurutan menjadi bilangan real, dan argumen geometris di atas mengatakan bahwa metrik Euclidean termasuk dalam kerucut ini. Poin pada sinar ekstrim kerucut adalah satu dimensi( n1O(nd)1(n1(n2)11 ( n(n2)1pseudometrics (di mana titik-titik dibagi menjadi dua set, semua jarak dalam satu set adalah nol, dan semua jarak di split adalah sama), dan Carathéodory mengatakan bahwa setiap titik di dalam kerucut (termasuk yang kita pedulikan) dapat menjadi direpresentasikan sebagai kombinasi cembung dari titik-titik pada sinar ekstrim yang jumlahnya paling banyak adalah dimensi ruang sekitar, . Tetapi kombinasi cembung paling banyak dari metrik satu dimensi adalah metrik .( n(n2)1 ( n(n2)11(n2)

Akhirnya, bagaimana kita bisa menghitung komputasi select dimensional dimensional? Pada titik ini, kita tidak hanya memiliki satu titik dalam kerucut cembung dimensi dari metrik (metrik jarak yang kita mulai dengan), tetapi kita juga memiliki satu set titik ekstrim kerucut (sesuai dengan partisi input menjadi dua himpunan bagian yang diinduksi oleh pesawat terbang) sedemikian rupa sehingga metrik kami adalah kombinasi cembung dari titik-titik ekstrem ini - untuk kecil , ini merupakan peningkatan besar atas sinar ekstrim yang dimiliki kerucut. secara keseluruhan. Sekarang yang perlu kita lakukan adalah menerapkan algoritma serakah yang menghilangkan titik ekstrim dari set kita, satu per satu, sampai hanya( n(n2)1O(nd)d2n-2 ( n(n2)1O(nd)d2n2( n(n2)dari mereka yang tersisa. Pada setiap langkah, kita perlu mempertahankan sebagai tidak tetap bahwa metrik kita masih berada di dalam cembung titik ekstrim yang tersisa, yang hanya masalah kelayakan pemrograman linear, dan jika kita melakukan ini, Carathéodory akan memastikan bahwa selalu ada satu set titik ekstrim yang cembung cembungnya berisi metrik input.(n2)

David Eppstein
sumber