Authors:

Autores

Person role Person
7512
3251,603,2740
7513
3251,603,2740
7514
Jon Lee (Co-supervisor)
3251,603,2740

Informations:

Pesc publication

Title
On the Computation of Sparse Reflexive Generalized Inverse
Research area
Mathematical Optimization
Publication type
Master's thesis
Identification Number
Date
12/19/2024
Resumo

A pseudo-inversa M-P (Moore-Penrose) pode ser usada em várias aplicações de álgebra linear; por exemplo, para calcular soluções de mínimos quadrados de sistemas lineares inconsistentes. Entretanto, independentemente de uma dada matriz ser esparsa, sua pseudo-inversa pode ser completamente densa, levando potencialmente a um alto custo computacional e dificuldades numéricas, especialmente ao lidarmos com matrizes de alta dimensão. A pseudo-inversa M-P é caracterizada por quatro propriedades, mas nem todas precisam ser atendidas para algumas aplicações. Nesta dissertação, investigamos a relaxação de algumas das propriedades M-P para alcançar esparsidade, seja impondo esparsidade estruturada ou induzindo esparsidade geral e esparsidade estruturada. A esparsidade estruturada é útil, não apenas por causa da eficiência computacional, mas também pela explicabilidade. No contexto da aplicação dos mínimos quadrados, é desejável ter esparsidade em linhas, ou seja, ter poucas linhas não nulas na inversa generalizada, pois assim o modelo linear associado é mais explicável. Mais especificamente, a teoria dos mínimos quadrados conecta variáveis explicativas a variáveis de resposta (observações), por meio de um modelo de regressão linear no qual os parâmetros desconhecidos da relação linear são estimados pela solução dos mínimos quadrados. A esparsidade em linhas corresponde à seleção de um pequeno número de variáveis explicativas para determinar o modelo linear. Fampa e Lee (2018) propõem um procedimento de busca local para construir, para uma dada matriz, uma inversa generalizada, esparsa em linhas, com estrutura em blocos, que satisfaz apenas a propriedade-chave da pseudo-inversa M-P e a propriedade chamada reflexiva. A propriedade-chave é essencial, pois mesmo a matriz completamente nula (bastante esparsa, mas sem nenhuma informação sobre a matriz dada), satisfaz as outras propriedades da pseudo-inversa M-P. A propriedade reflexiva é equivalente a impor uma condição de posto mínimo à inversa generalizada. Notamos que posto baixo é outra propriedade desejada para inversas generalizadas. Inversas generalizadas de posto baixo capturam outro tipo de explicabilidade (poucas "variáveis" explicativas no contexto da análise de componentes principais (PCA)). Uma garantia de aproximação para a minimização da norma-1 (vetorial) para as inversas generalizadas construídas pelo procedimento de busca local é demonstrada.

Nós estendemos este trabalho desenvolvendo, analisando teoricamente e computacionalmente diferentes métodos destinados a calcular inversas generalizadas esparsas. Nós visamos tanto a esparsidade não-estruturada quanto a esparsidade estruturada em linhas. Utilizamos a minimização da norma-1 (vetorial) para induzir esparsidade geral (não-estruturada) e a minimização da norma-2,1 para induzir esparsidade (estruturada) em linhas. É importante notar que, além de induzir a esparsidade, a minimização da norma também mantém controlada a magnitude das entradas das inversas generalizadas construídas, que pode ter um impacto numérico relevante. A maioria dos métodos propostos se concentra na aplicação da inversa generalizada na solução do problema de mínimos quadrados. Neste caso, garantimos que as duas propriedades necessárias da pseudo-inversa M-P sejam satisfeitas pelas inversas generalizadas esparsas construídas. Nossos métodos são baseados em modelos de otimização e em procedimentos de busca local. Investigamos modelos de otimização linear com minimização da norma-1 para induzir esparsidade nas inversas generalizadas construídas e modelos de otimização de cone de segunda ordem com minimização da norma-2,1 para induzir a esparsidade em linha. Demonstramos as propriedades dos modelos propostos com respeito à satisfação das propriedades da pseudo-inversa M-P. Além disso, ainda baseados em modelos de otimização, investigamos o trade-off entre norma-1 pequena e posto pequeno para inversas generalizadas que podem ser usadas no cálculo de soluções de mínimos quadrados e propomos diversas abordagens algorítmicas que começam com uma inversa generalizada que minimiza a norma-1 e que satisfaz as duas propriedades da pseudo-inversa M-P necessárias para a solução de mínimos quadrados, diminuindo gradualmente seu posto ao impor iterativamente a propriedade reflexiva. Finalmente, visando inversas generalizadas que resolvem o problema de mínimos quadrados, estendemos o trabalho de Fampa e Lee (2018), em particular para inversas generalizadas que minimizam aproximadamente a norma-1 e que satisfazem a propriedade adicional necessária para a solução de mínimos quadrados, usando uma construção em blocos de coluna para manter a esparsidade em linhas durante a busca local. Oferecemos uma garantia de aproximação na minimização da norma-1 para as inversas generalizadas construídas. Uma análise numérica baseada em experimentos extensivos  é fornecida para todos os métodos propostos.

Abstract

The well-known M-P (Moore-Penrose) 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 dissertation, we investigate the relaxation of some of the M-P properties to achieve sparsity, either by imposing structured sparsity or by inducing general sparsity and structured 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 variable to determine linear model. Fampa and Lee (2018) propose a local-search procedure to construct, for a given matrix, a row-sparse block-structured generalized inverse that satisfies only the key M-P property plus the so-called reflexive property. The key property is essential, as even the all-zero matrix very sparse, but with no information about the given matrix), satisfies the other M-P properties. The reflexive property is equivalent to imposing a minimum-rank condition on the generalized inverse. We note that low rank is another desired property for generalized inverses. Low-rank generalized inverses capture another kind of explainability (few explanatory "variables" in the context of principal components analysis (PCA)). An approximation guarantee on (vector) 1-norm minimization for the generalized inverses constructed by the local-search procedure is demonstrated.

We extend this work by developing, analyzing theoretically and computationally different methods aimed at computing sparse generalized inverses. We target both unstructured general sparsity and structured row-sparsity. We use 1-norm (vector) minimization to induce (unstructured) sparsity and 2,1-norm minimization to induce (structured) row-sparsity. It is important to note that, in addition to inducing sparsity, norm minimization also keeps the magnitude of the entries under control for the constructed generalized inverses, which can have relevant numerical impact. Most of the proposed methods focus on applying the generalized inverse to the solution of the least-squares problem. In this case, we ensure that the two required M-P properties are satisfied by the constructed sparse generalized inverses. Our methods are based on optimization models and on local-search procedures. We investigate linear-optimization models with 1-norm minimization to induce sparsity on the constructed generalized inverses and second-order-cone optimization models with 2,1-norm minimization to induce row-sparsity. We demonstrate properties of the proposed models with respect to the satisfaction of the M-P properties. Furthermore, still based on optimization models, we investigate the trade-off between low 1-norm and low rank for generalized inverses that can be used in the computation of least-squares solutions and propose several algorithmic approaches that start from a 1-norm minimizing generalized inverse that satisfies the two required M-P properties for the least-squares solution and gradually decrease its rank by iteratively imposing the reflexive property. Finally, targeting generalized inverses that solve the least-squares problem, we extend the work in Fampa and Lee (2018), in particular to approximate 1-norm minimizing generalized inverses that satisfy the additional required property for the least-squares solution, using a column-block construction to maintain row sparsity during a local search. We give an approximation guarantee in 1-norm minimization for the constructed generalized inverses. A numerical analysis based on extensive experiments is provided for all the proposed methods.

JSN_TPLFW_GOTO_TOP