Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition

WANG Xi; LIANG Wen-kai; YANG Hong; ZHANG Hong-sheng; LIU Ting; MOU Xiao-shuang; ZHANG Lei; YU Bai-shan; LI Miao

doi:10.12263/DZXB.20220554

您当前的位置：

首页 >

文章列表页 >

Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition

PAPERS | 更新时间：2025-12-11

- Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition
- ACTA ELECTRONICA SINICA Vol. 52, Issue 5, Pages: 1534-1542(2024)
- 作者机构：
  
  重庆邮电大学光电工程学院，重庆 400065
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(61604028);Special Key Project of Chongqing Technology Innovation and Application Development(cstc2020jscx-gksbX0012);Key Projects of Basic Research and Preface Exploration in Chongqing(cstc2021ycjh-bgzxm0085)
- DOI：10.12263/DZXB.20220554
  CLC： TN911.7;
- Received：14 May 2022，
  
  Revised：2023-12-28，
  
  Published：25 May 2024
- 稿件说明：
移动端阅览
王玺,梁文凯,杨虹,等.权重化QR分解的正交匹配追踪算法硬件实现[J].电子学报,2024,52(05):1534-1542.

WANG Xi, LIANG Wen-kai, YANG Hong, et al.Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition[J].Acta Electronica Sinica, 2024, 52(05): 1534-1542.
王玺,梁文凯,杨虹,等.权重化QR分解的正交匹配追踪算法硬件实现[J].电子学报,2024,52(05):1534-1542. DOI：10.12263/DZXB.20220554

WANG Xi, LIANG Wen-kai, YANG Hong, et al.Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition[J].Acta Electronica Sinica, 2024, 52(05): 1534-1542. DOI：10.12263/DZXB.20220554

摘要

为在小型化、低成本的硬件平台实现正交匹配追踪（Orthogonal Matching Pursuit，OMP）算法，针对OMP算法中最小二乘法的问题，该文构造一个确定性的传感矩阵，提出一种低复杂度、低资源的权重化QR分解的OMP（Weighted QR decomposition OMP，WQR-OMP）算法硬件结构，在ZYNQ 7020型号芯片上搭建WQR-OMP SOC系统.WQR-OMP算法在传感矩阵进行QR分解后，根据三角矩阵

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949658&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949673&type=

2.20133328

中元素的分布特性，通过权重化运算只保留主对角线上的元素而其他余元素归零，得到对角矩阵

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949664&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949678&type=

2.45533323

，然后近似计算稀疏向量的解.实验结果表明：与基于QR分解的OMP（QR decomposition OMP，QR-OMP）和Batch-OMP算法的硬件结构相比，WQR-OMP算法硬件结构的重构速度更快、存储资源更少.在压缩率为0.25的条件下，WQR-OMP SOC系统对256×256分辨率图像的重构时间为400 ms左右，其速率比仅使用ARM处理器的重构速率提高了约6.3倍.与其他现有研究对比，该系统在Block RAM存储资源消耗较少的情况下，进一步提升了重构速度，适用于存储资源受限的硬件平台.

Abstract

To realize the orthogonal matching pursuit (OMP) algorithm on a miniaturized and low-cost hardware platform

for calculation of the least square method in the OMP algorithm

this paper constructs a deterministic perception matrix and proposes a low-complexity

low-resource weighted QR decomposition OMP (WQR-OMP) algorithm hardware architecture

and the WQR-OMP SOC system is built on the ZYNQ 7020 chip. The WQR-OMP algorithm is that after the QR decomposition of the sensing matrix according to the distribution characteristics of the elements in the triangular matrix

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949684&type=

2.53999996

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949685&type=

2.45533323

the elements on the main diagonal are retained through the weighting operation

which returns other elements to zero to obtain the diagonal matrix

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949699&type=

2.53999996

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=61949689&type=

2.70933342

and then approximately computes the solution for the sparse vector. The experimental results show that compared with the hardware architecture of OMP algorithm based on QR decomposition OMP (QR-OMP) and Batch-OMP algorithm

the WQR-OMP algorit

hm has lower computational complexity and fewer storage resources. The reconstruction time of the WQR-OMP SOC system is about 400 ms for 256×256 resolution images at a compression rate of 0.25

which is 6.3 times faster than the ARM processor does. Compared with other existing researchers

this system further improves the reconstruction speed with less consumption of Block RAM storage resources and is suitable for hardware platforms with limited storage resources.

关键词

Keywords

references

DONOHO D L . Compressed sensing [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 4 ): 1289 - 1306 .

CANDES E J , TAO T . Near-optimal signal recovery from random projections: Universal encoding strategies? [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 12 ): 5406 - 5425 .

左婷 , 王法松 , 张建康 , 等 . 室内可见光通信系统中基于压缩感知的空移键控信号检测方法 [J ] . 电子学报 , 2022 , 50 ( 1 ): 36 - 44 .

ZUO T , WANG F S , ZHANG J K , et al . Space shift keying signal detection approach based on compressed sensing in indoor VLC system [J ] . Acta Electronica Sinica , 2022 , 50 ( 1 ): 36 - 44 . (in Chinese)

LUSTIG M , DONOHO D L , SANTOS J M , et al . Compressed sensing MRI [J ] . IEEE Signal Processing Magazine , 2008 , 25 ( 2 ): 72 - 82 .

肖许意 , 陈刘雅 , 张学智 , 等 . 单像素成像及其概率统计分析综述 [J ] . 激光与光电子学进展 , 2021 , 58 ( 10 ): 1011018 .

XIAO X Y , CHEN L Y , ZHANG X Z , et al . Review on single-pixel imaging and its probability statistical analysis [J ] . Laser & Optoelectronics Progress , 2021 , 58 ( 10 ): 1011018 . (in Chinese)

CRESPO MARQUES E , MACIEL N , NAVINER L , et al . A review of sparse recovery algorithms [J ] . IEEE Access , 2018 , 7 : 1300 - 1322 .

POLAT Ö , KAYHAN S K . High-speed FPGA implementation of orthogonal matching pursuit for compressive sensing signal reconstruction [J ] . Computers & Electrical Engineering , 2018 , 71 : 173 - 190 .

RABAH H , AMIRA A , MOHANTY B K , et al . FPGA implementation of orthogonal matching pursuit for compressive sensing reconstruction [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2015 , 23 ( 10 ): 2209 - 2220 .

GE X , YANG F , ZHU H L , et al . An efficient FPGA implementation of orthogonal matching pursuit with square-root-free QR decomposition [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2019 , 27 ( 3 ): 611 - 623 .

LI J , CHOW P , PENG Y X , et al . FPGA implementation of an improved OMP for compressive sensing reconstruction [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2021 , 29 ( 2 ): 259 - 272 .

RUBINSTEIN R , ZIBULEVSKY M , ELAD M . Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit [EB/OL ] . ( 2008 )[2022 ] . http://cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2008/CS/CS-2008-08.revised.pdf http://cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2008/CS/CS-2008-08.revised.pdf .

ZHANG F , PIAO Y . Design of restoration method based on compressed sensing and TwIST algorithm [J ] . Journal of Physics: Conference Series , 2018 , 1004 : 012006 .

BARANIUK R G . Compressive sensing[lecture notes] [J ] . IEEE Signal Processing Magazine , 2007 , 24 ( 4 ): 118 - 121 .

LI L X , FANG Y , LIU L W , et al . Overview of compressed sensing: Sensing model, reconstruction algorithm, and its applications [J ] . Applied Sciences , 2020 , 10 ( 17 ): 5909 .

CANDES E J , ROMBERG J , TAO T . Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 2 ): 489 - 509 .

DONOHO D L , ELAD M . Optimally sparse representation in general (nonorthogonal) dictionaries via l minimization [J ] . Proceedings of the National Academy of Sciences of the United States of America , 2003 , 100 ( 5 ): 2197 - 2202 .

TROPP J A , GILBERT A C . Signal recovery from random measurements via orthogonal matching pursuit [J ] . IEEE Transactions on Information Theory , 2007 , 53 ( 12 ): 4655 - 4666 .

李佳 , 王强 , 沈毅 , 等 . 压缩感知中测量矩阵与重建算法的协同构造 [J ] . 电子学报 , 2013 , 41 ( 1 ): 29 - 34 .

LI J , WANG Q , SHEN Y , et al . Collaborative construction of measurement matrix and reconstruction algorithm in compressive sensing [J ] . Acta Electronica Sinica , 2013 , 41 ( 1 ): 29 - 34 . (in Chinese)

YU Z L , SU J C , YANG F , et al . Fast compressive sensing reconstruction algorithm on FPGA using Orthogonal Matching Pursuit [C ] // 2016 IEEE International Symposium on Circuits and Systems (ISCAS) . Piscataway : IEEE , 2016 : 249 - 252 .

李明飞 , 阎璐 , 杨然 , 等 . 基于Hadamard矩阵优化排序的快速单像素成像 [J ] . 物理学报 , 2019 , 68 ( 6 ): 87 - 94 .

LI M F , YAN L , YANG R , et al . Fast single-pixel imaging based on optimized reordering Hadamard basis [J ] . Acta Physica Sinica , 2019 , 68 ( 6 ): 87 - 94 . (in Chinese)

GHARAVI-ALKHANSARI M , HUANG T S . A fast orthogonal matching pursuit algorithm [C ] // Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP’98 (Cat. No.98CH36181) . Piscataway : IEEE , 2002 : 1389 - 1392 .

ROY S , ACHARYA D P , SAHOO A K . Low-complexity architecture of orthogonal matching pursuit based on QR decomposition [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2019 , 27 ( 7 ): 1623 - 1632 .

FARDAD M , SAYEDI S M , YAZDIAN E . A low-complexity hardware for deterministic compressive sensing reconstruction [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2018 , 65 ( 10 ): 3349 - 3361 .

KOPPARTHI V R , PEESAPATI R , SABAT S L . System on chip implementation of low complex orthogonal matching pursuit algorithm on FPGA [C ] // 2020 6th International Conference on Signal Processing and Communication (ICSC) . Piscataway : IEEE , 2020 : 178 - 184 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Multi‑Fractal Detrended Fluctuation Analysis Method for Non‑Stationary Time Series Based on EMD‑LS

Multiscale Image Information from Multisensor Fusion Algorithm

A Low-Complexity QR Factorization Based Iterative Receiver for MIMO Systems

Improvement on Least Squares Twin Support Vector Machine for Pattern Classification

Related Author

Xiao-shuang Mou

LUO Yuan-xing

HU Feng-cheng

LI Chao

LIANG Xing

LI Zhi-hong

GAO Jing-li

WEN Cheng-lin

Related Institution

School of Mechanical and Electrical Engineering, Nanchang Institute of Technology

Jiangxi Province Key Laboratory of Precision Drive and Control, Institute of Technology

Institute of Information and Automation,Hangzhou Dianzi University

School of Computer and Information Engineering, Henan University

Institute of Information and AutomationHangzhou Dianzi UniversityHangzhouZhejiang 310018China

⁰