Métodos para completamento de matrizes de posto conhecido [recurso eletrônico]
Tacildo de Souza Araújo
TESE
Português
T/UNICAMP Ar15m
[Methods for known-rank matrix completion]
Campinas, SP : [s.n.], 2023.
1 recurso online (86 p.) : il., digital, arquivo PDF.
Orientadores: Cristiano Torezzan, Douglas Soares Gonçalves
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Resumo: O Problema de Completamento de Matrizes (PCM) consiste em estimar as entradas em falta de uma matriz, a partir de um subconjunto de entradas conhecidas. Esse problema pode ser formulado como um problema de otimização com a condição de que a matriz a ser completada tenha posto reduzido. Além...
Ver mais
Resumo: O Problema de Completamento de Matrizes (PCM) consiste em estimar as entradas em falta de uma matriz, a partir de um subconjunto de entradas conhecidas. Esse problema pode ser formulado como um problema de otimização com a condição de que a matriz a ser completada tenha posto reduzido. Além disso, em algumas aplicações, o posto da matriz alvo é conhecido a priori e esta informação pode ser útil para o processo de completamento da matriz. Esta tese concentra-se no estudo de métodos de otimização para o completamento de matrizes de posto conhecido. Inicialmente, propomos um método que utiliza a informação do posto alvo e uma decomposição SVD truncada em cada iteração. Estabelecemos uma condição sob a qual a sequência gerada pelo método é quasi-Fejér convergente para o conjunto solução do problema. Em seguida, incluímos um mecanismo de aceleração semelhante à aceleração de Nesterov para obter uma heurística que, embora não tenha garantia de convergência, pode ser usada para a obtenção de um bom ponto inicial, bem como um valor para o parâmetro de regularização para um método de gradiente proximal acelerado que visa resolver um problema de quadrados mínimos regularizado pela norma nuclear. Uma segunda contribuição da tese consiste na aplicação de um método de gradiente projetado para resolver um problema de otimização com restrição de posto que modela o PCM. O principal desafio dessa abordagem está na escassez de resultados de convergência para o gradiente projetado (GP) em conjuntos não-convexos, que sejam baseados em hipóteses razoáveis na prática. Utilizando a propriedade de isometria restrita, bem como, assumindo conhecido o posto da matriz alvo, mostramos que a sequência gerada pelo algoritmo de GP proposto converge para a solução do problema. Todos os métodos propostos foram testados, tanto com dados sintéticos, quanto em conjuntos de dados reais usualmente utilizados na área. Os resultados computacionais obtidos mostram que os métodos propostos têm desempenho similar aos principais métodos da literatura, com a vantagem de controlar o posto da matriz resultante
Ver menos
Abstract: The Matrix Completion Problem (MCP) consists in estimating the missing entries of a matrix from a subset of known entries. This problem can be formulated as an optimization problem with the condition that the matrix to be completed has a low rank. Furthermore, in some applications, the...
Ver mais
Abstract: The Matrix Completion Problem (MCP) consists in estimating the missing entries of a matrix from a subset of known entries. This problem can be formulated as an optimization problem with the condition that the matrix to be completed has a low rank. Furthermore, in some applications, the rank of the target matrix is known in advance; this information can be helpful during the matrix completion process. This thesis focuses on the study of optimization methods for the completion of matrices that have known rank. Initially, we propose a method that uses the target rank information and a truncated SVD decomposition at each iteration. We establish a condition under which the generated sequence is quasi-Fejér convergent to the solution set of the problem. We then include an acceleration mechanism similar to Nesterov’s acceleration to obtain a heuristic that, although the convergence is not guaranteed, can be used to obtain a good starting point, as well as a value for the regularization parameter for an accelerated proximal gradient method that aims to solve a nuclear norm regularized least squares problem. A second contribution of the thesis consists of the application of a projected gradient method to solve a rank-constrained optimization problem that models the PCM. The main challenge of this approach lies in the scarcity of convergence results for the projected gradient (GP) on non-convex sets that are based on reasonable assumptions in practice. Using the restricted isometry property, as well as, assuming that the rank of the target matrix is known, we show that the sequence generated by the proposed GP algorithm converges to the solution of the problem. All the proposed methods have been tested, both with synthetic data and on real data sets commonly used in the field. The computational results obtained show that the proposed methods perform similarly to the main methods in the literature, with the advantage of controlling the rank of the resulting matrix
Ver menos
Torezzan, Cristiano, 1976-
Orientador
Gonçalves, Douglas Soares, 1982-
Coorientador
Lavor, Carlile Campos, 1968-
Avaliador
Bueno, Luís Felipe Cesar da Rocha, 1983-
Avaliador
Métodos para completamento de matrizes de posto conhecido [recurso eletrônico]
Tacildo de Souza Araújo
Métodos para completamento de matrizes de posto conhecido [recurso eletrônico]
Tacildo de Souza Araújo