Vektor eigen dari penyesuaian norma kecil

Saya memiliki dataset yang perlahan berubah, dan saya harus melacak vektor eigen / nilai eigen dari matriks kovariansnya.

Saya sudah menggunakan scipy.linalg.eigh, tapi terlalu mahal, dan tidak menggunakan fakta bahwa saya sudah memiliki dekomposisi yang hanya sedikit salah.

Adakah yang bisa menyarankan pendekatan yang lebih baik untuk menangani masalah ini?

Pendekatan naif adalah dengan menggunakan solusi nilai eigen dari matriks sebagai tebakan awal eigensolver iteratif untuk matriks . Anda mungkin menggunakan QR jika Anda membutuhkan spektrum penuh, atau metode daya sebaliknya. Ini bukan pendekatan yang sepenuhnya kuat, namun, karena nilai eigen dari suatu matriks tidak selalu mendekati matriks yang hampir berdekatan (1) , terutama jika kondisi buruknya (2) .A ( t + δ t $A(t)$$A(t + \delta t)$

Metode pelacakan ruang bagian tampaknya lebih berguna (3) . Kutipan dari (4) :

Perhitungan iteratif dari pasangan eigen ekstrim (maksimal atau minimum) (nilai eigen dan vektor eigen) dapat tanggal kembali ke tahun 1966 [72]. Pada tahun 1980, Thompson mengusulkan algoritma adaptif tipe-LMS untuk memperkirakan vektor eigen, yang sesuai dengan nilai eigen terkecil dari matriks kovarians sampel, dan menyediakan algoritma pelacakan adaptif dari sudut / frekuensi combing dengan estimator harmonik Pisarenko [14]. Sarkar et al. [73] menggunakan algoritma gradien konjugasi untuk melacak variasi vektor eigen ekstrem yang sesuai dengan nilai eigen terkecil dari matriks kovarians dari sinyal yang berubah secara perlahan dan membuktikan konvergensi yang jauh lebih cepat daripada algoritma tipe-LMS Thompson. Metode ini hanya digunakan untuk melacak nilai ekstrem tunggal dan vektor eigen dengan aplikasi terbatas, tetapi kemudian mereka diperluas untuk metode pelacakan dan memperbarui eigen-subruang. Pada tahun 1990, Comon dan Golub [6] mengusulkan metode Lanczos untuk melacak nilai singular ekstrim dan vektor singular, yang merupakan metode umum yang awalnya dirancang untuk menentukan beberapa masalah eigen simetris besar dan jarang.$Ax = kx$ [74].

[6]: Comon, P., & Golub, GH (1990). Melacak beberapa nilai dan vektor tunggal yang ekstrem dalam pemrosesan sinyal. Dalam Memproses IEEE (hlm. 1327–1343).

[14]: Thompson, PA (1980). Teknik analisis spektral adaptif untuk frekuensi yang tidak bias

[72]: Bradbury, WW, & Fletcher, R. (1966). Metode iteratif baru untuk solusi dari masalah eigen. Matematika Numerik, 9 (9), 259–266.

[73]: Sarkar, TK, Dianat, SA, Chen, H., & Brule, JD (1986). Estimasi spektral adaptif dengan metode gradien konjugat. Transaksi IEEE pada Akustik, Pidato, dan Pemrosesan Sinyal, 34 (2), 272–284.

[74]: Golub, GH, & Beban Van, CF (1989). Perhitungan matriks (2nd ed.). Baltimore: The John Hopkins University Press.

Saya juga harus menyebutkan bahwa solusi untuk matriks simetris, seperti apa yang harus Anda pecahkan dengan penggunaannya scipy.linalg.eigh, agak murah. Jika Anda hanya tertarik pada beberapa nilai eigen, Anda mungkin menemukan peningkatan kecepatan dalam metode Anda juga. Metode Arnoldi sering digunakan dalam situasi seperti itu.

Ada teknik khusus untuk memperbarui eigen-dekomposisi dari matriks kovarian yang bergantung waktu. Diberikan dekomposisi nilai eigen "sebelum" (katakan pada waktu awal ), algoritma rekursif ini menurunkan kompleksitas pembaruan spektrum dari (pada dasarnya biaya komposisi eigend baru) ke mana adalah ukuran matriks Anda dan adalah pangkat pembaruan Anda.O ( N 3 ) O ( k N 2 ) N $t^0$$\mathcal{O}(N^3)$$\mathcal{O}(k N^2)$$N$$k$

Berikut adalah beberapa referensi yang relevan:

Eucendecomposition Adaptive Matriks Kovarian Data Berdasarkan Perturbasi Orde Pertama (Champagne, IEEE TSP 42 (10) 1994)

Rekursif memperbarui dekomposisi nilai eigen dari matriks kovarians (Yu, IEEE TSP, 39 (5) 1991)

Analisis Komponen Utama Online dalam Dimensi Tinggi: Algoritma mana yang harus Dipilih? (Cardot dan Degras)

Algoritma Yang Stabil Dan Cepat Untuk Memperbarui Dekomposisi Nilai Singular (Gu dan Eisenstadt, 1994)