Completamento de Matrizes usando Métodos de Projeção

Abstract

Neste estudo buscamos encontrar soluções para o problema de completamento de matrizes de distância Euclidianas, utilizando métodos de projeções. As matrizes de distância são muito importantes no estudo de problemas de geometria de distâncias, pois permitem descrever as distâncias entre os pontos como entradas de uma matriz. O completamento de uma matriz é a sua reconstituição a partir de um subconjunto de seus elementos conhecidos. Este também pode ser compreendido como um problema de viabilidade, em que a solução encontra-se na intersecção de conjuntos. Para encontrar a solução deste problema, foram estudados e implementados os seguintes métodos de projeções: o método das projeções alternadas, Douglas-Rachford, reflexões circuncentradas e o método de reflexões circuncentradas centralizado. Estes métodos foram minuciosamente comparados, quando resolvendo o problema de completamento de matrizes, por uma série de experimentos numéricos.

In this study we seek to find solutions to the problem of completing Euclidean distance matrices using projection methods. Distance matrices are very important in the study of distance geometry problems, as they allow us to describe the distances between points as entries of a matrix. The completion of a matrix is its reconstruction from a subset of its elements. It can also be seen as a feasibility problem. To find the solution of this feasibility problem, the following projection methods were studied and implemented: the method of alternating projections, Douglas-Rachford method , and the circumcentered-reflections and the centralized circumcetered-reflections methods. Those methods were thoroughly compared, when solving the matrix completing problem, through a series of numerical experiments.