Efficient Implementations for Orthogonal Matching Pursuit
Based on the efficient inverse Cholesky factorization, we propose an implementation of OMP (called as version 0, i.e., v0) and its four memory-saving versions (i.e., the proposed v1, v2, v3 and v4). In the simulations, the proposed five versions and the existing OMP implementations have nearly the s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/9/9/1507 |
| _version_ | 1797553708691619840 |
|---|---|
| author | Hufei Zhu Wen Chen Yanpeng Wu |
| author_facet | Hufei Zhu Wen Chen Yanpeng Wu |
| author_sort | Hufei Zhu |
| collection | DOAJ |
| description | Based on the efficient inverse Cholesky factorization, we propose an implementation of OMP (called as version 0, i.e., v0) and its four memory-saving versions (i.e., the proposed v1, v2, v3 and v4). In the simulations, the proposed five versions and the existing OMP implementations have nearly the same numerical errors. Among all the OMP implementations, the proposed v0 needs the least computational complexity, and is the fastest in the simulations for almost all problem sizes. As a tradeoff between computational complexities/time and memory requirements, the proposed v1 seems to be better than all the existing ones when only considering the efficient OMP implementations storing <inline-formula><math display="inline"><semantics><mi mathvariant="bold">G</mi></semantics></math></inline-formula> (i.e., the Gram matrix of the dictionary), the proposed v2 and v3 seem to be better than the only existing one when only considering the efficient implementations not storing <inline-formula><math display="inline"><semantics><mi mathvariant="bold">G</mi></semantics></math></inline-formula>, and the proposed v4 seems to be better than the naive implementation that has the (known) minimum memory requirements. Moreover, all the proposed five versions only include parallelizable matrix-vector products in each iteration, and do not need any back-substitutions that are necessary in some existing efficient implementations (e.g., those utilizing the Cholesky factorization). |
| first_indexed | 2024-03-10T16:20:26Z |
| format | Article |
| id | doaj.art-3a1fe9bac48245968f3687eb13924f28 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T16:20:26Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-3a1fe9bac48245968f3687eb13924f282023-11-20T13:39:58ZengMDPI AGElectronics2079-92922020-09-0199150710.3390/electronics9091507Efficient Implementations for Orthogonal Matching PursuitHufei Zhu0Wen Chen1Yanpeng Wu2Department of Information Science and Engineering, Hunan First Normal University, Changsha 410205, ChinaDepartment of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240, ChinaDepartment of Information Science and Engineering, Hunan First Normal University, Changsha 410205, ChinaBased on the efficient inverse Cholesky factorization, we propose an implementation of OMP (called as version 0, i.e., v0) and its four memory-saving versions (i.e., the proposed v1, v2, v3 and v4). In the simulations, the proposed five versions and the existing OMP implementations have nearly the same numerical errors. Among all the OMP implementations, the proposed v0 needs the least computational complexity, and is the fastest in the simulations for almost all problem sizes. As a tradeoff between computational complexities/time and memory requirements, the proposed v1 seems to be better than all the existing ones when only considering the efficient OMP implementations storing <inline-formula><math display="inline"><semantics><mi mathvariant="bold">G</mi></semantics></math></inline-formula> (i.e., the Gram matrix of the dictionary), the proposed v2 and v3 seem to be better than the only existing one when only considering the efficient implementations not storing <inline-formula><math display="inline"><semantics><mi mathvariant="bold">G</mi></semantics></math></inline-formula>, and the proposed v4 seems to be better than the naive implementation that has the (known) minimum memory requirements. Moreover, all the proposed five versions only include parallelizable matrix-vector products in each iteration, and do not need any back-substitutions that are necessary in some existing efficient implementations (e.g., those utilizing the Cholesky factorization).https://www.mdpi.com/2079-9292/9/9/1507inverse cholesky factorizationorthogonal matching pursuit (OMP)efficient implementation |
| spellingShingle | Hufei Zhu Wen Chen Yanpeng Wu Efficient Implementations for Orthogonal Matching Pursuit Electronics inverse cholesky factorization orthogonal matching pursuit (OMP) efficient implementation |
| title | Efficient Implementations for Orthogonal Matching Pursuit |
| title_full | Efficient Implementations for Orthogonal Matching Pursuit |
| title_fullStr | Efficient Implementations for Orthogonal Matching Pursuit |
| title_full_unstemmed | Efficient Implementations for Orthogonal Matching Pursuit |
| title_short | Efficient Implementations for Orthogonal Matching Pursuit |
| title_sort | efficient implementations for orthogonal matching pursuit |
| topic | inverse cholesky factorization orthogonal matching pursuit (OMP) efficient implementation |
| url | https://www.mdpi.com/2079-9292/9/9/1507 |
| work_keys_str_mv | AT hufeizhu efficientimplementationsfororthogonalmatchingpursuit AT wenchen efficientimplementationsfororthogonalmatchingpursuit AT yanpengwu efficientimplementationsfororthogonalmatchingpursuit |