Multi-Matrix Completion: A Novel Framework for Structurally Missing Elements

A common assumption in matrix completion (MC) and tensor completion (TC) is that the missing locations are sampled randomly. However, in real-world scenarios, the unobserved elements are often not arbitrarily located, and may concentrate within entire rows or columns. We refer to this missing mechanism as structural missingness, and traditional MC and TC schemes suffer from drastic degradation under these circumstances. This work addresses the challenge of restoring structural missingness by introducing a novel framework for simultaneously reconstructing multiple matrices, called multi-matrix completion (MMC). In MMC, tri-factorization across matrices captures the correlation between matrices, and Tikhonov regularization on each matrix exploits its correlation. This design enables MMC to efficiently handle both random and structural missingness. In addition, MMC is not affected by the smoothness along matrices which makes it suitable for a wider variety of data compared to Fourier transform based TC methods. The alternating direction method of multipliers is utilized to solve the resultant optimization problem. The global convergence of the algorithm is supported by comprehensive theoretical analyses. We demonstrate the versatility of MMC through extensive experiments in image and video restoration, and showcase its superior performance in comparison to traditional MC and TC methods.