Saya tahu definisi matriks positif simetris positif (SPD), tetapi ingin lebih memahami.
Mengapa mereka begitu penting, secara intuitif?
Inilah yang saya tahu. Apa lagi?
Untuk data yang diberikan, matriks Co-variance adalah SPD. Matriks co-variance adalah metrik penting, lihat posting yang luar biasa ini untuk penjelasan intuitif.
Bentuk kuadrat adalah cembung, jikaadalah SPD. Convexity adalah properti yang bagus untuk suatu fungsi yang dapat memastikan solusi lokal adalah solusi global. Untuk masalah Cembung, ada banyak algoritma yang baik untuk dipecahkan, tetapi tidak untuk masalah non-covex.
Ketika adalah SPD, solusi optimisasi untuk bentuk kuadratik
dan solusi untuk sistem linearadalah sama. Jadi kita dapat menjalankan konversi antara dua masalah klasik. Ini penting karena memungkinkan kami menggunakan trik yang ditemukan di satu domain di domain lain. Sebagai contoh, kita dapat menggunakan metode gradien konjugasi untuk menyelesaikan sistem linear.Ada banyak algoritma yang baik (cepat, stabil numerik) yang berfungsi lebih baik untuk matriks SPD, seperti dekomposisi Cholesky.
EDIT: Saya tidak mencoba menanyakan identitas untuk matriks SPD, tetapi intuisi di belakang properti untuk menunjukkan pentingnya. Misalnya, seperti yang disebutkan oleh @Matthew Drury, jika sebuah matriks adalah SPD, semua nilai Eigen adalah bilangan real positif, tetapi mengapa semua hal-hal positif penting. @Matthew Drury memiliki jawaban yang bagus untuk mengalir dan itulah yang saya cari.
Jawaban:
Matriks simetris (nyata) memiliki satu set vektor eigen ortogonal yang lengkap dengan nilai eigen yang sesuai semuanya adalah bilangan real. Untuk matriks non-simetris ini bisa gagal. Misalnya, rotasi dalam ruang dua dimensi tidak memiliki vektor eigen atau nilai eigen dalam bilangan real, Anda harus beralih ke ruang vektor di atas bilangan kompleks untuk menemukannya.
Jika matriks tersebut juga positif pasti, maka nilai eigen ini adalah bilangan real positif. Fakta ini jauh lebih mudah daripada yang pertama, karena jika adalah vektor eigen dengan satuan panjang, dan λ nilai eigen yang sesuai, makav λ
di mana kesetaraan terakhir menggunakan definisi ketajaman positif.
Pentingnya intuisi di sini adalah bahwa vektor eigen dan nilai eigen dari transformasi linear menggambarkan sistem koordinat di mana transformasi paling mudah dipahami. Transformasi linier bisa sangat sulit untuk dipahami dalam basis "alami" seperti sistem koordinat standar, tetapi masing-masing dilengkapi dengan basis vektor eigen "pilihan" di mana transformasi bertindak sebagai penskalaan di semua arah. Ini membuat geometri transformasi lebih mudah dipahami.
Misalnya, tes turunan kedua untuk ekstrema lokal dari fungsi sering diberikan sebagai serangkaian kondisi misterius yang melibatkan entri dalam matriks turunan kedua dan beberapa faktor penentu. Faktanya, kondisi ini hanya menyandikan pengamatan geometris berikut:R2→ R
Anda dapat memahami ini dengan alasan geometris di atas dalam basis eigen. Derivatif pertama pada titik kritis menghilang, sehingga laju perubahan fungsi di sini dikendalikan oleh turunan kedua. Sekarang kita dapat bernalar secara geometris
Karena vektor eigen menjangkau seluruh ruang, setiap arah lainnya merupakan kombinasi linear dari arah eigen, sehingga laju perubahan dalam arah tersebut adalah kombinasi linear dari laju perubahan dalam arah eigen. Jadi pada kenyataannya, ini berlaku untuk semua arah (ini kurang lebih artinya untuk fungsi yang didefinisikan pada ruang dimensi yang lebih tinggi untuk dapat dibedakan). Sekarang jika Anda menggambar sedikit di kepala Anda, ini membuat banyak akal dari sesuatu yang cukup misterius dalam teks kalkulus pemula.
Ini berlaku langsung ke salah satu poin Anda
Matriks turunan kedua adalah mana - mana, yang pasti positif simetris. Secara geometris, ini berarti bahwa jika kita bergerak dalam arah eigen apa pun (dan karenanya arah apa pun , karena yang lain merupakan kombinasi linear dari arah eigen) fungsi itu sendiri akan melengkung jauh di atas bidang singgung itu. Ini berarti seluruh permukaan cembung.SEBUAH
sumber
Anda akan menemukan beberapa intuisi dalam banyak cara dasar untuk menunjukkan nilai eigen dari matriks simetris nyata semuanya nyata: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- bukti / 118640 # 118640
Secara khusus, bentuk kuadrat muncul secara alami dalam hasil bagi Rayleigh, dan matriks simetris memberikan apa yang bisa dibilang cara paling alami untuk menunjukkan keluarga besar matriks yang nilai eigennya nyata. Lihat teorema minimax Courant misalnya: https://en.wikipedia.org/wiki/Courant_minimax_principlexTAx
Juga simetris, matriks yang pasti ketat positif hanya mengatur matriks yang dapat menentukan produk dalam non-sepele, bersama dengan norma diinduksi: . Ini karena menurut definisi untuk vektor nyata x , y d ( x , y ) = d ( y , x ) untuk semua x , y dan ‖ x ‖ 2 =d(x,y)=⟨x,Ay⟩=xTAy x,y d(x,y)=d(y,x) x,y untuk x ≠ 0 . Dengan cara ini, matriks definitif positif simetris dapat dipandang sebagai kandidat yang ideal untuk transformasi koordinat.∥x∥2=xTAx>0 x≠0
Properti yang terakhir ini benar-benar penting dalam bidang mesin vektor pendukung, khususnya metode kernel dan trik kernel , di mana kernel harus positif simetris untuk menginduksi produk dalam yang benar. Memang teorema Mercer menggeneralisasi sifat intuitif dari matriks simetris ke ruang fungsional.
sumber
Sehubungan dengan optimasi (karena Anda menandai pertanyaan Anda dengan tag optimasi), matriks SPD sangat penting untuk satu alasan sederhana - SPD Hessian menjamin bahwa arah pencarian adalah arah penurunan. Pertimbangkan derivasi metode Newton untuk optimisasi tanpa kendala. Pertama, kami membentuk ekspansi Taylor dari :f(x+Δx)
Selanjutnya, kami mengambil turunannya sehubungan dengan :Δx
Akhirnya, tetapkan turunan sama dengan 0 dan selesaikan untuk :Δx
Dengan asumsi∇2f(x) adalah SPD, mudah untuk melihat bahwa adalah arah penurunan karena:Δx
Saat menggunakan metode Newton, matriks Hessian non-SPD biasanya "didorong" menjadi SPD. Ada algoritma rapi yang disebut Cholesky termodifikasi yang akan mendeteksi Hessian non-SPD, "mendorong" dengan tepat ke arah yang benar dan memfaktisasi hasilnya, semuanya untuk (pada dasarnya) biaya yang sama dengan faktorisasi Cholesky. Metode Quasi-Newton menghindari masalah ini dengan memaksa perkiraan Goni menjadi SPD.
Sebagai tambahan, sistem tak terbatas simetris menerima banyak perhatian hari ini. Mereka muncul dalam konteks metode titik interior untuk optimasi terbatas.
sumber
Secara geometris, matriks definitif positif mendefinisikan metrik , misalnya metrik Riemann, sehingga kita dapat langsung menggunakan konsep geometris.
Jikax dan y adalah vektor dan A adalah matriks pasti positif, maka
d(x,y)=(x−y)TA(x−y)−−−−−−−−−−−−−−√
adalah metrik (juga disebut fungsi jarak).
sumber
Sudah ada beberapa jawaban yang menjelaskan mengapa matriks pasti positif simetris begitu penting, jadi saya akan memberikan jawaban yang menjelaskan mengapa mereka tidak sepenting beberapa orang, termasuk penulis dari beberapa jawaban itu, berpikir. Demi kesederhanaan, saya akan membatasi fokus ke matriks simetris, dan berkonsentrasi pada Hessians dan optimisasi.
Jika Tuhan membuat dunia cembung, tidak akan ada optimasi cembung, hanya akan ada optimasi. Demikian pula, tidak akan ada matriks (pasti) positif (simetris), hanya akan ada matriks (simetris). Tapi bukan itu masalahnya, jadi atasi saja.
Jika masalah Pemrograman Quadratic adalah cembung, itu bisa diselesaikan "dengan mudah". Jika tidak cembung, optimum global masih dapat ditemukan menggunakan metode branch and bound (tetapi mungkin membutuhkan lebih banyak memori dan lebih lama).
Jika metode Newton digunakan untuk optimasi dan Hessian di beberapa iterate tidak terbatas, maka tidak perlu untuk "memperhalus" itu ke kepastian positif. Jika menggunakan pencarian garis, arah kelengkungan negatif dapat ditemukan dan pencarian garis dieksekusi di sepanjang mereka, dan jika menggunakan wilayah kepercayaan, maka ada beberapa wilayah kepercayaan yang cukup kecil sehingga solusi dari masalah wilayah kepercayaan mencapai keturunan.
Adapun metode Quasi-Newton, BFGS (teredam jika masalahnya terbatas) dan DFP mempertahankan kepastian positif dari pendekatan Hessian atau Hessian terbalik. Metode Quasi-Newton lainnya, seperti SR1 (Symmetric Rank One) tidak harus mempertahankan kepastian positif. Sebelum Anda mendapatkan semua bengkok dari itu, itu adalah alasan yang baik untuk memilih SR1 untuk banyak masalah - jika Hessian benar-benar tidak pasti positif di sepanjang jalan ke optimal, maka memaksa pendekatan Quasi-Newton menjadi positif pasti dapat menghasilkan aproksimasi kuadratik yang buruk terhadap fungsi objektif. Sebaliknya, metode pemutakhiran SR1 "longgar seperti angsa", dan dapat berubah dengan sendirinya berubah seiring berjalannya waktu.
Untuk masalah optimasi yang dibatasi secara nonlinier, yang penting bukanlah Hessian dari fungsi objektif, tetapi Hessian dari Lagrangian. Hessian dari Lagrangian mungkin tidak terbatas bahkan pada optimum, dan memang, hanya proyeksi Hessian dari Lagrangian ke dalam ruang kosong dari Jacobian dari batasan aktif (linier dan nonlinier) yang perlu semi positif. -Tentu pada optimal. Jika Anda memodelkan Hessian of the Lagrangian via BFGS dan dengan demikian membatasinya menjadi positif pasti, itu mungkin sangat cocok di mana-mana, dan tidak berfungsi dengan baik. Sebaliknya, SR1 dapat menyesuaikan nilai eigennya dengan apa yang sebenarnya "dilihatnya".
Ada banyak lagi yang bisa saya katakan tentang semua ini, tetapi ini cukup untuk memberi Anda rasa.
Sunting : Apa yang saya tulis 2 paragraf di atas adalah benar. Namun, saya lupa menunjukkan bahwa itu juga berlaku untuk masalah yang dibatasi secara linear. Dalam kasus masalah yang dibatasi secara linear, Hessian dari Lagrangian hanya (mengurangi hingga) Hessian dari fungsi tujuan. Jadi syarat optimalitas urutan ke-2 untuk minimum lokal adalah bahwa proyeksi fungsi tujuan Goni ke dalam ruang kosong Jacobian dari kendala aktif adalah semi-pasti positif. Terutama, Hessian dari fungsi objektif tidak perlu (harus) menjadi optimal, dan seringkali tidak, bahkan pada masalah yang dibatasi secara linear.
sumber
Anda telah mengutip banyak alasan mengapa SPD penting namun Anda masih memposting pertanyaan. Jadi, menurut saya Anda harus menjawab pertanyaan ini terlebih dahulu: Mengapa kuantitas positif penting?
Jawaban saya adalah bahwa sejumlah kuantitas harus positif agar sesuai dengan pengalaman atau model kita. Misalnya, jarak antara item dalam ruang harus positif. Koordinat bisa negatif, tetapi jarak selalu non-negatif. Oleh karena itu, jika Anda memiliki kumpulan data dan beberapa algoritma yang memprosesnya Anda mungkin berakhir dengan satu yang rusak ketika Anda memberi makan jarak negatif ke dalamnya. Jadi, Anda mengatakan "algoritma saya memerlukan input jarak positif setiap saat", dan itu tidak terdengar seperti permintaan yang tidak masuk akal.
Dalam konteks statistik, analogi yang lebih baik adalah varians. Jadi, kami menghitung varians sebagai
Jadi, matriks varians-kovarians adalah semi-pasti positif, yaitu "non-negatif" dalam analogi ini. Contoh algoritma yang memerlukan kondisi ini adalah penguraian Cholesky, ini sangat berguna. Ini sering disebut "akar kuadrat dari matriks". Jadi, seperti akar kuadrat dari bilangan real yang membutuhkan non-negatif, Cholesky menginginkan matriks non-negatif. Kami tidak menemukan kendala ini ketika berhadapan dengan matriks kovarians karena selalu ada.
Jadi, itulah jawaban utilitarian saya. Kendala seperti non-negatif atau SPD memungkinkan kami membangun algoritma perhitungan yang lebih efisien atau alat pemodelan yang nyaman yang tersedia ketika input Anda memenuhi kendala ini.
sumber
Berikut adalah dua alasan lagi yang belum disebutkan mengapa matriks positif-semidefinit penting:
Matriks Laplacian grafik dominan diagonal dan dengan demikian PSD.
Semidefiniteness positif mendefinisikan urutan parsial pada set matriks simetris (ini adalah dasar pemrograman semidefinite).
sumber