Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing
This paper reports a field-programmable gate array (FPGA) design of compressed sensing (CS) using the orthogonal matching pursuit (OMP) algorithm. While solving the least-squares (LS) problem in the OMP algorithm, the complexity of the matrix inversion operation at every loop is reduced by the propo...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-09-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2079-9292/7/9/206 |
| _version_ | 1798041329463197696 |
|---|---|
| author | Seonggeon Kim Uihyun Yun Jaehyuk Jang Geunsu Seo Jongjin Kang Heung-No Lee Minjae Lee |
| author_facet | Seonggeon Kim Uihyun Yun Jaehyuk Jang Geunsu Seo Jongjin Kang Heung-No Lee Minjae Lee |
| author_sort | Seonggeon Kim |
| collection | DOAJ |
| description | This paper reports a field-programmable gate array (FPGA) design of compressed sensing (CS) using the orthogonal matching pursuit (OMP) algorithm. While solving the least-squares (LS) problem in the OMP algorithm, the complexity of the matrix inversion operation at every loop is reduced by the proposed partitioned inversion that utilizes the inversion result in the previous iteration. By the proposed matrix (n × n) inversion method inside the OMP, the number of operations is reduced down from O(n3) to O(n2). The OMP algorithm is implemented with a Xilinx Kintex UltraScale. The architecture with the proposed partitioned inversion involves 722 less DSP48E compared with the conventional method. It operates with a sample period of 4 ns, signal reconstruction time of 27 μs, and peak signal to noise ratio (PSNR) of 30.26 dB. |
| first_indexed | 2024-04-11T22:20:03Z |
| format | Article |
| id | doaj.art-55ed07f9fef64be6892dc9af62dccdc8 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-04-11T22:20:03Z |
| publishDate | 2018-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-55ed07f9fef64be6892dc9af62dccdc82022-12-22T04:00:10ZengMDPI AGElectronics2079-92922018-09-017920610.3390/electronics7090206electronics7090206Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive SensingSeonggeon Kim0Uihyun Yun1Jaehyuk Jang2Geunsu Seo3Jongjin Kang4Heung-No Lee5Minjae Lee6The School of Electrical and Computer Science, Gwangju Institute of Science and Technology, Gwangju 61005, KoreaThe School of Electrical and Computer Science, Gwangju Institute of Science and Technology, Gwangju 61005, KoreaThe School of Electrical and Computer Science, Gwangju Institute of Science and Technology, Gwangju 61005, KoreaThe LG Innotek, Ansan 426791, KoreaThe Hanwha System, Seongnam 13524, KoreaThe School of Electrical and Computer Science, Gwangju Institute of Science and Technology, Gwangju 61005, KoreaThe School of Electrical and Computer Science, Gwangju Institute of Science and Technology, Gwangju 61005, KoreaThis paper reports a field-programmable gate array (FPGA) design of compressed sensing (CS) using the orthogonal matching pursuit (OMP) algorithm. While solving the least-squares (LS) problem in the OMP algorithm, the complexity of the matrix inversion operation at every loop is reduced by the proposed partitioned inversion that utilizes the inversion result in the previous iteration. By the proposed matrix (n × n) inversion method inside the OMP, the number of operations is reduced down from O(n3) to O(n2). The OMP algorithm is implemented with a Xilinx Kintex UltraScale. The architecture with the proposed partitioned inversion involves 722 less DSP48E compared with the conventional method. It operates with a sample period of 4 ns, signal reconstruction time of 27 μs, and peak signal to noise ratio (PSNR) of 30.26 dB.http://www.mdpi.com/2079-9292/7/9/206compressed sensing (CS)field programmable gate array (FPGA)high-level synthesis (HLS)partitioned inversionorthogonal matching pursuit (OMP) |
| spellingShingle | Seonggeon Kim Uihyun Yun Jaehyuk Jang Geunsu Seo Jongjin Kang Heung-No Lee Minjae Lee Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing Electronics compressed sensing (CS) field programmable gate array (FPGA) high-level synthesis (HLS) partitioned inversion orthogonal matching pursuit (OMP) |
| title | Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing |
| title_full | Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing |
| title_fullStr | Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing |
| title_full_unstemmed | Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing |
| title_short | Reduced Computational Complexity Orthogonal Matching Pursuit Using a Novel Partitioned Inversion Technique for Compressive Sensing |
| title_sort | reduced computational complexity orthogonal matching pursuit using a novel partitioned inversion technique for compressive sensing |
| topic | compressed sensing (CS) field programmable gate array (FPGA) high-level synthesis (HLS) partitioned inversion orthogonal matching pursuit (OMP) |
| url | http://www.mdpi.com/2079-9292/7/9/206 |
| work_keys_str_mv | AT seonggeonkim reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT uihyunyun reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT jaehyukjang reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT geunsuseo reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT jongjinkang reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT heungnolee reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing AT minjaelee reducedcomputationalcomplexityorthogonalmatchingpursuitusinganovelpartitionedinversiontechniqueforcompressivesensing |