刘仲、李立春、李慧启（信息工程大学信息系统工程学院）于2018年2月在《计算机工程》（Computer Engineering）第44卷第2期发表了一项原创研究，题为《一种稀疏度自适应的稀疏傅里叶变换算法》（A Sparsity Adaptive Sparse Fourier Transform Algorithm）。该研究针对信号处理领域中稀疏傅里叶变换（Sparse Fast Fourier Transform, SFFT）算法依赖先验稀疏度信息的问题，提出了一种稀疏度自适应的改进算法（SASFFT），显著提升了算法在未知稀疏度场景下的适用性。

学术背景

稀疏傅里叶变换（SFFT）是离散傅里叶变换（DFT）的优化算法，其通过频域稀疏性将计算复杂度从O(n log n)降至亚线性级别，广泛应用于图像处理、宽带频谱感知等领域。然而，传统SFFT需预先知道信号的频域稀疏度k，而实际应用中k常未知，导致算法受限。现有研究虽在降维、并行化等方面取得进展（如文献[12-16]），但稀疏度自适应问题尚未解决。本研究旨在通过动态估计稀疏度，突破这一瓶颈。

研究流程与方法

1. 算法设计框架

SASFFT包含三个核心步骤：
- 稀疏度估计：通过下采样域能量检测初始化稀疏度k̂，并迭代调整。每次迭代中，增大下采样维度b以降低频谱碰撞概率（推论1证明碰撞概率≤4k/(n√k̂)），同时利用窗函数卷积特性（推论2）过滤虚警频点，最终得到略大于真实k的估计值k̂m。
- 稀疏傅里叶变换：将k̂m作为参数输入改进的SFFT-1算法，通过时域降维（频谱重排、滤波、下采样）和频域重构（渐近法或统计法）获取k̂m个频点。
- 有效分量筛选：设定阈值β剔除能量低于β的虚警频点，保留真实k个频域信息。

2. 关键技术

• 窗函数设计：采用文献[11]的平滑窗函数，其通带（1±δ）和阻带（<δ）特性可平衡频谱泄漏与虚警率。
  
• 复杂度控制：单次迭代复杂度为O(b log(n/δ))，总复杂度为O(√(nk) log(n) log(n/δ))，与SFFT-1相当（式4）。
  

3. 实验验证

• 对象与参数：测试信号为n维矢量（n=2^17~2^24），频域随机生成k个非零分量（k=50~1000），幅度为1，相位随机。
  
• 对比算法：FFTW（传统FFT）、SFFT-1（已知稀疏度）。
  
• 平台：Ubuntu 16.04，Intel i5-4210M CPU，8GB内存。
  

主要结果

1. 信号长度影响（k=50固定）：当n>2^19时，SASFFT运行时间显著低于FFTW（图3），且与SFFT-1的时间差稳定。例如，n=2^22时，SASFFT耗时仅为FFTW的60%。
   
2. 稀疏度影响（n=2^22固定）：k<900时，SASFFT始终快于FFTW（图4）；k=900时两者耗时相当。稀疏度估计迭代次数稳定为2次，验证了算法鲁棒性。
   
3. 误差分析：所有测试中，每符号平均L1误差（式5）<10^-6（图5），表明算法精度满足实际需求。
   

结论与价值

SASFFT首次实现了未知稀疏度条件下的高效稀疏傅里叶变换，其科学价值体现在：
1. 理论创新：通过动态稀疏度估计与阈值筛选，解决了先验信息依赖问题，扩展了SFFT应用场景。
2. 工程意义：在n>2^19或k<900时，算法速度优于FFTW，适用于大规模稀疏信号处理（如卫星通信[7]、OFDM频偏估计）。
3. 方法论贡献：提出的窗函数卷积分析与频谱碰撞概率模型（推论1-2）为后续研究提供了理论基础。

研究亮点

• 创新性：首次将稀疏度自适应机制引入SFFT，填补了领域空白。
  
• 实用性：算法复杂度与SFFT-1相当，且无需额外硬件支持。
  
• 鲁棒性：通过迭代估计与阈值筛选，在保证精度的同时降低虚警率。
  

其他价值

实验部分验证了算法在极端参数（如k=1000）下的稳定性，为高稀疏度信号处理提供了参考。此外，文中对频谱碰撞和窗函数卷积的数学分析（定理1、推论2）可推广至其他稀疏变换算法研究。