On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Yunhua Xiang;Tianyu Zhang;Xu Wang;A. Shojaie;N. Simon
中科院分区：
文献类型：
--
作者：
Yunhua Xiang;Tianyu Zhang;Xu Wang;A. Shojaie;N. Simon
矩阵补全最初是为了在低秩或近似低秩矩阵中输入缺失条目而开发的，在许多没有理由在底层矩阵中假设低维线性结构的问题中，矩阵补全已经被证明是广泛有效的，因为秩约束会强加给这些问题。在这篇文章中，我们建立了一些关于这种行为的理论直觉。我们考虑的矩阵不一定是低秩的，但在一个低维的非线性流形。我们表明，当观察完全随机丢失时，核规范惩罚仍然有效地恢复这些矩阵。特别地，我们给出了收敛速度的上界，作为矩阵中行、列和观察条目的数量的函数，以及非线性嵌入的平滑度和维数。我们还给出了一个极大极小下界：这个下界与我们的上界（直到一个对数因子）一致，这表明核范数惩罚（直到对数项）对于这些问题来说是极大极小率最优的。
Originally developed for imputing missing entries in low rank, or approximately low rank matrices, matrix completion has proven widely effective in many problems where there is no reason to assume low-dimensional linear structure in the underlying matrix, as would be imposed by rank constraints. In this manuscript, we build some theoretical intuition for this behavior. We consider matrices which are not necessarily low-rank, but lie in a low-dimensional non-linear manifold. We show that nuclear-norm penalization is still effective for recovering these matrices when observations are missing completely at random. In particular, we give upper bounds on the rate of convergence as a function of the number of rows, columns, and observed entries in the matrix, as well as the smoothness and dimension of the non-linear embedding. We additionally give a minimax lower bound: This lower bound agrees with our upper bound (up to a logarithmic factor), which shows that nuclear-norm penalization is (up to log terms) minimax rate optimal for these problems.