On Sparse Reflexive Generalized Inverses
This work addresses the problem of computing sparse generalized inverses for matrix analysis, offering theoretical guarantees but is incremental in nature.
The paper provides constructions for sparse reflexive generalized inverses of real matrices, achieving at most r^2 nonzeros, and for rank-1 and rank-2 nonnegative matrices minimizes the 1-norm. For general rank, it finds inverses with 1-norm within a factor of r^2 of the minimum.
We study sparse generalized inverses $H$ of a rank-$r$ real matrix $A$. We give a construction for reflexive generalized inverses having at most $r^2$ nonzeros. For $r=1$ and for $r=2$ with $A$ nonnegative, we demonstrate how to minimize the (vector) 1-norm over reflexive generalized inverses. For general $r$, we efficiently find reflexive generalized inverses with 1-norm within approximately a factor of $r^2$ of the minimum 1-norm generalized inverse.