Greedy Algorithm with Approximation Ratio for Sampling Noisy Graph Signals

Changlong Wu, Wenxin Chen, June ZhangICASSP 2018 · OpenReview

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{wu2018greedy,
  author = {Changlong Wu and Wenxin Chen and June Zhang},
  title = {{Greedy Algorithm with Approximation Ratio for Sampling Noisy Graph Signals}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  url = {https://openreview.net/forum?id=Nsr_hHZygQa},
}

Loading related content...

Figure