Fast matrix completion without the condition number
We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Fast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion
We formulate the problem of matrix completion with and without side information as a non-convex optimization problem. We design fastImpute based on non-convex gradient descent and show it converges to a global minimum th…
Matrix CompletionFast Exact Matrix Completion with Finite Samples
Matrix completion is the problem of recovering a low rank matrix by observing a small fraction of its entries. A series of recent works [KOM12,JNS13,HW14] have proposed fast non-convex optimization based iterative algori…
Matrix CompletionFaster Matrix Completion Using Randomized SVD
Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decompositio…
CPUImage InpaintingMatrix CompletionRecommendation SystemsModel-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positi…
ClusteringDimensionality ReductionMatrix CompletionSpeedup Matrix Completion with Side Information: Application to Multi-Label Learning
In standard matrix completion theory, it is required to have at least $O(n\ln^2 n)$ observed entries to perfectly recover a low-rank matrix $M$ of size $n\times n$, leading to a large number of observations when $n$ is l…
Matrix CompletionMulti-Label Learning