Pertimbangkan dua ruang metrik dan , dan embedding . Penyematan ruang metrik tradisional mengukur kualitas sebagai rasio terburuk dari asli ke jarak final:
Ada beberapa ukuran kualitas lainnya: Dhamdhere dkk mempelajari distorsi "rata-rata":
Namun, ukuran saya tertarik di sini adalah yang digunakan oleh metode seperti MDS, yang melihat rata-rata kesalahan aditif :
Meskipun metode MDS seperti dipelajari secara luas di luar komunitas theoryCS, saya menyadari hanya satu makalah ( oleh Dhamdhere et al ) yang meneliti optimasi di bawah ukuran ini, dan itu juga untuk masalah terbatas menanamkan ke garis ( ) (catatan: tesis MS 2005 Tasos Sidiropoulos memiliki ulasan yang bagus tentang pekerjaan sebelumnya)
Adakah pekerjaan baru yang diketahui orang tentang analisis kualitas yang ketat di bawah gagasan kesalahan ini? Sementara masalah-masalah ini umumnya NP-keras, apa yang saya lebih tertarik adalah perkiraan apa pun.
sumber
Saya mungkin melewatkan sesuatu, tetapi mengapa ? Kami tertarik dengan perkiraan secara additif, jadi kami tidak dapat membuat skala untuk membuat untuk semua , kan?ϵ2≤(ρ−1)∑d(x,y)2 f(μ(x),μ(y))≥d(x,y) x,y
Satu keuntungan di sini adalah bahwa kita dapat melakukan hal buruk dalam jangka pendek dan akhirnya baik-baik saja. Juga, apakah masalahnya mudah (untuk perkiraan, bahkan) jika, katakanlah kita ingin menanamkan ke ? (bisakah kita menulis program matematika untuk menangkap pertanyaan?)ℓ2
sumber