TY - GEN
T1 - Greedy algorithm with approximation ratio for sampling noisy graph signals
AU - Wu, Changlong
AU - Chen, Wenxin
AU - Zhang, June
N1 - Publisher Copyright: © 2018 IEEE.
PY - 2018/9/10
Y1 - 2018/9/10
N2 - 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.
AB - 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.
KW - Approximation Ratio
KW - Graph Signal Processing
KW - Graph Signal Sampling
KW - Greedy Algorithm
KW - Noisy Graph Signal
UR - https://www.scopus.com/pages/publications/85054264011
UR - https://www.scopus.com/pages/publications/85054264011#tab=citedBy
U2 - 10.1109/ICASSP.2018.8462626
DO - 10.1109/ICASSP.2018.8462626
M3 - Conference contribution
SN - 9781538646588
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 4654
EP - 4658
BT - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2018
Y2 - 15 April 2018 through 20 April 2018
ER -