一种基二快速Hadamard变换的并行算法

发布时间：2017-09-17 14:46

  本文关键词：一种基二快速Hadamard变换的并行算法

  更多相关文章： 单像素相机 压缩感知 Hadamard变换 并行算法

【摘要】：快速Hadamard变换被广泛应用于信号与图像处理、通信系统、数字逻辑等领域中.当问题规模非常大时,快速Hadamard变换有可能不能满足计算时间的要求;这种情况下,算法并行化是一种行之有效的手段.本文以单像素相机的压缩感知图像复原为应用背景,利用基二快速Hadamard变换与快速傅里叶变换的结构相似性,提出一种通用的基二快速Hadamard变换的任务级并行算法,并用构造方式证明了该并行算法与串行算法计算结果之间的等价性.仿真表明对于小于2~(20)向量长度的问题规模以及并行子任务数少于2~(10)的情况,该并行算法对比串行算法的数值计算结果的欧氏距离平方误差小于10~(-18),佐证了并行算法的正确性.在PC平台通过多核CPU上POSIX线程实现的实验表明:在该特定平台和特定配置上对于220至225向量长度的问题规模并行计算加速比为1.33~1.42,证明了文中提出方法的可行性和有效性.
【作者单位】： 中国科学院沈阳自动化研究所;中国科学院大学;密歇根州立大学;
【关键词】： 单像素相机 压缩感知 Hadamard变换 并行算法
【基金】：国家自然科学基金资助项目(61102014) 国际热核聚变实验堆(ITER)计划资助项目(2012GB102005)
【分类号】：TP391.41
【正文快照】： 1引言 Hadamard矩阵(在基二快速Hadamard变换的语境下这里具体指Hadamard定序的Walsh-Hadamard矩阵或称Sylvester矩阵,下文简称为H阵)是一种结构特殊的矩阵, 可以通过如下方法迭代构造: H0=[1] (1)(2) 1i，

本文编号：870058