Prêmio Clóvis Gonzaga: Gabriel Oliveira da Ponte (UFRJ)

Título: On the computation of sparse reflexive generalised inverses

Resumo: The well-known Moore-Penrose (M-P) pseudoinverse is used in several linear-algebra applications; for example, to compute least-squares solutions of inconsistent systems of linear equations. Irrespective of whether a given matrix is sparse, its M-P pseudoinverse can be completely dense, potentially leading to high computational burden and numerical difficulties, especially when we are dealing with high-dimensional matrices. The M-P pseudoinverse is uniquely characterized by four properties, but not all of them need to be satisfied for some applications. In this work, we apply mathematical optimization to induce general sparsity and structured sparsity on generalized inverses of a given matrix, which satisfy only specific subsets of the M-P properties. We use 1-norm (vector) minimization to induce (unstructured) sparsity and 2,1-norm minimization to induce (structured) row-sparsity. Structured sparsity is useful, not only because of computational efficiency, but also for explainability. In the context of the least-squares application it is desirable to have row-sparsity, i.e., to have few non-zero rows on the generalized inverse, as then the associated linear model is more explainable. More specifically, least-squares theory connects explanatory variables to predicted variables (observations), through a linear regression model in which the unknown parameters of the linear relation are estimated by the least-squares solution. Row-sparsity corresponds to the selection of a small number of explanatory variables to determine a linear model. We also consider local-search procedures that produce generalized inverses with guaranteed structured sparsity, low rank, and magnitude of the entries under control.