Komplexität beim Auffinden der pseudoinversen Matrix

Wie viele arithmetische Operationen sind erforderlich, um eine Moore-Penrose-Pseudoinverse-Matrix eines beliebigen Feldes zu finden?

Wenn die Matrix invertierbar und komplex bewertet ist, ist sie nur umgekehrt. Das Finden der Umkehrung dauert , wobei die Matrixmultiplikationskonstante ist. Es ist Satz 28.2 in Einführung in Algorithmen 3. Auflage.$O(n^\omega)$$\omega$

Wenn die Matrix hat linear unabhängigen Reihen oder Spalten und komplexwertige, kann die Pseudo - Inverse - Matrix mit berechnet werden oder jeweils , wobei die konjugierte Transponierte von . Insbesondere bedeutet dies eine Zeit für die Pseudo - Inversen des Finden .A ∗ ( A A ∗ ) - 1 ( A A ∗ ) - 1 A ∗ A ∗ A O ( n ω ) $A$$A^*(A A^*)^{-1}$$(A A^*)^{-1}A^*$$A^*$$A$$O(n^\omega)$$A$

Für die allgemeine Matrix verwenden die Algorithmen, die ich gesehen habe, QR-Zerlegung oder SVD, die im schlimmsten Fall -Arithmetikoperationen zu verwenden scheint . Gibt es Algorithmen, die weniger Operationen verwenden?$O(n^3)$

Zuallererst neigen die Leute dazu zu vergessen, dass ein Infimum ist. Immer wenn wir schreiben , meinen wir tatsächlich für alle , gibt es einen Algorithmus, der in der Zeit läuft .O ( n ω ) γ > ω O γ ( n γ$\omega$$O(n^\omega)$$\gamma > \omega$$O_\gamma(n^\gamma)$

Keller-Gehrig zeigte (unter anderem), wie man eine Matrix in Rangnormalform in der Zeit . Wenn Rang hat , dann eine Rang normale Form ist für einige invertierbare der geeigneten Abmessungen; siehe auch Algebraische Komplexitätstheorie, Satz 16.13 auf Seite 435.$A$$O(n^\omega)$$A$$r$$A$

Rank Normalform ist ähnlich der rank Zersetzung in dem Artikel Wikipedia erwähnt, wobei hat Spalten und hat Zeilen. In der Tat können wir als die ersten Spalten von und als die ersten Zeilen von . Angesichts dieser Zerlegung gibt Wikipedia eine Formel für die Pseudoinverse an, bei der nur Hermitian Adjoint, Matrixmultiplikation und Matrixinverse verwendet werden. Daher kann die Pseudoinverse in der Zeit berechnet werden .$A = XY$$X$$r$$Y$$r$$X$$r$$S$$Y$$r$$T$$O(n^\omega)$