Sharp Bounds for Multiple Models in Matrix Completion

Abstract

In this paper, we demonstrate how a class of advanced matrix concentration inequalities, introduced in \cite{brailovskaya2024universality}, can be used to eliminate the dimensional factor in the convergence rate of matrix completion. This dimensional factor represents a significant gap between the upper bound and the minimax lower bound, especially in high dimension. Through a more precise spectral norm analysis, we remove the dimensional factors for three popular matrix completion estimators, thereby establishing their minimax rate optimality.

37 pages. Accepted by the Electronic Journal of Statistics. All comments are warmly welcomed