Abstract
While matrix completion algorithms fill missing entries in a matrix given a subset of samples, how to best pre-select matrix entries to collect informative observations given a sampling budget is largely unaddressed. In this paper, we propose a fast graph sampling algorithm to select entries for matrix completion. Specifically, we first regularize the matrix reconstruction objective using a dual graph signal smoothness prior, resulting in a system of linear equations for solution. We then seek to maximize the smallest eigenvalue $\lambda_{\min}$ of the coefficient matrix by choosing appropriate samples, thus maximizing the stability of the linear system. To efficiently optimize this combinatorial problem, we derive a greedy sampling strategy, leveraging on Gershgorin circle theorem, that iteratively selects one sample at a time corresponding to the largest magnitude entry in the first eigenvector of a shifted graph Laplacian matrix. Our algorithm benefits computationally from warm start as the first eigenvectors of progressively shifted Laplacian matrices are computed recurrently for more samples. Towards computation-scalable sampling on large matrices, we further rewrite the coefficient matrix as a sum of two separate components, each of which exhibits attractive block-diagonal structure that we exploit for alternating block-wise sampling. Extensive experiments on both synthetic and real-world datasets show that our graph sampling algorithms substantially outperform existing sampling schemes for matrix completion, when combined with a range of modern matrix completion algorithms.
Introduction
Matrix Completion (MC) is the process of estimating missing entries in a large data matrix from a sparse set of observations. While significant research has focused on reconstruction algorithms, the problem of "active sampling"—strategically selecting which entries to observe under a fixed budget—is often overlooked. Random sampling is the standard baseline, but it frequently fails to capture the most informative data points. Existing active sampling methods often suffer from high computational complexity or restrictive sampling structures (e.g., only allowing row/column sampling).
This paper proposes a fast, deterministic, and unstructured sampling strategy. By modeling the matrix as a signal on a graph and applying Dual Graph Laplacian Regularization (DGLR), the authors frame sampling as an optimization of the reconstruction system's numerical stability.
Methodology
Stability and the E-Optimality Criterion
The reconstruction objective is formulated as a linear system $Qx = y$. To ensure that the solution is robust to noise, the authors aim to maximize the smallest eigenvalue ($\lambda_{\min}$) of the coefficient matrix $Q$. This is known as the E-optimality criterion in experimental design, which minimizes the upper bound of the Mean Squared Error (MSE).
Greedy Selection via Gershgorin Circle Theorem
Directly maximizing $\lambda_{\min}$ for every possible sample is computationally prohibitive. To address this, the authors leverage the Gershgorin Circle Theorem (GCT). They prove that adding a sample is equivalent to shifting a Gershgorin disc. The optimal greedy choice at each step is to select the node corresponding to the largest magnitude entry in the first eigenvector of the current shifted graph Laplacian.
Recurrent Computation and Scalability
To maintain high performance, the algorithm employs the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method. By using a "warm start"—initializing the eigenvector computation with the result from the previous iteration—the computational cost per sample is significantly reduced. For extremely large matrices, the authors introduce the Iterative Gershgorin Circle Shift (IGCS) algorithm, which decomposes the problem into row and column components to maintain linear complexity.
Key Insights: Energy Spread
A core intuition behind the algorithm is the concept of "spectral energy." The algorithm identifies nodes with high energy in the graph spectrum. Once a node is sampled, its energy effectively drops, forcing the greedy selection to move toward other unsampled clusters or communities in the graph. This ensures a diverse and informative set of samples.
Experimental Results
The proposed GCS and IGCS algorithms were evaluated on synthetic data and various real-world recommendation datasets, including MovieLens and YahooMusic. The results demonstrate that these sampling strategies consistently lead to lower Root Mean Squared Error (RMSE) across multiple matrix completion algorithms (such as SVT and Graph Convolutional Matrix Completion) compared to random sampling or Leverage Score Sampling (LSS). The performance gap is particularly notable in scenarios with low signal-to-noise ratios.
Conclusion
This work presents a scalable and theoretically grounded approach to active sampling for matrix completion. By combining Graph Signal Processing with the Gershgorin Circle Theorem, the authors provide a method that is both fast and highly effective at selecting informative samples. Future work may explore dynamic graph updates to further refine the sampling process as data is collected.
Summary updated