一种基于无网格进化算法的线谱估计方法研究

作者及单位
本文由Bai Yan（南方科技大学可信自主系统研究院/广东省类脑智能计算重点实验室）、Qi Zhao、Jin Zhang（通讯作者）、J. Andrew Zhang（悉尼科技大学电气与数据工程学院）和Xin Yao（IEEE Fellow）共同完成，发表于2024年2月的《IEEE Transactions on Cybernetics》第54卷第2期。

学术背景

线谱估计（Line Spectral Estimation, LSE）是信号处理领域的核心问题，旨在从受噪声污染的测量数据中估计复杂正弦信号的频率成分并确定模型阶数（即频率数量）。该技术在雷达/声纳波达方向估计、无线通信信道估计和分子动力学模拟等领域具有重要应用价值。传统方法存在三大瓶颈：1）基于离散化网格（grid-based）的方法会因基失配问题导致估计偏差；2）现有无网格（gridless）方法采用原子l1范数等松弛指标，存在分辨率限制；3）模型阶数选择依赖经验阈值或渐进假设，在低信噪比（SNR）或有限快拍条件下性能急剧下降。

针对这些挑战，本研究提出创新性解决方案：通过多目标优化框架直接求解原子l0范数（atomic l0 norm）最小化问题，突破分辨率限制；设计可变长度进化搜索算法（MVESA），实现频率和模型阶数的联合精确估计。该研究获得中国国家自然科学基金（61701216）、深圳市基础研究项目（JCYJ20180507181527806）等多个项目支持。

研究方法与流程

1. 多目标优化模型构建

研究团队首先建立了双目标优化模型：

min f(θ, s) = (‖y‖_{a,0}, ‖y−As‖^2_F) 

其中第一目标‖y‖_{a,0}为原子l0范数（直接表征模型阶数k），第二目标‖y−As‖^2_F为测量误差。该设计具有两大优势： 1) 避免传统方法需要平衡参数调节的问题 2) 通过精确的原子l0范数（非松弛形式）突破分辨率限制

原子l0范数定义为：

‖y‖_{a,0} = inf_{θ_k,s_k} { κ : y = ∑_{k=1}^κ a(θ_k)s_k, θ ∈ [-1,1) } 

其中a(θ_k)=[1,e^{jπθ_k},…,e^{j(m-1)πθ_k}]^T为第k个正弦信号。

2. 可变长度进化算法设计

为解决上述NP难问题，研究团队开发了MVESA算法，其创新性体现在：

（1）可变长度编码与搜索策略
- 采用动态长度染色体表示不同模型阶数的解，例如个体编码为：

p = { (θ_1,s_1),...,(θ_n,s_n) }, θ_n=[θ_{n1},...,θ_{nd_n}] ∈ R^{1×d_n} 

• 改造基于相似性的Synapsing交叉算子：通过频率成分的欧氏距离匹配实现变长染色体对齐，随机选择交叉点数量n∈[1, min(d_p1,d_p2)]保持多样性
• 结合多项式变异（mutation probability=1/k）进行局部搜索

（2）模型阶数修剪机制
1) 归档操作：外部存档R_g保存各阶数最优解，通过非支配排序更新 2) 功率评估：按(8)式计算各频率成分功率：

p_i = √(∑_{l=1}^L |s_{il}|^2) 

3) 随机修剪：对新增存档解，按功率降序保留前(dn - k{cut})个频率，k_{cut}∈[1,d_n-1]为随机数

（3）计算流程
1. 初始化：生成30个个体（1个基于Capon方法，其余随机） 2. 迭代优化： - 二元锦标赛选择父代 - 变长交叉与多项式变异产生子代 - 最小二乘法恢复幅度矩阵：s=(A^TA)^{-1}A^Ty - 环境选择（NSGA-II机制） - 存档更新与模型修剪 3. 终止条件：测量误差变化<10^-6或迭代达100代 4. 输出：通过Kink方法从Pareto前沿识别膝点解

3. 实验验证方案

设置五组对照实验： 1. 噪声鲁棒性测试：SNR∈[-6,15]dB，k=4，m=15，t=30快拍 2. 模型阶数适应性：k∈[1,7]，m=15，t=10，SNR=10dB 3. 分辨率测试：双频间距Δ∈[0.02,0.26]，m=6 4. 不完整数据测试：有效测量数m_{sel}∈[6,20] 5. 时间复杂度分析：m∈[10,50]

评价指标： - 频率估计误差：RMSE(θ̂)=√(1/υ ∑‖θ̂-θ‖^2) - 阶数选择成功率：Pr(k=k̂)

主要研究成果

1. 性能对比实验

（1）噪声鲁棒性
当SNR=-5dB时，MVESA的RMSE为0.018，显著优于SPA（0.152）、RAM（0.121）和VALSE_MMV（0.035）；模型阶数识别成功率达82%，较次优方法(VALSE_MMV)提升29%。

（2）密集频率分辨
在Δ=0.04时，MVESA仍保持0.025的RMSE，而对比方法均失效（RMSE>0.3）。这验证了原子l0范数相比reweighted atomic norm等方法的分辨率优势。

（3）不完整数据重建
当m_{sel}=10（50%缺失）时，MVESA成功率保持68%，而SPA、RAM已降至<15%。表明变长搜索策略能有效探索欠定解空间。

2. 算法特性验证

（1）模型修剪机制有效性
在k=6实验中，带修剪的MVESA较无修剪版本RMSE降低42%，收敛代数减少60%。随机修剪策略使解空间探索更高效。

（2）计算效率
虽然MVESA时间复杂度为O(g_maxnm^3)（VALSE_MMV为O(m^2+ml)），但其并行特性可通过GPU加速。在m=30时单次运行平均耗时45秒（MATLAB平台）。

研究结论与价值

科学价值

1. 理论突破：首次将原子l0范数严格引入多目标优化框架，从理论上消除分辨率限制。仿真证明其最小可分辨频率间距达传统方法的1/6。
2. 方法创新：提出的变长编码策略实现动态维度搜索空间探索，为高维稀疏优化问题提供新思路。

应用价值

1. 工程适用性：在低SNR（<-5dB）、少快拍（t=10）等非渐近条件下仍保持稳定性能，适合实际系统中的实时处理。
2. 扩展潜力：算法框架可推广至DOA估计、雷达信号处理等领域。作者已开源核心代码促进应用。

研究亮点

1. 双重创新方法：

   • 理论层面：建立首个基于原子l0范数的多目标LSE模型，避免松弛带来的偏差
     
   • 算法层面：开发融合变长搜索与随机修剪的进化框架，解决NP难问题

2. 全面性能优势：
   在SNR=-5dB至15dB、k=1-7、Δ≥0.04等广泛场景下，RMSE平均降低62%，阶数识别准确率提升35%

3. 开源贡献：
   配套发布MATLAB/Python工具包，集成SPA、RAM等对比方法，推动领域基准测试

未来方向

作者指出三个拓展方向： 1. 开发更高效的矩阵求逆近似方法，降低O(m^3)计算复杂度 2. 研究统计一致性保证理论，提升大m场景下的估计精度 3. 探索深度学习与进化算法的混合架构，进一步强化噪声鲁棒性

本研究为非线性谱估计提供了新的方法论框架，其技术路线对解决高维稀疏优化问题具有普遍参考价值。