Pseudoinverso de la descomposición CUR

Question

Dada una matriz A, sé que hay una forma de obtener su pseudoinverso (también llamado inverso de Moore-Penrose) a partir de su SVD. Si $A = USV^T$ entonces

$A^{\dagger} = VS^{\dagger}U^T$

Imaginemos, en cambio, que conozco una descomposición CUR de A, es decir $A = CUR$ , donde:

• $C = A(:, \mathcal{C})$ (donde $A(:, \mathcal{C})$ significa $A$ restringido a un conjunto de columnas $\mathcal{C}$ )
• $R = A(\mathcal{R}, :)$ (donde $A(\mathcal{R}, :)$ significa $A$ restringido a un conjunto de filas $\mathcal{R}$ )
• $U = A(\mathcal{R}, \mathcal{C})^{-1}$ (donde $A(\mathcal{R}, \mathcal{C})$ significa $A$ restringido a un conjunto de filas $\mathcal{R}$ y un conjunto de columnas $\mathcal{C}$ )

Entonces, ¿cómo puedo derivar una expresión para $A^{\dagger}$ (pseudoinverso de A) utilizando los factores $C$ , $U$ y $R$ ?

Alternativamente, suponiendo que tengo una caja negra $pinv(M)$ que calcula el pseudoinverso de M, ¿cómo podría obtener el pseudoinverso de A aparte del enfoque trivial (y quizás no muy inteligente) de ir con $pinv(CUR)$ ?

Answer 1

Sorprendentemente (porque los pseudoinversos sólo funcionan así en casos especiales), resulta que la respuesta es $$A^\dagger = R^\dagger U C^\dagger. $$ Quizás lo más sorprendente es que esto equivale a $A=CU^\dagger R$ . Aquí se da una caracterización completa de las descomposiciones CUR (teorema 4.10): https://arxiv.org/pdf/1903.09698.pdf

Un esbozo de la prueba de lo que pregunta es el siguiente:

Primero hay que tener en cuenta que si rank( $U$ ) = rank( $A$ ), entonces $A=CU^\dagger R$ por lo que basta con demostrar que $A^\dagger = R^\dagger UC^\dagger$ implica que el rango $(U)$ = rank( $A$ ).

Supongamos ahora que $A^\dagger = R^\dagger UC^\dagger$ y observe que $$ A = AA^\dagger A = AR^\dagger UC^\dagger A.$$ De ello se deduce que el rango( $A) \leq$ rango( $C$ ), pero evidentemente rank( $C) \leq$ rango( $A)$ , por lo que rank( $C$ ) = rank( $A$ ). Por un argumento similar rank( $R$ ) = rank( $A$ ).

Por último, hay que demostrar que si rank( $C$ ) = rank( $R$ ) = rank( $A$ ), entonces necesariamente rank( $U$ ) = rank( $A$ ), lo que puede hacerse mediante la SVD de $A$ .

El artículo enlazado contiene muchos más detalles de la prueba si se desea.