On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
Yunhua Xiang, Tianyu Zhang, Xu Wang, Ali Shojaie, Noah Simon; 24(228):1−38, 2023.
Abstract
Originally developed for imputing missing entries in low rank or approximately low rank matrices, nuclear-norm-based matrix completion has proven to be widely effective in many problems where there is no assumption of low-dimensional linear structure in the underlying matrix. This manuscript demonstrates that nuclear-norm-based matrix completion achieves a rate within a log factor of the minimax rate for estimating the mean structure of matrices that are not necessarily low-rank but lie in a low-dimensional non-linear manifold, when observations are missing completely at random. The convergence rate is determined by the number of rows, columns, and observed entries in the matrix, as well as the smoothness and dimension of the non-linear embedding. Additionally, a minimax lower bound is provided, which corroborates the upper bound (up to a logarithmic factor) and confirms that nuclear-norm penalization is (up to log terms) minimax rate optimal for these problems.
[abs]