Greedy Algorithm with Approximation Ratio for Sampling Noisy Graph Signals

Changlong Wu; Wenxin Chen; June Zhang

ICASSP 2018accepted0 citations

Greedy Algorithm with Approximation Ratio for Sampling Noisy Graph Signals

Abstract

We study the optimal sampling set selection problem in sampling a noisy k -bandlimited graph signal. To minimize the effect of noise when trying to reconstruct a k -bandlimited graph signal from m samples, the optimal sampling set selection problem has been shown to be equivalent to finding a m×k submatrix with the maximum smallest singular value, σmin [3]. As the problem is NP-hard, we present a greedy algorithm inspired by a similar submatrix selection problem known in computer science and to which we add a local search refinement. We show that 1) in experiments, our algorithm finds a submatrix with larger σmin than prior greedy algorithm [3], and 2) has a proven worst-case approximation ratio of 1/(1+ε)k, where ε is a constant.

BibTeX

@inproceedings{icassp2018_greedyalgorithmw,
  title = {Greedy Algorithm with Approximation Ratio for Sampling Noisy Graph Signals},
  author = {Changlong Wu and Wenxin Chen and June Zhang},
  booktitle = {ICASSP 2018},
  year = {2018}
}