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

来源：信息与控制杂志2016年第6期北京时间：

作者：秦书嘉, 缪磊, 崔龙, 席宁

摘要：快速Hadamard变换被广泛应用于信号与图像处理、通信系统、数字逻辑等领域中．当问题规模非常大时，快速Hadamard变换有可能不能满足计算时间的要求；这种情况下，算法并行化是一种行之有效的手段．本文以单像素相机的压缩感知图像复原为应用背景，利用基二快速Hadamard变换与快速傅里叶变换的结构相似性，提出一种通用的基二快速Hadamard变换的任务级并行算法，并用构造方式证明了该并行算法与串行算法计算结果之间的等价性．仿真表明对于小于220向量长度的问题规模以及并行子任务数少于210的情况，该并行算法对比串行算法的数值计算结果的欧氏距离平方误差小于10-18，佐证了并行算法的正确性．在PC平台通过多核CPU上POSIX线程实现的实验表明：在该特定平台和特定配置上对于220至225向量长度的问题规模并行计算加速比为1.33~1.42，证明了文中提出方法的可行性和有效性.

关键词：单像素相机, 压缩感知, Hadamard变换, 并行算法