Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift
Matrix completion algorithms fill missing entries in a large matrix given a subset of observed samples. The problem of how to pre-select a subset of entries for sampling to maximize the reconstructed matrix fidelity is largely unaddressed. In this paper, we propose two sampling algorithms to tackle this problem: (i) a fast base sampling algorithm on general single graphs, and (ii) an extended sampling algorithm from the base algorithm for active matrix completion. Assuming the double graph smoothness prior where rows / columns of the matrix signal are smooth with respect to row / column factor graphs, we first show that a matrix signal can be recovered from partial observations by solving a system of linear equations <inline-formula><tex-math notation="LaTeX">${\mathbf Q}{\mathbf x}={\mathbf y}$</tex-math></inline-formula>, where the sought matrix is vectorized as <inline-formula><tex-math notation="LaTeX">${\mathbf x}$</tex-math></inline-formula> and interpreted as a signal residing on a single graph. On this single graph, to promote small reconstruction error and stability of the linear system, we maximize the smallest eigenvalue <inline-formula><tex-math notation="LaTeX">$\lambda _{\min }$</tex-math></inline-formula> of <inline-formula><tex-math notation="LaTeX">${\mathbf Q}$</tex-math></inline-formula> by greedily selecting samples corresponding to the largest magnitude entries in the first eigenvectors of <inline-formula><tex-math notation="LaTeX">${\mathbf Q}$</tex-math></inline-formula>, based on a corollary of the Gershgorin circle theorem. Extending to the active matrix completion case, we alternately choose entries in the rows and columns corresponding to the largest magnitude entries in the first eigenvectors of the row / column coefficient matrices <inline-formula><tex-math notation="LaTeX">${\mathbf Q}_r$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">${\mathbf Q}_c$</tex-math></inline-formula>. Our algorithm benefits computationally from warm start as the first eigenvectors are computed recurrently for more samples. Extensive experiments on both synthetic and real-world datasets show that our extended graph sampling algorithm outperforms existing sampling schemes for matrix completion, when combined with a range of modern matrix completion algorithms.