Badan Cembung dengan norma minimum l2 yang diharapkan

23

Pertimbangkan benda cembung K yangK berpusat pada titik asal dan simetris (yaitu jika x KxK maka ). Saya ingin menemukan tubuh cembung berbeda sehingga dan ukuran berikut diminimalkan:xKxKLLK LKL

f ( L ) = E ( x Tx )f(L)=E(xTx) , di mana adalah titik yang dipilih secara seragam secara acak dari L.xx

Saya baik-baik saja dengan perkiraan faktor konstan terhadap ukuran.

Beberapa catatan - Tebakan intuitif pertama bahwa itu sendiri adalah jawabannya salah. Sebagai contoh, anggap sebagai silinder tipis dalam dimensi yang sangat tinggi. Kemudian kita bisa mendapatkan sedemikian rupa sehingga dengan membiarkan memiliki volume yang lebih dekat ke asalnya.K K L f ( L ) < f ( K ) LKKLf(L)<f(K)L

Ashwinkumar BV
sumber
Untuk apa-apa nilainya, masalahnya terlihat sulit. Bahkan dalam 3d tidak jelas bagaimana menyelesaikannya.
Sariel Har-Peled
Apakah sudah jelas bagaimana melakukannya dalam 2d secara optimal? Tentu saja dalam 2d pendekatan faktor konstan tidak menarik.
Ashwinkumar BV
Tidak jelas bagi saya. Perkiraan faktor konstan terlihat jelas dalam dimensi apa pun dengan mendekati bentuk oleh ellipsoid www.math.sc.edu/ ~ howard/Notes/john.pdf. Konstanta akan tergantung pada dimensi.
Sariel Har-Peled
Saya lebih tertarik pada pendekatan faktor konstan di mana konstanta tidak tergantung pada dimensi.
Ashwinkumar BV
1
Tentu saja. Tapi izinkan saya mengambilnya kembali - bahkan ellipsoid case tidak jelas. Jika Anda ingin menyerang masalah ini, itu akan menjadi versi pertama yang diselidiki. Secara intuitif, Anda harus memutuskan dimensi mana yang harus diabaikan, dan dimensi mana yang akan diperluas. Tampaknya solusi alami adalah cembung-cembung penyatuan ellipsoid dengan ellipsoid lain, di mana sumbu ellipsoid baru sama dengan beberapa parameter r, atau sama dengan ellipsoid lainnya.
Sariel Har-Peled

Jawaban:

1

Jika kami membatasi K dan L sebagai ellipsoid, maka masalah Anda dapat diselesaikan dengan akurasi dengan SDP. Saya tahu ini bukan yang Anda tanyakan pada awalnya, tetapi sepertinya kami tidak memiliki solusi bahkan untuk kasus terbatas ini, dan mungkin ini dapat membantu secara umum.KL

Jadi katakanlah E adalah input ellipsoid dan kami mencari untuk menemukan ellipsoid J yang optimal . Terdapat peta linear F st E = F B 2 dan peta G st J = G B 2 , di mana B 2 adalah bola satuan. Kemudian E x J [ x 2 2 ] = 1EJFE=FB2GJ=GB2B2n Tr(GTG). JugaEJJE, di manaEadalahbadan kutubdariE. Dengan mudah,E={x:xTFTFx1}danJ={x:xTGTGx1}ExJ[x22]=1nTr(GTG)EJJEEEE={x:xTFTFx1}J={x:xTGTGx1}. Ini mengikuti bahwa J E (dan karenanya E J ) jika dan hanya jika G T G - F T F adalah matriks semidefinit positif.JEEJGTGFTF

Jadi SDP didefinisikan oleh: diberi simetris PSD matriks M , menemukan matriks PSD simetris N st N - M adalah PSD dan T r ( N ) diminimalkan. N dapat ditemukan dengan memecahkan SDP dan kemudian sebuah SVD akan memberikan sumbu dan sumbu panjang J .MNNMTr(N)NJ

Sasho Nikolov
sumber
0

(Seperti yang disebutkan dalam komentar, pendekatan berikut tidak bekerja. Objek yang diperoleh tidak cembung. Ini mencirikan objek "berbentuk bintang" dengan jarak minimum yang diharapkan.)

Saya pikir objek yang optimal adalah penyatuan K dan beberapa bola berpusat pada titik asal. Inilah pikiran saya. Menurut definisi Anda tentang f ( L ) , f ( L ) S d - 1r L 0 x d ( x d / x d L )Kf(L)d x rLv o l ( L ) dxdS S d-1r 2 Lv o l ( L ) dS S d - 1 r 2 L dSS d - 1 r L d S d e f = g(L), di manarLadalah jarak dari titik asal ke permukaanLsepanjang arah tertentu. Saya menggunakanbukannya =, karena saya menjatuhkan beberapa konstanta. Sekarang kita ingin meminimalkang(L)di bawah kendala yangrLrKbersama segala arah. Perhatikan bahwa jikarKbersama beberapa arah lebih kecil darig(

f(L)Sd1rL0xd(xd/xdL)dxrLvol(L)dxdSSd1r2Lvol(L)dSSd1r2LdSSd1rLdS=defg(L),
rLLg(L)rLrKrKK ) / 2 , maka kita bisa membuatnya sedikit lebih besar, katakanlah tambah ϵ g ( K ) / 2 - r K , untuk membuat g ( K ) lebih kecil. Itu karena kita meningkatkan enumerator dengan ( r L + ϵ ) 2 - r 2 L = ϵ ( 2 r L + ϵ ) , kurang dari faktor g ( K )g(K)/2ϵg(K)/2rKg(K)(rL+ϵ)2r2L=ϵ(2rL+ϵ)g(K)dari peningkatan penyebut. Oleh karena itu, kita dapat berpikir secara bertahap "mendeformasi" K (dengan berulang kali menumbuhkan objek sedikit, dan memperbarui g ( ) ) untuk membuat nilainya g ( ) lebih kecil. Biarkan K menjadi objek cembung pada akhirnya. Kemudian, setiap titik pada K K berada pada jarak g ( K ) / 2 dari titik asal, yaitu, K adalah gabungan K dan bola dengan jari-jari g ( KKg()g()KKKg(K)/2KK ) / 2 .g(K)/2

Memang, pertimbangkan objek cembung lain K sehingga g ( K ) = g ( K ) . Kemudian K K , karena jika tidak kita dapat menumbuhkan bagian K di dalam K untuk membuat g ( K ) lebih kecil. Di sisi lain, K K , karena jika tidak, dengan ide yang sama, kita dapat mengecilkan bagian dari K K di luar K Kg(K)=g(K)KKKKg(K)KKKKK to make g(K)g(K) smaller. So there is a unique optimal solution.

user7852
sumber
1
Maybe I'm missing something, but why is the object generated in this way convex?
mjqxxxx
@mjqxxxx You are right. How did I miss that...
user7852
How about the following idea: it is well known that a convex object can be approximated by some ellipsoid, i.e., there is an ellipsoid EKEK such that EKKdEKEKKdEK. Then f(dEK)f(dEK) approximates f(K)f(K) with approx ratio d. For any L containing K, dEKdEL. So if we can find the optimal ellipsoid E containing dEK, then f(E)d2f(L). I don't know how to compute E. But I would guess its axes align with the axes of dEK, and all eigenvalues of dEK below some threshold are raised to that threshold.
user7852
I agree that if L is not restricted to a convex body it is union of K and a ball.
Ashwinkumar B V
The idea of using ellipsoid won't give you a constant factor. It can give at best a d approximation. My conjecture is that convex hull of L with a ball of appropriate radius is a constant factor approximation. I am not sure how to prove or disprove the conjecture.
Ashwinkumar B V
0

The following solution is based on the this assumpotion/conjecture [to be proved]:

Conjecture: The expectation of a convex function on conv(KK) is smaller than the larger between the expectation on K and the expectation on K.

[We will need the above only for K,K convex, but is might be true in general]

Take now any set K and apply a rotation R to it centered on the origin, obtaining R(K). You are going to have f(K)=f(R(K)), because the rotation leaves the length of the elements of K invariant. If I am right about the conjecture, f(conv(KR(K)))f(K). Since for any optimal L you could consider L=RR(L)=conv(RR(L)), where R indicates the union over all rotations, and have f(L)f(L)f(L), it would seem that the optimal L can be chosen to be the smallest sphere containing K.

Marco
sumber
It would be sufficient to prove that Econv(A)EA for the expectation of a convex function. That EKKmax{EK,EK} seems easy.
Marco
4
I am not entirely sure I get your answer. But it is definitely not true that L can be chosen to be the smallest sphere containing K. Consider a long thin cylinder in d dimensions of length t. Then any sphere S containing K should have f(S)t. But if you construct L=conv(KU) where U is a sphere or radius roughly c1t/d you get f(L) roughly c2t/d. (where c1,c2 are constants)
Ashwinkumar B V