Complejidad de encontrar la matriz pseudoinversa

¿Cuántas operaciones aritméticas se requieren para encontrar una matriz pseudoinversa de Moore-Penrose de un campo arbitrario?

Si la matriz es invertible y tiene un valor complejo, entonces es solo lo inverso. Encontrar el inverso toma tiempo , donde es la constante de multiplicación de la matriz. Es el Teorema 28.2 en Introducción a los Algoritmos 3ra Edición. $O(n^\omega)$ $\omega$

Si la matriz $A$ tiene filas o columnas linealmente independientes y un valor complejo, entonces la matriz pseudoinversa puede calcularse con $A^*(A A^*)^{-1}$ o $(A A^*)^{-1}A^*$ respectivamente , en donde $A^*$ es la transpuesta conjugada de $A$ . En particular, esto implica un $O(n^\omega)$ de tiempo para encontrar la pseudoinversa de $A$ .

Para la matriz general, los algoritmos que he visto usan descomposición QR o SVD, que parece tomar operaciones aritméticas $O(n^3)$ en el peor de los casos. ¿Hay algoritmos que usan menos operaciones?

algorithms linear-algebra Chao Xu
fuente

Tengo un seguimiento, que podría ser demasiado básico, pero puede usted por favor confirmar lo que es n aquí en la ecuación de la complejidad. ¿Es la dimensión de una matriz y qué pasa si la matriz no es un cuadrado?

Mike Pomp

En la afirmación de que lo inverso se puede encontrar en el tiempo

O (n^{ω})

$O(n^\omega)$ ,

n

$n$ es de hecho la dimensión de la matriz cuadrada; Si la matriz no es cuadrada, probablemente pueda tomar

n

$n$ como la dimensión más grande.

David Richerby el

Como esta es una pregunta fácil, la he respondido aquí. Sin embargo, si tiene más preguntas, hágalo como una página por sí mismo utilizando el botón "hacer preguntas" en la parte superior de la página. Puede volver a esta página para dar contexto. Este sitio solo está configurado para una pregunta por página: no hay subprocesos y las publicaciones se mueven de acuerdo con los votos que obtienen, por lo que las cosas se vuelven terriblemente desordenadas con más de una pregunta en una página. Hay más información en nuestro breve recorrido y en nuestro centro de ayuda .

David Richerby el

Respuestas:

En primer lugar, las personas tienden a olvidar que es un infimum. Cada vez que escribimos , en realidad queremos decir para todos , hay un algoritmo que se ejecuta en el tiempo . $\omega$ $O(n^\omega)$ $\gamma > \omega$ $O_\gamma(n^\gamma)$

Keller-Gehrig mostró (entre otros) cómo presentar una matriz en forma normal de rango en el tiempo . Si tiene rango , entonces una forma normal de rango de es para algunos invertibles de las dimensiones apropiadas; ver también Teoría de la complejidad algebraica, Proposición 16.13 en la página 435. $A$ $O(n^\omega)$ $A$ $r$ $A$

S (\begin{matrix} I_{r} & 0 \\ 0 & 0 \end{matrix}) T

$S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T$

S, T

$S,T$

La forma normal de rango es similar a la descomposición de rango mencionada en el artículo de Wikipedia, donde tiene columnas e tiene filas. De hecho, podemos tomar para ser los primeros columnas de , y para ser los primeros filas de . Dada esta descomposición, Wikipedia da una fórmula para el pseudoinverso usando solo adjuntos hermitianos, multiplicación de matrices e inverso de matrices. Por lo tanto, el pseudoinverso puede calcularse en el tiempo . $A = XY$ $X$ $r$ $Y$ $r$ $X$ $r$ $S$ $Y$ $r$ $T$ $O(n^\omega)$

Yuval Filmus
fuente

¡Gracias por la respuesta! Recibí el papel y descubrí que parece que me falta el fondo. ¿Hay algunas buenas presentaciones / encuestas sobre este tipo de resultado? Sé que el libro de la teoría de la complejidad algebraica es bueno, pero actualmente está sacado de la biblioteca ...

Chao Xu

Puede haber notas de clase relevantes, aunque probablemente sea mejor echar un vistazo al libro. CLRS (Introducción a los algoritmos) también contiene material relevante, como la equivalencia entre la multiplicación de matrices y la matriz inversa.

Yuval Filmus

Entonces, ¿ cumple en general? ¿Me puede dar una pista de lo que es la "constante de multiplicación de matrices" ?

O (n^{ω})

$O(n^ω)$

w

$w$

ben

No sabemos el valor de . El mejor límite superior, debido a Le Gall, es . Se conjetura que .

ω

$\omega$

ω < 2.3728639

$\omega < 2.3728639$

ω = 2

$\omega = 2$

Yuval Filmus