Apakah optimasi PCA cembung?

Fungsi objektif dari Principal Component Analysis (PCA) adalah meminimalkan kesalahan rekonstruksi dalam norma L2 (lihat bagian 2.12 di sini . Pandangan lain sedang mencoba untuk memaksimalkan varians pada proyeksi. Kami juga memiliki posting yang sangat baik di sini: Apa fungsi tujuan PCA ? ).

Pertanyaan saya adalah apakah optimasi PCA cembung? (Saya menemukan beberapa diskusi di sini , tetapi berharap seseorang dapat memberikan bukti yang bagus di sini di CV).

Tidak, formulasi PCA yang biasa bukan masalah cembung. Tetapi mereka dapat ditransformasikan menjadi masalah optimisasi cembung.

Wawasan dan kesenangan dari ini mengikuti dan memvisualisasikan urutan transformasi daripada hanya mendapatkan jawaban: itu terletak pada perjalanan, bukan tujuan. Langkah utama dalam perjalanan ini adalah

1. Dapatkan ungkapan sederhana untuk fungsi tujuan.

2. Perbesar domainnya, yang bukan cembung, menjadi domain yang cembung.

3. Ubah tujuan, yang bukan cembung, menjadi sesuatu yang, dengan cara yang jelas tidak mengubah titik di mana ia mencapai nilai optimalnya.

Jika Anda terus mencermati, Anda dapat melihat pengganda SVD dan Lagrange mengintai - tetapi mereka hanya tontonan, ada untuk pemandangan indah, dan saya tidak akan mengomentarinya lebih lanjut.

---

Formulasi memaksimalkan-varians standar PCA (atau setidaknya langkah kuncinya) adalah

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*}$$

di mana matriks A adalah matriks simetris, positif-semidefinit yang dibangun dari data (biasanya jumlah kuadrat dan matriks produknya, matriks kovariansnya, atau matriks korelasinya).$n\times n$$\mathbb A$

(Dengan kata lain, kita dapat mencoba memaksimalkan objektif yang tidak dibatasi . Tidak hanya ini ekspresi yang lebih buruk - ini bukan lagi fungsi kuadrat - tetapi grafik kasus khusus akan dengan cepat menunjukkan itu bukan fungsi cembung) , salah satu. Biasanya orang mengamati fungsi ini invarian di bawah rescalings x → λ x dan kemudian menguranginya ke formulasi terbatas ( ∗ ) .)$x^\prime \mathbb{A} x / x^\prime x$$x\to \lambda x$$(*)$

Setiap masalah optimasi dapat dirumuskan secara abstrak sebagai

Temukan setidaknya satu yang membuat fungsi f : X → R sebesar mungkin.$x\in\mathcal{X}$$f:\mathcal{X}\to\mathbb{R}$

Ingat bahwa masalah pengoptimalan adalah cembung saat menikmati dua properti terpisah:

1. The domain cembung. $\mathcal{X}\subset\mathbb{R}^n$ Ini dapat dirumuskan dengan banyak cara. Salah satunya adalah bahwa setiap kali dan y ∈ X dan 0 ≤ λ ≤ 1 , λ x + ( 1 - λ ) y ∈ X juga. Geometris: setiap kali dua titik akhir dari kebohongan segmen garis di X , seluruh kebohongan segmen di X .$x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$$\lambda x + (1-\lambda)y\in\mathcal{X}$$\mathcal X$$\mathcal X$

2. The Fungsi adalah cembung. $f$ Ini juga dapat dirumuskan dengan banyak cara. Salah satunya adalah bahwa setiap kali dan y ∈ X dan 0 ≤ λ ≤ 1 , f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . (Kami membutuhkan $x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$

   $$f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$$ $\mathcal X$menjadi cembung agar kondisi ini untuk masuk akal) geometris. setiap kali adalah setiap segmen garis di X , grafik f (sebagai terbatas segmen ini) terletak di atas atau segmen yang menghubungkan ( x , f ( x ) ) dan ( y , f ( y ) ) dalam R n + 1 .$\bar{xy}$$\mathcal X$$f$$(x,f(x))$$(y,f(y))$$\mathbb{R}^{n+1}$

   Pola dasar dari fungsi cembung adalah lokal di mana-mana parabola dengan koefisien terkemuka non-positif: pada setiap segmen garis dapat dinyatakan dalam bentuk dengan a ≤ $y\to a y^2 + b y + c$$a \le 0.$

Kesulitan dengan adalah bahwa X adalah satuan bola S n - 1 ⊂ R n , yang jelas-jelas bukan cembung. $(*)$$\mathcal X$$S^{n-1}\subset\mathbb{R}^n$ Namun, kami dapat memodifikasi masalah ini dengan memasukkan vektor yang lebih kecil. Itu karena ketika kita skala dengan faktor λ , f dikalikan dengan λ 2 . Ketika 0 < x ′ x < 1 , kita dapat menskalakan x hingga satuan panjang dengan mengalikannya dengan λ = 1 / $x$$\lambda$$f$$\lambda^2$$0 \lt x^\prime x \lt 1$$x$, dengan demikian meningkatkanftetapi tetap dalam bola satuanDn={x∈ R n∣x′x≤1}. Karena itu marilah kita merumuskan kembali(∗)sebagai$\lambda=1/\sqrt{x^\prime x} \gt 1$$f$ $D^n = \{x\in\mathbb{R}^n\mid x^\prime x \le 1\}$$(*)$

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**}$$

Domainnya adalah yang jelas-jelas cembung, jadi kita setengah jalan. Masih mempertimbangkan cembungnya grafik f .$\mathcal{X}=D^n$$f$

Cara yang baik untuk memikirkan masalah - bahkan jika Anda tidak bermaksud melakukan perhitungan yang sesuai - adalah dalam hal Teorema Spektral. $(**)$ Ia mengatakan bahwa dengan cara transformasi ortogonal , Anda dapat menemukan setidaknya satu dasar R n di mana A adalah diagonal: yaitu,$\mathbb P$$\mathbb{R}^n$$\mathbb A$

$$\mathbb {A = P^\prime \Sigma P}$$

$\Sigma$$\mathbb{P}$$\mathbb A$$x\to x^\prime \mathbb{A} x$

$\mathbb A$$\Sigma$$\mathbb P$

$$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0.$$

$x=\mathbb{P}^\prime y$$x$$y=\mathbb{P}x$$f$

$$f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2.$$

$\mathcal X$$\sigma_i$

$(**)$$x^\prime x = 1$$\sigma_1$$f$$\mathcal{X}$$f$$f$$\sigma_1$

$$g(y) = f(y) - \sigma_1 y^\prime y.$$

$\sigma_1$$f$$g$$f$$\mathcal X$

$-\sigma_1$$-\sigma_1 y^\prime y$$\mathbb P$$y^\prime y = x^\prime x$$x$$g$

$$g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2.$$

$\sigma_1 \ge \sigma_i$$i$$g$$g$$x_2=x_3=\cdots=x_n=0$$x^\prime x=1$$x_1=\pm 1$$y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$$\mathbb P$

$g$$\partial D^n=S^{n-1}$$y^\prime y = 1$$f$$g$$\sigma_1$$g$$f$$D^n$$f$$g$

Tidak.

$k$$M$

$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$

$\|\cdot\|_F$

Meskipun normalnya cembung, set di mana ia dioptimalkan adalah nonconvex.

---

Sebuah relaksasi cembung masalah PCA ini disebut Convex Rendah Ranking Pendekatan

$\hat{X} = \underset{\|X\|_* \leq c}{argmin} \| M - X\|_F^2$

$\|\cdot\|_*$$\|\cdot\|_1$

Anda dapat melihat Pembelajaran Statistik dengan Sparsity , bab 6 (dekomposisi matriks) untuk detailnya.

Jika Anda tertarik pada masalah yang lebih umum dan bagaimana hubungannya dengan kecemburuan, lihat Generalized Low Rank Models .

Penafian: Jawaban sebelumnya melakukan pekerjaan yang cukup baik untuk menjelaskan bagaimana PCA dalam formulasi aslinya adalah non-cembung tetapi dapat dikonversi ke masalah optimasi cembung. Jawaban saya hanya ditujukan untuk jiwa-jiwa miskin (seperti saya) yang tidak begitu akrab dengan jargon Unit Spheres dan SVD - yang, baik, baik untuk diketahui.

Sumber saya adalah catatan kuliah ini oleh Prof. Tibshirani

Untuk masalah optimasi yang harus diselesaikan dengan teknik optimasi cembung, ada dua prasyarat.

1. Fungsi objektif harus cembung.
2. Fungsi kendala juga harus cembung.

Sebagian besar formulasi PCA melibatkan kendala pada peringkat matriks.

$rank(X) = k,$$J_{11}$$J_{22}$