类卷积表达式高效计算：如何以O(m·2^m)复杂度求解ν(z₁,…,zₘ)？

问题背景 #

已知$x_i, z_i \in {0,1}$（$i=1\ldots m$），需高效计算所有$z_1\ldots z_m$对应的表达式：
$$\nu(z₁,…,zₘ)=\sum_{x₁,…xₘ} \prod_{i=1}^m p(z_i|x_i)μ(x₁,…,xₘ)$$
其中$p(z|x)$是与$i$无关的概率分布：
$$p(z|x)=\begin{cases}1-q, & (z,x)=(0,0) \ q, & (z,x)=(1,0) \ 1/2, & (z,x)=(0,1) \ 1/2, & (z,x)=(1,1)\end{cases}$$
希望找到复杂度为$O(m·2^m)$的算法（类似FFT卷积的效率，此前尝试FFT卷积类方法未成功）。

高效解法：基于快速沃尔什-哈达玛变换（FWHT） #

可以利用FWHT实现$O(m·2^m)$复杂度的计算，核心思路是将问题转化为沃尔什基下的对角变换，具体步骤如下：

• 步骤1：对$\mu$做FWHT
  将$\mu$视为长度为$2^m$的数组（索引对应$x_1\ldots x_m$的二进制表示），执行FWHT得到$\hat{\mu}$，复杂度$O(m·2^m)$。FWHT的核心是通过分治实现快速变换，与FFT的分治逻辑类似。
• 步骤2：逐系数加权
  对每个FWHT后的索引$s$（二进制表示为$s_1\ldots s_m$），计算：
  $$\hat{\nu}(s) = \hat{\mu}(s) · \left( \frac{1-2q}{2} \right)^{|s|}$$
  其中$|s|$是$s$中1的个数（即每个$s_i=1$时乘一次$\lambda_1$，$s_i=0$时乘$\lambda_0=1$）。这一步是逐元素操作，复杂度$O(2^m)$。
• 步骤3：逆FWHT得到结果
  对$\hat{\nu}$执行逆FWHT，得到最终的$\nu(z_1\ldots z_m)$数组，复杂度$O(m·2^m)$。

复杂度验证 #

整个流程的总复杂度为$O(m·2^m)$，与FFT卷积的复杂度完全一致，满足需求。

内容的提问来源于stack exchange，提问作者tiX5eeMo