The Moore-Penrose (M-P) pseudoinverse is a key object in matrix theory and applications. The M-P pseudoinverse is characterized by the four well-known M-P properties. But not all of these properties are needed for the use of it in applications like least-squares fitting. When a matrix is not full rank, there can be much sparser generalized inverses than the M-P pseudoinverse that solve the least-squares problem for arbitrary response vectors. Besides sparsity and even structured sparsity, we are interested in low-rank and low-norm solutions. We approach the problem of generating such generalized inverses using a variety of optimization methods, including linear optimization, second-order-cone optimization, first-order methods, and local-search based approximation algorithms.