Embedding isometrik dari L2 ke L1

Hal ini diketahui bahwa diberi $n$ bagian-titik dari $\ell_2^d$ (yang, diberikan $n$ poin di ${\mathbb R}^d$ dengan jarak Euclidean) adalah mungkin untuk menanamkan mereka isometrically di .$\ell^{n\choose 2}_1$

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 ${\mathbb R}^d$ dan $\epsilon >0$ , adakah pemetaan $f: X \to {\mathbb R}^{n\choose 2}$ computable (mungkin, menggunakan keacakan) di polinomial waktu dalam $n$ dan logaritmik dalam $1/\epsilon$ sedemikian rupa sehingga untuk setiap $x,y\in X$ kita memiliki

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

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

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 .$1/\epsilon$$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 $d$$C$$C$$C$$C$$C$$C$$C$. (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.$\ell_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 dan$p$n K p q K i K p q K K i p q K i ℓ $q$$n$$K$$pq$$K_i$$K$$p$$q$$K$$K_i$$p$$q$$K_i$$\ell_1$q K i K ℓ 2 p $p$$q$ (jumlah dari ukuran ) adalah ukuran dari , yang hanya merupakan jarak asli antara dan .$K_i$$K$$\ell_2$$p$$q$

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,$n$p q ℓ 1 p q O ( n d ) ∑ d i = 0 ($n$$p$$q$$\ell_1$ 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 .$p$$q$$O(n^d)$$\sum_{i=0}^d{n\choose i}$

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 ℓ ($\ell_1^{O(n^d)}$ℓ1($\ell_1^{n\choose 2}$$\ell_1$ ℓ1 ($n\choose 2$$\ell_1$pseudometrics (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\choose 2$ ℓ1ℓ ($n\choose 2$$\ell_1$$\ell_1^{n\choose 2}$

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\choose 2$ ℓ1O(nd)d2n-2 ($n\choose 2$$\ell_1$$O(n^d)$$d$$2^n-2$($n\choose 2$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.$n\choose 2$