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...

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

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...

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