Sharp Bounds for Multiple Models in Matrix Completion

2024/11/20 by Liu, Dali, Weng, Haolei
#FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2411.13199

Abstract

In this paper, we demonstrate how a class of advanced matrix concentration inequalities, introduced in \citebrailovskaya2024universality, 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.

Related

• Matrix completion by singular value thresholding: sharp bounds
• Structured Matrix Estimation and Completion
• Unified View of Matrix Completion under General Structural Constraints
• Fast matrix completion without the condition number
• Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion