On Computing Sparse Generalized Inverses and Sparse-Inverse/Low-Rank Decompositions

Abstract

Pseudoinverses are ubiquitous tools for handling over- and under-determined systems of equations. For computational efficiency, sparse pseudoinverses are desirable. Recently, sparse left and right pseudoinverses were introduced, using 1-norm minimization and linear programming. We introduce several new sparse generalized inverses by using 1-norm minimization on a subset of the linear Moore-Penrose properties, again leading to linear programming. Computationally, we demonstrate the usefulness of our approach in the context of application to least-squares problems and minimum 2-norm problems.

One of the Moore-Penrose properties is nonlinear (in fact, quadratic), and so developing an effective convex relaxation for it is nontrivial. We develop a variety of methods for this, in particular a nonsymmetric lifting which is more efficient than the usual symmetric lifting that is normally applied to non-convex quadratic equations. In this context, we develop a novel and computationally effective “diving procedure” to find a path of solutions trading off sparsity against the nice properties of the Moore- Penrose pseudoinverse.

Next, we consider the well-known low-rank/sparse decomposition problem min {