In this two-part series (Part I, Part II), we study properties of generalized inverses beyond the Moore-Penrose. Freeing up the degrees of freedom associated with Frobenius optimality enables us to promote other interesting properties. In Part I, we look at the basic properties of norm-minimizing generalized inverses, especially in terms of uniqueness and relation to the MPP. We show that the MPP minimizes many norms beyond those unitarily invariant, thus further bolstering its role as a robust choice in many situations. We also study norms which are generally not minimized by the MPP, but whose minimization is relevant for linear inverse problems and sparse representations such as mixed norms and the induced norms.

To illustrate our results in Part I, we invented a visualization gadget called the norm cube. The norm cube captures various equivalences between matrix norms for particular choices of parameters. Each point on the displayed planes corresponds to a matrix norm. For example, using notations in Table 1.1 of Part I, the Schatten -norm equals the Frobenius norm as well as the entrywise -norm. The induced norm equals the Schatten -norm, while the induced norm equals the largest column -norm, that is, the columnwise mixed norm.

In Part II we focus on generalized inverses that are minimizers of entrywise norms, with the main representative being the sparse pseudoinverse for . The idea is to replace the Moore-Penrose pseudoinverse by a sparser generalized inverse which is in some sense well-behaved. Sparsity means that it is faster to multiply by the resulting matrix; well-behavedness means that we do not lose much with respect to the least-squares performance of the MPP.

We first address questions of uniqueness and non-zero count of (putative) sparse pseudoinverses, showing that a sparse pseudoinverse is generically unique and that it indeed reaches optimal sparsity for almost all matrices. We then turn to proving our main stability result: finite-size concentration bounds for the Frobenius norm of -minimal inverses for (thus including the Moore-Penrose!). Our proof is based on tools from convex analysis and random matrix theory, in particular the recently developed convex Gaussian min-max theorem. Along the way we prove several folklore facts about sparse representations and convex programming that were to the best of our knowledge thus far unproven.