On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Low-Rank Inducing Norms with Optimality Interpretations
Optimization problems with rank constraints appear in many diverse fields such as control, machine learning and image analysis. Since the rank constraint is non-convex, these problems are often approximately solved via c…
Matrix CompletionRelative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix …
Low-Rank Matrix CompletionMatrix CompletionA Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the …
Low-Rank Matrix CompletionMatrix CompletionQuantum State TomographyMatrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
In this paper, we study the popularly dubbed matrix completion problem, where the task is to "fill in" the unobserved entries of a matrix from a small subset of observed entries, under the assumption that the underlying …
Matrix CompletionTruncated Nuclear Norm Minimization for Image Restoration Based On Iterative Support Detection
Recovering a large matrix from limited measurements is a challenging task arising in many real applications, such as image inpainting, compressive sensing and medical imaging, and this kind of problems are mostly formula…
Compressive SensingImage InpaintingImage RestorationMatrix Completion