Wie berechnet man die tridiagonale ungefähre Kovarianzmatrix für eine schnelle Dekorrelation?

Gibt es bei einer Datenmatrix von beispielsweise 1000000 Beobachtungen 100 Merkmalen eine schnelle Möglichkeit, eine tridiagonale Approximation ? Dann könnte man , alle 0 außer und faktorisieren und eine schnelle Dekorrelation (Weißfärbung) durchführen, indem man löst . (Mit "schnell" meine ich .) $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 )$

(Hinzugefügt, um dies zu klären): Ich suche einen schnellen und schmutzigen Weißmacher, der schneller als die volle aber besser als die Diagonale ist. Angenommen, ist Datenpunkte Merkmale, z. B. 1000000 100, mit Merkmalen 0-Mittelwert. $cov(X)$ $X$ $N$ $\times Nf$ $\times$

1) Build , Cholesky-Faktor als , lösen , um neue s aufzuhellen . Dies ist quadratisch in der Anzahl der Merkmale. $Fullcov = X^T X$ $L L^T$ $L x = x_{white}$ $x$

2) Diagonale: ignoriert Kreuzkorrelationen vollständig. $x_{white} = x / \sigma(x)$

Man könnte eine tridiagonale Matrix von indem man einfach alle Einträge außerhalb der tridiagonalen auf setzt oder sie überhaupt nicht akkumuliert. Und hier fange ich an zu sinken: Es muss eine bessere Annäherung geben, vielleicht hierarchisch, Blockdiagonale → Tridiagonale? $Fullcov$

(Hinzugefügt am 11. Mai): Lassen Sie mich die Frage in zwei Teile teilen:

1) es eine schnelle ungefähre ? Nein (whuber), man muss sich alle Paare ansehen (oder Struktur oder Stichprobe haben). $cov(X)$
${N \choose 2}$

2) Wie schnell kann man bei einer neue s ? Nun, , unteres Dreieck einmal , ist es ziemlich schnell, lösen . scipy.linalg.solve_triangular verwendet beispielsweise Lapack. Ich suchte nach einem noch schnelleren Whiten (), das immer noch suchte. $cov(X)$ $x$
$cov = L L^T$ $L$ $L x = x_{white}$

variance approximation covariance-matrix denis
quelle

Haben die Säulen eine natürliche Reihenfolge? Oder möchten Sie eine tridiagonale Näherung unter einer ("optimalen") Permutation der Spalten finden? Ich gehe davon aus, dass Sie mit von der Kovarianzstruktur der Features sprechen. Können Sie das bestätigen?

A = C o v (X)

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

Kardinal

Nein, es gibt keine natürliche Reihenfolge und ja, Kovarianz der 100 Merkmale. Methoden, die eine vollständige Kovarianzmatrix addieren und dann approximieren, wären >> O (Größe X); Ich suche eine schnelle einfache Annäherung, die notwendigerweise grob sein wird.

Denis

Sie möchten also eine tridiagonale Approximation unter einer (durch die Daten zu bestimmenden) Permutation, ja?

Kardinal

hinzugefügt, versucht zu klären. Wenn eine gute (zufriedenstellende) Permutation in O (Nfeatures) gefunden werden könnte, würde dies ausreichen.

Denis

Es gibt Annäherungen, wenn die Variablen eine zusätzliche Struktur haben, z. B. wenn sie eine Zeitreihe bilden oder Realisierungen eines räumlichen stochastischen Prozesses an verschiedenen Orten. Diese beruhen effektiv auf Annahmen, mit denen wir die Kovarianz zwischen einem Variablenpaar mit der zwischen anderen Variablenpaaren in Beziehung setzen können, z. B. zwischen Paaren, die durch die gleichen Zeitverzögerungen getrennt sind. Berechnungen können in solchen Fällen . Ohne ein solches Modell sehe ich nicht, wie Sie es vermeiden können, alle paarweisen Kovarianzen zu

O (N f \log (N f)

$O(Nf \log(Nf)$

berechnen

Antworten:

Die bloße Berechnung der Kovarianzmatrix - die Sie auf jeden Fall benötigen, um loszulegen - ist . Asymptotisch in wird also nichts gewonnen, wenn Sie einen -Algorithmus für die auswählen Bleaching. $O((Nf)^2)$ $N$ $O(Nf)$

Es gibt Annäherungen, wenn die Variablen eine zusätzliche Struktur aufweisen, z. B. wenn sie eine Zeitreihe bilden oder Realisierungen eines räumlichen stochastischen Prozesses an verschiedenen Orten. Diese beruhen effektiv auf Annahmen, mit denen wir die Kovarianz zwischen einem Variablenpaar mit der zwischen anderen Variablenpaaren in Beziehung setzen können, z. B. zwischen Paaren, die durch die gleichen Zeitverzögerungen getrennt sind. Dies ist der herkömmliche Grund für die Annahme, dass ein Prozess beispielsweise stationär oder an sich stationär ist. Berechnungen können in solchen Fällen ( z. B. unter Verwendung der schnellen Fourier-Transformation wie in Yao & Journel 1998 ). Ohne ein solches Modell sehe ich nicht, wie Sie die Berechnung aller paarweisen Kovarianzen vermeiden können. $O(Nflog(Nf)$

whuber
quelle

Aus einer Laune heraus habe ich beschlossen, die Kovarianzmatrix (in R) für einen Datensatz von etwa der im OP genannten Größe zu berechnen:

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

Dies dauerte insgesamt weniger als eine Minute auf einem ziemlich generischen Laptop mit Windows XP 32-Bit. Das Generieren hat wahrscheinlich länger zgedauert als das Berechnen der Matrix vcv. Und R ist nicht besonders für sofort einsatzbereite Matrixoperationen optimiert.

Ist Geschwindigkeit angesichts dieses Ergebnisses so wichtig? Wenn N >> p, wird die Zeit, die zur Berechnung Ihrer Näherung benötigt wird, wahrscheinlich nicht viel kürzer sein, als um die tatsächliche Kovarianzmatrix zu erhalten.

Hong Ooi
quelle