Numpy Cholesky Zerlegung LinAlgError

Question

In meinem Versuch, Cholesky-Zerlegung auf einer Varianz-Kovarianz-Matrix für ein 2D-Array der periodischen Randbedingung durchzuführen, bekomme ich unter bestimmten Parameterkombinationen immer LinAlgError: Matrix is not positive definite - Cholesky decomposition cannot be computed. Nicht sicher, ob es sich um eine numpy.linalg oder Implementierungsproblem ist, wie das Skript einfach ist:

sigma = 3. 
U = 4 

def FromListToGrid(l_): 
    i = np.floor(l_/U) 
    j = l_ - i*U 
    return np.array((i,j)) 

Ulist = range(U**2) 

Cov = [] 
for l in Ulist: 
    di = np.array([np.abs(FromListToGrid(l)[0]-FromListToGrid(i)[0]) for i, x in enumerate(Ulist)]) 
    di = np.minimum(di, U-di) 

    dj = np.array([np.abs(FromListToGrid(l)[1]-FromListToGrid(i)[1]) for i, x in enumerate(Ulist)]) 
    dj = np.minimum(dj, U-dj) 

    d = np.sqrt(di**2+dj**2) 
    Cov.append(np.exp(-d/sigma)) 
Cov = np.vstack(Cov) 

W = np.linalg.cholesky(Cov) 

Versuche Potential singularies entfernen auch das Problem zu lösen ist fehlgeschlagen. Jede Hilfe wird sehr geschätzt.

Answer 1

Ich grabe ein bisschen tiefer in das Problem, habe versucht, die Eigenwerte der Cov-Matrix zu drucken.

print np.linalg.eigvalsh(Cov) 

Und die Antwort stellt sich heraus, diese

[-0.0801339 -0.0801339 0.12653595 0.12653595 0.12653595 0.12653595 0.14847999 0.36269785 0.36269785 0.36269785 0.36269785 1.09439988 1.09439988 1.09439988 1.09439988 9.6772531 ] 

Aha sein! Beachten Sie die ersten beiden negativen Eigenwerte? Jetzt ist eine Matrix genau dann positiv definit, wenn alle ihre Eigenwerte positiv sind. Das Problem mit der Matrix ist also nicht, dass sie nahe an "Null" ist, sondern dass sie "negativ" ist. Um @duffymo-Analogie zu erweitern, ist dies ein lineares Algebraäquivalent, das versucht, die Quadratwurzel der negativen Zahl zu nehmen.

Jetzt versuchen wir, die gleiche Operation durchzuführen, aber dieses Mal mit scipy.

scipy.linalg.cholesky(Cov, lower=True) 

Und das nicht klappt etwas zu sagen mehr

numpy.linalg.linalg.LinAlgError: 12-th leading minor not positive definite 

, dass etwas mehr, erzählt (obwohl ich nicht wirklich verstehen konnte, warum es etwa 12-ten kleinere beschweren).

Fazit, die Matrix ist nicht ganz nah an "Null" aber ist eher wie "negativ"

Answer 2

Das Problem sind die Daten, die Sie ihm zuführen. Die Matrix ist gemäß dem Solver singulär. Das bedeutet ein Null- oder Fast-Null-Diagonalelement, so dass eine Inversion unmöglich ist.

Es wäre einfacher zu diagnostizieren, wenn Sie eine kleine Version der Matrix bereitstellen könnten.

Nulldiagonalen sind nicht die einzige Möglichkeit, eine Singularität zu erzeugen. Wenn zwei Zeilen proportional zueinander sind, brauchen Sie beide nicht in der Lösung. Sie sind überflüssig. Es ist komplexer als nur auf der Diagonale nach Nullen zu suchen.

Wenn Ihre Matrix korrekt ist, haben Sie ein nicht leeres Null-Leerzeichen. Sie müssen Algorithmen zu etwas wie SVD ändern.

Siehe meinen Kommentar unten.