Apa kompleksitas komputasi untuk menghitung Matriks Varians-Kovarian?

Saya menggunakan perhitungan matriks Varians-Kovarian dalam program yang saya tulis (untuk Analisis Komponen Utama), dan saya bertanya-tanya apa kerumitannya. Sementara jelas dekomposisi Eigenvector menyebabkan hit kinerja terbesar, saya bertanya-tanya berapa banyak hit yang disebabkan oleh perhitungan Covariance Matrix.

Waktu berjalan asimptotik yang saya perkirakan akan digunakan adalah menggunakan algoritma naif, karena harus mengambil rata-rata semua data ukuran N dan kemudian harus melakukannya untuk setiap dimensi (di mana n adalah jumlah dimensi) dalam iterasi bersarang, dan dengan demikian menghasilkan n 2 ukuran matriks.$O(N\cdot n^2)$$N$$n$$n^2$

Apakah asumsi saya benar, atau jika tidak, apa kompleksitas asimptotiknya?

Dugaan Anda benar.

Jika dengan N sebagai jumlah titik data dan n menjadi jumlah fitur, maka Anda dapat memperoleh matriks kovarians dengan X T X (terlepas dari pengurangan rata-rata yang dapat diabaikan dari perspektif kompleksitas).$X\in \mathbb{R}^{N \times n}$$N$$n$$X^TX$

Jadi, perhitungan matriks kovarians adalah perkalian matriks yang memang naif dalam lihat di sini , karena Anda harus melakukan kira-kira operasi untuk mengisi setiap posisi dalam matriks kovarians . Dalam praktiknya, perkalian matriks dipercepat hingga untuk matriks kuadratik (lihat tautan).$\mathcal{O}(Nn²)$ $2N$$n²$$X$$\mathcal{O}(n^{2.73})$