Bagaimana cara menghitung matriks kovarians perkiraan tridiagonal, untuk dekorelasi cepat?

Dengan matriks data katakanlah pengamatan 1000000 100 fitur, apakah ada cara cepat untuk membangun perkiraan tridiagonal ? Maka kita dapat faktor , semua 0 kecuali dan , dan melakukan hubungan dekorasi cepat (memutihkan) dengan memecahkan . (Dengan "cepat" Maksudku .) $X$ $\times$ $A \approx cov(X)$
$A = L L^T$ $L$ $L_{i\ i-1}$ $L_{i i}$ $L x = x_{white}$ $O( size\ X )$

(Ditambahkan, mencoba mengklarifikasi): Saya mencari pemutih yang cepat dan kotor yang lebih cepat daripada full tetapi lebih baik daripada diagonal. Katakanlah adalah titik data fitur , mis. 1000000 100, dengan fitur 0-mean. $cov(X)$ $X$ $N$ $\times Nf$ $\times$

1) membangun , faktor Cholesky sebagai , pecahkan untuk memutihkan baru . Ini kuadratik dalam jumlah fitur. $Fullcov = X^T X$ $L L^T$ $L x = x_{white}$ $x$

2) diagonal: mengabaikan korelasi silang sepenuhnya. $x_{white} = x / \sigma(x)$

Orang bisa mendapatkan matriks tridiagonal dari hanya dengan -zeroing semua entri di luar tridiagonal, atau tidak mengakumulasinya di tempat pertama. Dan di sini saya mulai tenggelam: harus ada perkiraan yang lebih baik, mungkin hierarkis, blok diagonal → tridiagonal? $Fullcov$

(Ditambahkan 11 Mei): Biarkan saya membagi pertanyaan menjadi dua:

1) apakah ada perkiraan cepat ? Tidak (whuber), seseorang harus melihat semua pasangan (atau memiliki struktur, atau sampel). $cov(X)$
${N \choose 2}$

2) diberikan , seberapa cepat dapat satu memutihkan baru s? Nah, memfaktorkan , segitiga bawah, satu kali, lalu menyelesaikan cukup cepat; scipy.linalg.solve_triangular, misalnya, menggunakan Lapack. Saya mencari whiten () yang lebih cepat, masih mencari. $cov(X)$ $x$
$cov = L L^T$ $L$ $L x = x_{white}$

variance approximation covariance-matrix denis
sumber

Apakah kolom memiliki urutan alami untuk mereka? Atau Anda ingin menemukan pendekatan tridiagonal di bawah permutasi kolom ("optimal")? Saya berasumsi bahwa ketika Anda mengatakan Anda berbicara tentang struktur kovarians fitur. Bisakah Anda mengkonfirmasi ini?

A = C o v (X)

$A = \mathrm{Cov}(X)$

kardinal

Tidak, tidak ada pemesanan alami, dan ya, kovarians dari 100 fitur. Metode yang menjumlahkan matriks kovarian penuh, kemudian memperkirakannya, akan menjadi >> O (ukuran X); Saya mencari perkiraan sederhana yang cepat, yang tentu saja kasar.

denis

Jadi, Anda ingin pendekatan tridiagonal di bawah permutasi (ditentukan oleh data), ya?

kardinal

ditambahkan, mencoba mengklarifikasi. Jika permutasi yang baik (memuaskan) dapat ditemukan di O (Nfeatures), ya, itu bisa dilakukan.

denis

Ada perkiraan ketika variabel memiliki struktur tambahan, seperti ketika mereka membentuk deret waktu atau realisasi proses stokastik spasial di berbagai lokasi. Ini secara efektif bergantung pada asumsi yang memungkinkan kita menghubungkan kovarians antara satu pasang variabel dengan pasangan variabel lainnya, seperti antara pasangan yang dipisahkan oleh jeda waktu yang sama. Perhitungan dapat berupa dalam kasus seperti itu. Tidak ada model seperti itu, saya tidak melihat bagaimana Anda dapat menghindari menghitung semua kovarian berpasangan.

O (N f \log (N f)

$O(Nf \log(Nf)$

whuber

Jawaban:

Hanya menghitung matriks kovarians - yang Anda perlukan untuk memulai dalam peristiwa apa pun - adalah jadi, asimtotik dalam , tidak ada yang diperoleh dengan memilih algoritma untuk memutihkan. $O((Nf)^2)$ $N$ $O(Nf)$

Ada perkiraan ketika variabel memiliki struktur tambahan, seperti ketika mereka membentuk deret waktu atau realisasi proses stokastik spasial di berbagai lokasi. Ini secara efektif bergantung pada asumsi yang memungkinkan kita menghubungkan kovarians antara sepasang variabel dengan pasangan variabel lainnya, seperti antara pasangan yang dipisahkan oleh jeda waktu yang sama. Ini adalah alasan konvensional untuk menganggap suatu proses stasioner atau intrinsik stasioner , misalnya. Perhitungan bisa dalam kasus seperti itu ( misalnya , menggunakan Fast Fourier Transform seperti dalam Yao & Journel 1998 ). Tanpa model seperti itu, saya tidak melihat bagaimana Anda dapat menghindari menghitung semua kovarian berpasangan. $O(Nflog(Nf)$

whuber
sumber

Pada saat yang bersamaan, saya memutuskan untuk mencoba menghitung (dalam R) matriks kovarians untuk dataset sebesar ukuran yang disebutkan dalam OP:

z <- rnorm(1e8)
dim(z) <- c(1e6, 100)
vcv <- cov(z)

Ini membutuhkan waktu kurang dari satu menit, pada laptop yang cukup umum yang menjalankan Windows XP 32-bit. Mungkin butuh waktu lebih lama untuk menghasilkan zdaripada menghitung matriks vcv. Dan R tidak terlalu optimal untuk operasi matriks di luar kotak.

Mengingat hasil ini, apakah kecepatan itu penting? Jika N >> p, waktu yang dibutuhkan untuk menghitung perkiraan Anda mungkin tidak akan jauh lebih sedikit daripada untuk mendapatkan matriks kovarians yang sebenarnya.

Hong Ooi
sumber