Randomized Orthogonal Matching Pursuit Algorithm with Adaptive Partial Selection for Sparse Signal Recovery
SIAM Journal on Imaging Sciences · 30.06.2025 · 18 (2) · 1028-1057
DOI: 10.1137/24m1648624 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Imaging Sciences, online erschienen am 25.04.2025. Verfasst von Jinming Wen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
The orthogonal matching pursuit (OMP) algorithm, known for its exceptional ability to reconstruct sparse signals, is a widely employed algorithm in compressed sensing. Numerous studies have provided theoretical analyses supporting its capability for achieving exact recovery. However, when applied to large-scale sparse signal recovery, the OMP algorithm incurs substantial computational overhead, leading to prolonged running time. To address this challenge, we design a Randomized OMP with Adaptive Partial Selection (AROMP) algorithm to mitigate computational overhead and reduce runtime. The novelty of the AROMP algorithm lies in its utilization of a randomized index selection method rather than a greedy approach to select the index in each iteration. Subsequently, we theoretically characterize the gap between AROMP and OMP for exactly recovering an [Formula: see text]-sparse signal and show that the gap decreases as the number of comparisons [Formula: see text] increases, sparsity [Formula: see text] decreases, or signal dimension [Formula: see text] decreases. As [Formula: see text] approaches [Formula: see text], the gap between AROMP and OMP tends to 0. The experimental results substantiate that our proposed method significantly reduces running time while maintaining satisfactory accuracy in sparse signal recovery, face recognition tasks, and image reconstruction tasks.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Wen, J., Li, C., Shu, Q., & Zhou, Z. (2025). Randomized Orthogonal Matching Pursuit Algorithm with Adaptive Partial Selection for Sparse Signal Recovery. SIAM Journal on Imaging Sciences, 18(2), 1028-1057. https://doi.org/10.1137/24m1648624
Vancouver
Wen J, Li C, Shu Q, Zhou Z. Randomized Orthogonal Matching Pursuit Algorithm with Adaptive Partial Selection for Sparse Signal Recovery. SIAM Journal on Imaging Sciences. 2025;18(2):1028-1057. doi:10.1137/24m1648624
BibTeX
@article{Wen2025,
author = {Wen, Jinming and Li, Changhao and Shu, Qianyu and Zhou, Zhengchun},
title = {Randomized Orthogonal Matching Pursuit Algorithm with Adaptive Partial Selection for Sparse Signal Recovery},
journal = {SIAM Journal on Imaging Sciences},
year = {2025},
volume = {18},
number = {2},
pages = {1028--1057},
doi = {10.1137/24m1648624}
}
EUVIMED