Universal Matrix Completion
The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled afresh. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties. Moreover, we also show that under certain stricter incoherence conditions, $O(nr^2)$ uniformly sampled entries are enough to recover any rank-$r$ $n\times n$ matrix, in contrast to the $O(nr\log n)$ sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Low-rank matrix completion and denoising under Poisson noise
This paper considers the problem of estimating a low-rank matrix from the observation of all or a subset of its entries in the presence of Poisson noise. When we observe all entries, this is a problem of matrix denoising…
DenoisingLow-Rank Matrix CompletionMatrix CompletionExact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent
Factorization-based gradient descent is a scalable and efficient algorithm for solving low-rank matrix completion. Recent progress in structured non-convex optimization has offered global convergence guarantees for gradi…
Low-Rank Matrix CompletionMatrix CompletionStatistical Inferences of Linear Forms for Noisy Matrix Completion
We introduce a flexible framework for making inferences about general linear forms of a large matrix based on noisy observations of a subset of its entries. In particular, under mild regularity conditions, we develop a u…
Matrix CompletionMatrix Completion with Hierarchical Graph Side Information
We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical gr…
ClusteringGraph ClusteringMatrix CompletionStochastic Block ModelTransfer Learning for Matrix Completion
In this paper, we explore the knowledge transfer under the setting of matrix completion, which aims to enhance the estimation of a low-rank target matrix with auxiliary data available. We propose a transfer learning proc…
Transfer Learning