Matrix Completion from Non-Uniformly Sampled Entries
This addresses the problem of efficient matrix completion for applications like recommendation systems or data imputation, but it is incremental as it builds on existing low-rank matrix completion methods with a specific sampling strategy.
The paper tackles matrix completion from non-uniformly sampled entries, including fully and partially observed columns, by first recovering the column space from fully observed columns and then completing each partially observed column within that space. It shows exact recovery from Ω(rn ln n) entries for low-rank matrices and provides an additive error bound for noisy cases, with experimental verification on synthetic datasets.
In this paper, we consider matrix completion from non-uniformly sampled entries including fully observed and partially observed columns. Specifically, we assume that a small number of columns are randomly selected and fully observed, and each remaining column is partially observed with uniform sampling. To recover the unknown matrix, we first recover its column space from the fully observed columns. Then, for each partially observed column, we recover it by finding a vector which lies in the recovered column space and consists of the observed entries. When the unknown $m\times n$ matrix is low-rank, we show that our algorithm can exactly recover it from merely $Ω(rn\ln n)$ entries, where $r$ is the rank of the matrix. Furthermore, for a noisy low-rank matrix, our algorithm computes a low-rank approximation of the unknown matrix and enjoys an additive error bound measured by Frobenius norm. Experimental results on synthetic datasets verify our theoretical claims and demonstrate the effectiveness of our proposed algorithm.