Сложность нахождения псевдообратной матрицы

Сколько арифметических операций требуется, чтобы найти псевдообратную матрицу Мура – ​​Пенроуза произвольного поля?

Если матрица обратима и имеет комплексное значение, то это просто обратная величина. Нахождение обратного времени занимает , где - константа умножения матриц. Это Теорема 28.2 в Введение в алгоритмы 3-е издание.$O(n^\omega)$$\omega$

Если матрица имеет линейно независимые строки или столбцы и имеет комплексное значение, то псевдообратная матрица может быть вычислена с помощью или соответственно , где является сопряженной транспозицией . В частности, это предполагает время нахождения Псевдообратного .$A$$A^*(A A^*)^{-1}$$(A A^*)^{-1}A^*$$A^*$$A$$O(n^\omega)$$A$

Для общей матрицы в алгоритмах, которые я видел, используется QR-разложение или SVD, которое, кажется, в худшем случае использует арифметических операций. Есть ли алгоритмы, которые используют меньше операций?$O(n^3)$

Прежде всего люди склонны забывать, что - это инфимум. Всякий раз, когда мы пишем O ( n ω ) , мы фактически имеем в виду для всех γ > ω , существует алгоритм, работающий во времени O γ ( n γ ) .$\omega$$O(n^\omega)$$\gamma > \omega$$O_\gamma(n^\gamma)$

Келлер-Гериг показал (среди прочего), как представить матрицу в ранге нормальной формы за время O ( n ω ) . Если A имеет ранг r , то ранг-нормальная форма A есть S ( I r 0 0 0 ) T для некоторых обратимых S , T соответствующих размерностей; см. также Теория алгебраической сложности, предложение 16.13 на стр. 435.$A$$O(n^\omega)$$A$$r$$A$

$A = XY$$X$$r$$Y$$r$$X$$r$$S$$Y$$r$$T$$O(n^\omega)$