广义Walsh-Hadamard变换的快速算法

本文证明了广义Walsh-Hadamard变换矩阵的因子分解定理: X(n)=X_(n-1)X_(n-2)…X_1X。 其中每个X_k,都是每行只含p个非零元素的p~n×P~n阶稀疏矩阵。根据这个定理,得到了广义Walsh-Hadamard变换的快速算法,它将原来需要p~n×P~n次运算缩减为np~n次运算。在信号处理中常用的Walsh-Hadamard变换的快速算法是本文结果的最简单的情形(P=2)。