Confined Orthogonal Matching Pursuit for Sparse Random Combinatorial Matrices
IEEE Transactions on Signal Processing · 2025 · 73 · 4077-4091
DOI: 10.1109/tsp.2025.3615973 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Signal Processing, 2025. Verfasst von Xinwei Zhao und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 39 Literaturangaben. Gefördert von: National Key R&D Program of China, National Natural Science Foundation of China, Guangdong Provincial Key Laboratory of Information Security Technology.
Abstract (Originalsprache)
Orthogonal matching pursuit (OMP) is a commonly used greedy algorithm for recovering sparse signals from compressed measurements. In this paper, we introduce a variant of the OMP algorithm to reduce the complexity of reconstructing a class of $K$ -sparse signals $\boldsymbol{x}\in\mathbb{R}^{n}$ from measurements $\boldsymbol{y}=\boldsymbol{A}\boldsymbol{x}$ . In particular, $\boldsymbol{A}\in\{0,1\}^{m\times n}$ is a sparse random combinatorial matrix with independent columns, where each column is chosen uniformly among the vectors with exactly $d \, (d\leq m/2)$ ones. The proposed algorithm, referred to as the confined OMP algorithm, leverages the properties of the sparse signal $\boldsymbol{x}$ and the measurement matrix $\boldsymbol{A}$ to reduce redundancy in $\boldsymbol{A}$ , thereby requiring fewer column indices to be identified. To this end, we first define a confined set $\Gamma$ (see Definition 1 in Sec. II-A ) with $|\Gamma|\leq n$ and then prove that the support of $\boldsymbol{x}$ is a subset of $\Gamma$ with probability 1 if the distributions of nonzero components of $\boldsymbol{x}$ satisfy a certain condition. During the process of the confined OMP algorithm, the possibly chosen column indices are strictly confined to the confined set $\Gamma$ . We further develop the lower bound on the probability of exact recovery of $\boldsymbol{x}$ using the confined OMP algorithm. The derived bound shows that, if the spark of $\boldsymbol{A}$ is greater than $K$ , then $m = 2\mathrm{e}K\ln(n-K)$ measurements are sufficient to ensure the probability of recovering a $K$ -sparse signal with the proposed algorithm is at least $1-\frac{1}{n-K}$ , where $\mathrm{e}$ represents Euler’s number. Furthermore, the obtained theoretical results can be used to optimize the column degree $d$ of $\boldsymbol{A}$ . Finally, experimental results show that the confined OMP algorithm is more efficient in reconstructing a class of sparse signals compared to the OMP algorithm.
Förderung
- National Key R&D Program of China
- National Natural Science Foundation of China
- Guangdong Provincial Key Laboratory of Information Security Technology
Zitieren
APA
Zhao, X., Wen, J., Yang, H., & Ma, X. (2025). Confined Orthogonal Matching Pursuit for Sparse Random Combinatorial Matrices. IEEE Transactions on Signal Processing, 73, 4077-4091. https://doi.org/10.1109/tsp.2025.3615973
Vancouver
Zhao X, Wen J, Yang H, Ma X. Confined Orthogonal Matching Pursuit for Sparse Random Combinatorial Matrices. IEEE Transactions on Signal Processing. 2025;73:4077-4091. doi:10.1109/tsp.2025.3615973
BibTeX
@article{Zhao2025,
author = {Zhao, Xinwei and Wen, Jinming and Yang, Hongqi and Ma, Xiao},
title = {Confined Orthogonal Matching Pursuit for Sparse Random Combinatorial Matrices},
journal = {IEEE Transactions on Signal Processing},
year = {2025},
volume = {73},
pages = {4077--4091},
doi = {10.1109/tsp.2025.3615973}
}
EUVIMED