18 March 2020 in IEEE Transactions on Signal Processing
Graph sampling set selection, where a subset of nodes are chosen to collect samples to reconstruct a bandlimited or smooth graph signal, is a fundamental problem in graph signal processing (GSP). Previous works employ an unbiased least square (LS) signal reconstruction scheme and select samples via expensive extreme eigenvector computation. Instead, we assume a biased graph Laplacian regularization (GLR) based scheme that solves a system of linear equations for reconstruction. We then choose samples to minimize the condition number of the coefficient matrix---specifically, maximize the smallest eigenvalue ${\lambda_{min}}$ . Circumventing explicit eigenvalue computation, we maximize instead the lower bound of ${\lambda_{min}}$ , designated by the smallest left-end of all Gershgorin discs of the matrix. To achieve this efficiently, we first convert the optimization to a dual problem, where we minimize the number of samples needed to align all Gershgorin disc left-ends at a chosen lower-bound target T. Algebraically, the dual problem amounts to optimizing two disc operations: i) shifting of disc centers due to sampling, and ii) scaling of disc radii due to a similarity transformation of the matrix. We further reinterpret the dual to an intuitive disc coverage problem bearing strong resemblance to the famous NP-hard set cover (SC) problem. The reinterpretation enables us to derive a fast approximation algorithm from a known SC error-bounded approximation algorithm. We find the appropriate target ${T}$ efficiently via binary search. Experiments on real graph data show that our disc-based sampling algorithm runs substantially faster than existing sampling schemes and outperforms other eigen-decomposition-free sampling schemes in reconstruction error.
9 September 2019 in IEEE Transactions on Signal Processing
Graph sampling addresses the problem of selecting a node subset in a graph to collect samples, so that a $K$ -bandlimited signal can be reconstructed in high fidelity. Assuming an independent and identically distributed (i.i.d.) noise model, minimizing the expected mean square error (MMSE) leads to the known A-optimality criterion for graph sampling, which is expensive to compute and difficult to optimize. In this paper, we propose an augmented objective based on Neumann series that well approximates the original criterion and is amenable to greedy optimization. Specifically, we show that a shifted A-optimal criterion can be equivalently written as a function of an ideal low-pass (LP) graph filter, which in turn can be approximated efficiently via fast graph Fourier transform (FGFT). Minimizing the new objective, we select nodes greedily without large matrix inversions using a matrix inverse lemma. Further, for the dynamic network case where node availability varies across time, we propose an extended sampling strategy that replaces offline samples one-by-one in the selected set. For signal reconstruction, we propose an accompanied biased signal recovery strategy that reuses the approximated filter from sampling. Experiments show that our reconstruction is more robust to large noise than the least square (LS) solution, and our sampling strategy far outperforms several existing schemes.
23 March 2018 in IEEE Signal Processing Letters
Graph signal processing (GSP) studies signals that live on irregular data kernels described by graphs. One fundamental problem in GSP is sampling-from which subset of graph nodes to collect samples in order to reconstruct a bandlimited graph signal in high fidelity. In this letter, we seek a sampling strategy that minimizes the mean square error (MSE) of the reconstructed bandlimited graph signals assuming an independent and identically distributed noise model-leading naturally to the A-optimal design criterion. To avoid matrix inversion, we first prove that the inverse of the information matrix in the A-optimal criterion is equivalent to a Neumann matrix series. We then transform the truncated Neumann series-based sampling problem into an equivalent expression that replaces eigenvectors of the Laplacian operator with a submatrix of an ideal low-pass graph filter. Finally, we approximate the ideal filter using a Chebyshev matrix polynomial. We design a greedy algorithm to iteratively minimize the simplified objective. For signal reconstruction, we propose an accompanied signal reconstruction strategy that reuses the approximated filter submatrix and is provably more robust than conventional least square recovery. Simulation results show that our sampling strategy outperforms two previous strategies in MSE performance at comparable complexity.
22 December 2021 in Functional Materials Letters
20 April 2020 in IEEE Transactions on Signal Processing
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 ${\mathbf Q}{\mathbf x}={\mathbf y}$ , where the sought matrix is vectorized as ${\mathbf x}$ 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 $\lambda _{\min }$ of ${\mathbf Q}$ by greedily selecting samples corresponding to the largest magnitude entries in the first eigenvectors of ${\mathbf Q}$ , 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 ${\mathbf Q}_r$ and ${\mathbf Q}_c$ . 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.
24 August 2022 in IEEE Transactions on Signal Processing
Signals typical in the real world have different modes, expressed as vectors, matrices, or higher-order tensors. In practice, a target signal is commonly assumed to be linear in the residing factor mode(s) with low-dimensional parameters, and thus can be recovered from partial samples by solving a linear inverse problem (LIP). Sampling for LIPs is to partially query signals for better recovery. There exist many fast sampling methods for vector signals, but they are not applicable for higher-order tensors due to high computation and storage costs. In this paper, we propose a fast sampling algorithm for vector signals first and then extend it to sample tensors with low complexity. Specifically, a tensor signal with $R$ modes is modelled as multilinear on $R$ factor matrices ${\mathbf \{U_{i}\}}^{R}_{i=1}$, whose vectorized version is linear on a matrix $\pmb {\Phi }$—the Kronecker product of $\mathbf {U}_{i}$'s. Thus, it can be estimated from partial noisy samples via the least-squares (LS) method, where the mean square error (MSE) depends on chosen samples and matrix $\pmb {\Phi }$. Instead of MSE, we minimize a modified MSE problem and prove it has the same optimal and greedy solutions to a problem with a sample-dependent sub-matrix of $\pmb {\Phi }\pmb {\Phi }^\top$. For one-order vector signals, where $\pmb {\Phi }=\mathbf {U}_{1}$ is given, we propose a fast algorithm to solve the sampling problem via simple vector-vector multiplications based on a matrix inversion formula and greedy solution reuse. For higher-order tensors, we extend our sampling algorithm to select entries by addressing matrices $\mathbf {U}_{i}$'s directly, thus removing the burden of obtaining $\pmb {\Phi }$ explicitly. Accompanying our sampling strategy, we propose an iterative reconstruction scheme to estimate the LS solution. Experiments on synthetic and real-world signals from vectors to tensors validated the performance and efficacy of our strategy compared to previous methods.