Lemma Johnson-Lindenstrauss mengatakan secara kasar bahwa untuk setiap koleksi dari poin dalam , terdapat peta mana sedemikian rupa sehingga untuk semua :
Lemma Johnson-Lindenstrauss mengatakan secara kasar bahwa untuk setiap koleksi dari poin dalam , terdapat peta mana sedemikian rupa sehingga untuk semua :
Referensi standar untuk hasil positif tersebut adalah makalah Piotr Indyk tentang distribusi stabil:
http://people.csail.mit.edu/indyk/st-fin.ps
Dia menunjukkan teknik reduksi dimensi untuk mana jarak antara setiap pasangan poin tidak meningkat (lebih dari faktor ) dengan probabilitas konstan dan jarak tidak berkurang (lebih dari faktor ) dengan probabilitas tinggi. Dimensi embedding akan menjadi eksponensial dalam .
Mungkin ada tindak lanjut yang tidak saya sadari.
Baru-baru ini, Woodruff dan Sohler telah membuktikan hasil yang analog dengan Talagrand, tetapi dengan fitur tambahan bahwa , seperti di JLT, adalah pemetaan linear yang diambil dari distribusi independen : Anda perlu memilih matriks mana setiap entri adalah variabel acak iid Cauchy. Ini adalah semangat proyeksi stabil Indyk: Cauchy adalah 1-stable.