Low-rank matrix completion : theory, algorithms and applications

Orientadores: Cristiano Torezzan, Carlile Campos LavorTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação CientíficaResumo: O problema de estimar dados faltantes em matrizes aparece em diversas aplicações e tem despertado interesses de pesquisadores das mais variadas áreas. Em termos gerais, o Problema de Completamento de Matrizes (PCM) consiste em determinar as entradas desconhecidas ou imprecisas de uma matriz. Em diversas situações o PCM está associado a matrizes que possuem postos reduzidos. Nestes casos, o PCM pode ser modelado como um problema de otimização, que admite uma relaxação nuclear na forma Lagrangiana por meio de um parâmetro regularizador. Neste trabalho, desenvolvemos um estudo teórico e computacional sobre o PCM com posto reduzido. Propomos uma maneira de computar a sequência associada ao parâmetro regularizador, quando o posto da matriz é conhecido visando acelerar a convergência do algoritmo conhecido na literatura como Soft-Impute. Esta modificação tem apresentado resultados computacionais relevantes permitindo, por exemplo, resolver problemas com até 99% de dados faltantes com alta precisão. Como aplicação, exploramos o completamento de Matriz de Distâncias Euclidianas (EDM) e propomos um protocolo de recuperação que explora a matriz de Gram associada à EDM. Finalmente, comparamos os resultados obtidos, usando a nossa proposta, com os resultados obtidos a partir de outros métodos e propomos aplicações relacionadas ao processamento de imagens, tanto para eliminação de ruído quanto para a construção de compressores de imagens usando o PCM. Diversos resultados numéricos atestam a eficiência das nossas propostasAbstract: The problem of estimating missing data in matrices appears in several applications and it has aroused the attention of researchers from different areas. In general, the Matrix Completion Problem (PCM) consists in determining the values of a subset of the entries in a matrix that are unknown or imprecise. In several situations the PCM is associated with matrices that have low-rank. In these cases, the PCM can be modeled as an optimization problem that admits a nuclear relaxation in the Lagrangian form, and uses a regularization parameter. In this work, we develop a theoretical and computational study on the PCM with low-rank. We propose a new way to compute the sequence associated with the regularization parameter for the case where the rank of the matrix is known a priori in order to accelerate the convergence of an algorithm known in the literature as Soft- Impute. This modification has presented relevant computational results allowing, for example, solving problems with up to 99% of missing data with high precision. As an application, we explore the Euclidean Distances Matrix (EDM) completion and propose a retrieval protocol that explores the Gram matrix associated to the EDM. Finally, we compare the results obtained, using our proposal, with the results obtained from other methods and propose applications related to image processing, both for noise elimination and for the construction of image compressors using PCM. Several numerical results attest the efficiency of our proposalsDoutoradoMatematica AplicadaDoutor em Matemática AplicadaCAPE