Given a matrix A, I know there is a way to get its pseudo-inverse (a.k.a. Moore-Penrose inverse) from its SVD. If $A = USV^T$, then
$A^{\dagger} = VS^{\dagger}U^T$
Let's, instead, imagine I know a CUR decomposition of A, that is $A = CUR$, where:
- $C = A(:, \mathcal{C})$ (where $A(:, \mathcal{C})$ means $A$ restricted to a set of columns $\mathcal{C}$)
- $R = A(\mathcal{R}, :)$ (where $A(\mathcal{R}, :)$ means $A$ restricted to a set of rows $\mathcal{R}$)
- $U = A(\mathcal{R}, \mathcal{C})^{-1}$ (where $A(\mathcal{R}, \mathcal{C})$ means $A$ restricted to a set of rows $\mathcal{R}$ and a set of columns $\mathcal{C}$)
Then how can I derive an expression for $A^{\dagger}$ (pseudo -inverse of A) using the factors $C$, $U$ and $R$?
Alternatively, supposing I have a blackbox $pinv(M)$ which computes the pseudo-inverse of M, how could I get the pseudo-inverse of A apart from the trivial (and maybe not really smart) approach of going with $pinv(CUR)$?
Surprisingly (because pseudoinverses only work this way in special cases), it turns out that the answer is $$A^\dagger = R^\dagger U C^\dagger. $$ Perhaps more surprisingly, this is equivalent to $A=CU^\dagger R$. A full characterization of CUR Decompositions is given here (Theorem 4.10): https://arxiv.org/pdf/1903.09698.pdf
A sketch of the proof of what you are asking is as follows:
First note that if rank($U$) = rank($A$), then $A=CU^\dagger R$, so it suffices to show that $A^\dagger = R^\dagger UC^\dagger$ implies that rank$(U)$ = rank($A$).
Now assume $A^\dagger = R^\dagger UC^\dagger$ and note that $$ A = AA^\dagger A = AR^\dagger UC^\dagger A.$$ It follows that rank($A) \leq$ rank($C$), but evidently rank($C) \leq$ rank($A)$, so rank($C$) = rank($A$). By similar argument rank($R$) = rank($A$).
Finally, one must show that if rank($C$) = rank($R$) = rank($A$), then necessarily rank($U$) = rank($A$) which can be done via the SVD of $A$.
The linked article contains many more details of the proof if desired.