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

[摘要] 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 problemmin {

[发布机构] University of Michigan

[效力级别] Computational Mathematics

[关键词] Sparse Optimization;Computational Mathematics;Moore-Penrose Pseudoinverse;Convex Relaxation;Matrix Decomposition;Industrial and Operations Engineering;Engineering;Industrial & Operations Engineering