MSE-based Sampling of Bandlimited Product Graph Signals via Joint Low-pass Impulse Responses

Abstract

Matrix graph signals, which are associated with two factor graphs, are ubiquitous in daily life, such as time-varying physical signals in sensor networks and rating matrices in recommendation systems. In practice, due to the row-wise and column-wise smoothness, they are modeled as bandlimited (BL) graph signals on the product of two factor graphs. In this paper, we propose a fast sampling method for BL product graph signals by minimizing the reconstruction mean squared error (MSE). First, we formulate the MSE-based sampling objective for BL signals on a product graph. Next, we simplify the greedy subproblem using matrix inversion approximation, which involves straightforward computations between the defined joint low-pass impulse responses (JLIRs). To eliminate the huge computation and storage complexity, we propose a strategy to directly compute the greedy evaluation score based on low-dimensional LIRs on two factor graphs, leveraging the property of Kronecker product. Employing this strategy, we also extend existing popular LIR-based methods to sample signals from single graphs to product graphs with low complexity. Extensive experiments on synthetic and real-world product graph signals demonstrate that our proposed method maintains superior MSE performance compared to other extended graph sampling schemes.