Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift

Abstract

Matrix completion algorithms fill missing entries in a large matrix given a subset of observed samples. However, how to best pre-select informative matrix entries given a sampling budget is largely unaddressed. In this paper, we propose a fast sample selection strategy for matrix completion from a graph signal processing perspective. 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 select appropriate samples to maximize the smallest eigenvalue ${\lambda }_{\min }$ of the coefficient matrix, thus maximizing the stability of the linear system. To efficiently solve this combinatorial problem, we derive a greedy sampling strategy, leveraging on Gershgorin circle theorem, that iteratively selects one sample (equivalent to shifting one Gershgorin disc) at a time corresponding to the largest magnitude entry in the first eigenvector of a modified graph Laplacian matrix. Our algorithm benefits computationally from warm start as the first eigenvectors of incremented Laplacian matrices are computed recurrently for more samples. To achieve computation scalability when sampling large matrices, we further rewrite the coefficient matrix as a sum of two separate components, each of which exhibits 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 algorithm substantially outperforms existing sampling schemes for matrix completion and reduces the completion error, when combined with a range of modern matrix completion algorithms.

References in corpus (20)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Graph Convolutional Matrix Completion
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• GSPBOX: A toolbox for signal processing on graphs
• Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain
• Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks
• Graph-Based Blind Image Deblurring From a Single Photograph
• Matrix Completion on Graphs
• Greedy Sampling of Graph Signals
• Feature Graph Learning for 3D Point Cloud Denoising
• Eigendecomposition-Free Sampling Set Selection for Graph Signals
• Sensor placement by maximal projection on minimum eigenspace for linear inverse problems
• Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment
• Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
• Sparse Sampling for Inverse Problems with Tensors
• A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series
• Matrix completion with queries
• 3D Point Cloud Denoising via Bipartite Graph Approximation and Reweighted Graph Laplacian

Cited by in corpus (3)

• Sampling Signals on Graphs: From Theory to Applications
• Fast sensor placement by enlarging principle submatrix for large-scale linear inverse problems
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection