权重化QR分解的正交匹配追踪算法硬件实现

王玺; 梁文凯; 杨虹; 张红升; 刘挺; 牟晓霜; 张磊; 余柏汕; 黎淼

doi:10.12263/DZXB.20220554

您当前的位置：

首页 >

文章列表页 >

权重化QR分解的正交匹配追踪算法硬件实现

学术论文 | 更新时间：2025-12-11

- 权重化QR分解的正交匹配追踪算法硬件实现
- Hardware Implementation of Orthogonal Matching Pursuit Algorithm for Weighted QR Decomposition
- 电子学报 2024年52卷第5期页码：1534-1542
- 作者机构：
  
  重庆邮电大学光电工程学院，重庆 400065
- 作者简介：
  
  [ "王玺男，1983年出生，重庆人.2013年6月于重庆大学获得工学博士学位.2013年3月至2018年8月就职于中国电子科技集团第四十四研究所，任高级工程师.2018年9月至今就职于重庆邮电大学，任硕士生导师.主要研究方向为稀疏优化方法及其硬件加速计算. E-mail: xiwang@cqupt.edu.cn" ]
  [ "梁文凯男，1997年出生，河南周口人.重庆邮电大学电子科学与技术专业硕士研究生.主要研究方向为压缩感知算法的研究及硬件实现. E-mail: 1429205353@qq.com" ]
  [ "黎淼男，1982年出生，重庆人.工学博士.副教授，硕士生导师.主要研究方向为X射线及Gamma射线超快诊断技术. E-mail: limiao@cqupt.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(61604028);重庆市技术创新与应用发展专项重点项目(cstc2020jscx-gksbX0012);重庆市基础研究与前言探索重点项目(cstc2021ycjh-bgzxm0085)
- DOI：10.12263/DZXB.20220554
  中图分类号： TN911.7;
- 收稿：2022-05-14，
  
  修回：2023-12-28，
  
  纸质出版：2024-05-25
- 稿件说明：
移动端阅览
王玺,梁文凯,杨虹,等.权重化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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于EMD‑LS的非平稳时间序列多重分形去趋势波动分析方法

多传感器多尺度图像信息融合算法

新型基于QR分解的低复杂度MIMO迭代接收机

一种改进的最小二乘孪生支持向量机分类算法