谱压缩感知的非凸低秩矩阵优化模型与方法综述*

杨在， 吴训蒙， 徐宗本

西安交通大学数学与统计学院，陕西 西安 710049

考虑由少量单频正弦波叠加构成的谱稀疏信号，谱压缩感知旨在从少量采样中恢复出谱稀疏信号及其频率参数，是信号与信息处理领域的基本问题.由于谱稀疏信号的频率取值具有连续性，谱压缩感知又被称为连续压缩感知、无限维压缩感知或无栅格压缩感知（Duarte et al.，2013；Tang et al.，2013）.数学上，谱稀疏信号X∈CN×L可以表示为

其中A(f) =[a(f1)，…，a(fK)]是一个N×K维的Vandermonde矩阵，

其中E∈CN×L为噪声.谱压缩感知的目标是从Y中恢复出原信号X和频率向量f.

在信息技术中，谱稀疏信号及其参数恢复又称信号频谱分析（Stoica et al.，2005），其领域中经典的快速傅里叶变换方法（FFT，Fast Fourier Transform）被誉为20世纪十大算法之一（Dongarra et al.，2000）.当通道数L= 1时，X=x∈CN×1被称为单通道谱稀疏信号

当L＞1时，X∈CN×L被称为多通道谱稀疏信号

信号频谱分析问题在阵列与雷达信号处理中有着广泛应用（Krim et al.，1996；Yang et al.，2018）.在国防军事上，为通过雷达侦查空中飞行目标，若干接收天线被布置成天线阵列，监测飞行目标的方位信息.每个信源均可引起空间中无线电信号的周期变化，其反映在天线阵列中的变化周期/频率与信源方位密切相关.在短时间内采集多个时刻点的阵列输出信号，这些信号组成了多通道的谱稀疏信号.基于信号频谱分析便可从阵列输出信号中估计出信源方位信息.另外，信号频谱分析问题亦常见于无线通信和用户感知定位（Garcia et al.，2017）等实际问题.

当L＞1 且S=BΦ，其中B= diag(b) ∈RK×K，bk＞0 且Φ ∈CK×L，Φkl= eiϕkl时（即S在通道间的模恒定），X∈CN×L被称为恒模谱稀疏信号（Leshem et al.，1999）：

显然，恒模谱稀疏信号是一类具有恒模结构的多通道谱稀疏信号.由于无线通信和雷达中的发射信号经常采用相位调制、频率调制、相移键控和频移键控等恒模调制方式，恒模谱稀疏信号普遍存在于阵列信号处理和通感一体化等实际问题中（Liu et al.，2018）.Wax（1992）、Williams et al.（1992）和Leshem et al.（1999）的研究表明，通过利用恒模结构，可以在频率的可辨识个数和估计精度上带来显著的性能增益.

对于单通道和多通道谱稀疏信号，传统频谱分析方法对数据质量要求高，精度有限.早期基于FFT的波束成形方法虽然计算速度快，易于实现，但精度较低，需要充足的样本数据.极大似然估计具有渐近有效性，是统计估计的基本准则和终极目标.然而参数域上的极大似然估计方法（Feder et al.，1988；Starer et al.，1992）需要求解高度非凸的优化问题，其性能通常严重依赖于优化算法的初始化选取，导致其在实际中难以应用.上世纪70 年代提出的子空间方法（Paulraj et al.，1986；Schmidt，1986；Stoica et al.，1989）在理想数据环境下取得了不错的性能，但在数据稀缺（即通道数少）和数据缺失等非理想数据环境下，子空间方法的性能急剧下降.本世纪初建立起来的基于原子范数最小化的凸优化方法（Candès et al.，2013；Tang et al.，2013；Candès et al.，2014；Yang et al.，2016）虽然显著降低了对数据质量的要求，但凸松弛导致其具有严格的分辨率限制，只能恢复相距较远的频率参数，算法精度受限.对于恒模谱稀疏信号，由于恒模结构会引入大量的非凸约束，现有的算法（Veen et al.，1996；Leshem et al.，1999；Leshem，2000；Stoica et al.，2000）要么无法完整利用信号先验结构，要么对初始化高度敏感，从而导致性能不稳定.

为提高算法精度，学界近期提出了针对谱压缩感知的结构低秩矩阵非凸优化框架（Wu et al.，2022a；2022b；2023）.在此框架内，通过精确刻画谱稀疏信号的几何结构，将谱稀疏信号嵌入到结构低秩矩阵中，从而将原参数域极大似然估计问题等价刻画为信号域中的结构低秩矩阵恢复问题，进一步借助低秩矩阵恢复领域的前沿成果，提出了切实可行的信号域非凸优化算法，避免了传统参数域极大似然方法对于初始化敏感的根本缺陷，为谱压缩感知问题求解提供了全新思路.本文综述了针对单通道（Wu et al.，2022a）、多通道（Wu et al.，2023）和恒模（Wu et al.，2022b）这三类谱稀疏信号的结构低秩矩阵恢复模型，总结了相应的优化求解算法，分析了这些模型的共性和特性，并对未来研究方向进行了展望.

1 结构低秩矩阵恢复框架

1.1 从参数域到信号域

假设频率f和系数S是确定但未知的，E为随机高斯白噪声，频谱分析中的参数域极大似然估计可以表述为以下非线性最小二乘问题

当f给定时，通过最小二乘法可以容易地得到S的估计，因此问题关键是求解f.Stoica et al.（2005）的研究表明，问题（6）中的目标函数关于频率参数f高度非凸，难以设计算法找到全局最优点.

为解决问题（6）的可求解问题，Candès et al.（2013），Tang et al.（2013），Candès et al.（2014）和Yang et al.（2016）提出了基于原子范数最小化的凸优化方法，带来了谱压缩感知领域的技术变革，但凸优化方法本质上是对原参数域非凸极大似然问题（6）的凸松弛，这种松弛带来了精度和速度上的弊端.具体而言，凸松弛导致凸优化方法具有严格的分辨率限制，只能恢复相距较远的频率参数，算法精度受限.事实上，即使在无噪环境中，凸优化方法也需要频率间保持适当距离.此外，凸优化方法最终需求解半正定规划问题，而针对后者的算法往往都存在计算复杂度过高的缺陷，这导致凸优化方法在计算速度上受限.精度和速度的两大弊端严重制约了凸优化方法在实际场景中的应用.近几年，学界在上述凸优化框架下探索了精度与速度的折中（Morgenshtern et al.，2016；Wang et al.，2018；Zhang et al.，2022），但无法在两方面同时进行改进.

不同于上述的参数域极大似然方法和凸优化方法，Wu et al.（2022a）提出了信号域的极大似然方法，其将问题（6）等价表述为频谱稀疏结构约束下的信号恢复问题

其中谱稀疏信号集合

其具体形式根据考虑的谱稀疏信号种类不同而有所变化.问题（7）的变量为信号X，故其被称为信号域上的极大似然估计问题.通过将问题（6）等价为问题（7），目标函数的非凸性被转移到约束中.针对问题（7）设计切实可行的非凸优化算法，有望避免传统参数域非凸优化方法对于初始化敏感的根本缺陷，取得精度上的提升.

1.2 信号域上的结构低秩矩阵优化

要使问题（7）变成一个可求解的优化问题，关键是为S0构造一个等价且可计算的代理集合.注意到S0中蕴含了Vandermonde和稀疏这两大类几何结构，为刻画这两类结构同时保证问题的可求解性，学界提出了构造结构低秩矩阵的思想（Andersson et al.，2014；Wu et al.，2022a；Wu et al.，2022b；Wu et al.，2023），其中矩阵的特殊结构用于刻画Vandermonde结构，矩阵的低秩性则是为了利用信号的稀疏性.在这一结构低秩矩阵框架下，问题（7）被等价转化为低秩矩阵优化问题：

其中SM是结构低秩矩阵约束下的信号集合，它满足SM=S0.

值得注意的是，SM的构造并非易事.根据所利用的矩阵结构的不同，现有方法大致可以分为三类：基于Hankel 矩阵（Andersson et al.，2014；Yang et al.，2023）、基于Toeplitz 矩阵（Tang et al.，2013；Yang et al.，2016）、以及基于Hankel-Toeplitz 矩阵（Wu et al.，2022a；2022b；2023）.Wu et al.（2022a）分析指出，基于Hankel矩阵和基于Toeplitz矩阵的两类方法都存在着难以克服的根本性缺陷.具体而言，Hankel方法中的优化问题虽然易于求解，但其没有利用谱稀疏信号的无衰减（即=1，j= 1，…，N）这一先验结构，导致构造出的SM要大于S0.为利用无衰减的先验，Yang et al.（2023）提出了基于double Hankel 矩阵的方法，其构造出的SM比Hankel方法的要更接近S0，但仍然无法保证完全等价.相反，Toeplitz方法通过引入新的Toeplitz矩阵变量，保证了其构造出的SM和S0间的等价性，但其非凸优化问题中新引入变量的最优解不唯一且无界，导致难以设计有效的非凸优化算法进行求解.Wu et al.（2022a）提出的基于Hankel-Toeplitz 矩阵的方法克服了Hankel 方法和Toeplitz 方法的缺陷，并同时继承了它们的优点，即其构造的SM等价于S0，且对应的问题（8）的最优解唯一.

本文重点介绍基于Hankel-Toeplitz 矩阵的这类方法.如前所述，单通道、多通道和恒模这三类谱稀疏信号虽然都属于S0，但其各自系数S的具体形式各有特点，因此需要基于Hankel-Toeplitz矩阵构造不同的SM.在接下来的三节中，我们将对三类信号对应的基于Hankel-Toeplitz 低秩矩阵的模型和优化算法进行逐一介绍.

2 单通道谱压缩感知

2.1 单通道信号的Hankel-Toeplitz低秩矩阵模型

对于式（3）中的单通道谱稀疏信号x∈CN，对应的信号集合

不失一般性，假设N= 2n- 1，Wu et al.（2022a）中构造了基于Hankel-Toeplitz低秩结构矩阵的集合

和两个互为共轭的Hermitian Toeplitz矩阵

定理1（Wu et al.，2022a） 假设K＜n，则如下命题成立：

假设原极大似然估计问题（6）的最优解是{fML，sML}，其中sMLk≠0 几乎成立（若不成立，则y可以由K- 1 个或更少的正弦波叠加而成，当有噪声存在时，这种情况出现的概率为零）.根据唯一性，问题（11）具有如下唯一最优解

最优解唯一使得我们能够设计非凸优化算法有效地求解问题（11），继而频率f可以通过使用子空间方法（Paulraj et al.，1986；Schmidt，1986；Stoica et al.，1989）计算式（12）中Topelitz 矩阵的Vandermonde 分解得到.

2.2 优化算法

由于秩约束的存在，问题（11）是非凸优化问题.近年来交替方向乘子法（ADMM，Alternating Direction Method of Multipliers）（Boyd et al.，2011）在求解凸优化和非凸优化问题时都取得了优异的性能表现（Andersson et al.，2014），因此Wu et al.（2022a）采用ADMM对问题（11）进行求解，具体求解过程如下：

问题（13）的增广Lagrange函数

其中每步迭代中其它变量均使用往步迭代更新后的值.

子问题（14）的解为（Dax，2014）

其中投影是通过对Hermitian矩阵做截断特征值分解实现，截断的方式为：若正特征值的数量大于或等于K，则保留前K个特征值，令其余特征值为0；若正特征值的数量小于K，则保留所有的正特征值，令其余特征值为0.

其中I为单位阵，HH和TH分别表示Hankel 算子和Toeplitz 算子的伴随算子，DH= diag{1，2，…，n，n- 1，…，1} 和DT= diag{n，n- 1，…，1}.

3 多通道谱压缩感知

3.1 多通道信号的Hankel-Toeplitz低秩矩阵模型

对于式（4）中的多通道谱稀疏信号X∈CN×L，其对应的信号集合= S0.与单通道信号相比，多通道信号不仅拥有更多的通道数据，更重要的是各通道间都共享着相同的频率参数，即联合稀疏性.因此，有效地利用联合稀疏性是解决多通道谱压缩感知问题的核心.为刻画中的信号几何结构，Wu et al.（2023）构造了基于Hankel-Toeplitz低秩结构矩阵的集合

且其最优解唯一.

3.2 优化算法

与单通道情形相同，Wu et al.（2023）提出采用ADMM 对秩约束下的非凸优化问题（17）进行求解.不同的是，此处问题（17）中的变量{tl}和t耦合在一起，不能分离求解.Wu et al.（2023）的求解过程简要概况如下：

问题（18）的增广Lagrange函数

ADMM的算法迭代步骤如下

其中每步迭代中其它变量均使用往步迭代更新后的值.

子问题（19）的解为（Dax，2014）

对于关于{{tl}，t}的子问题，使用Lagrange乘子法，可以得到如下更新公式

4 恒模谱压缩感知

4.1 恒模信号的Hankel-Toeplitz低秩矩阵模型

对于式（5）中的恒模谱稀疏信号X∈CN×L，其对应的信号集合

与多通道信号相比，恒模信号的特性在于系数S在其通道间的模是恒定的.针对恒模信号去构造结构低秩矩阵的关键在于有效利用恒模结构.Wu et al.（2022b）构造了基于Hankel-Toeplitz低秩矩阵的集合

其中CM是constant modulus的缩写，并给出了如下定理：

定理3假设K＜n，则如下命题成立：

和单通道情形类似，由定理3 知问题（23）的最优解是唯一的.由于实际计算中难以保证两个矩阵的秩相等，Wu et al.（2022b）考虑松弛后的问题

通过分析和实验得出，这种松弛是近似紧的，一般不会改变问题的最优解.

4.2 优化算法

和问题（17）相比，问题（24）中变量有所减少.Wu et al.（2022b）同样采用了ADMM 求解.首先简记引入一系列辅助变量{Ql∈C2n×2n}，问题（24）可以等价为

问题（25）的增广Lagrange函数

ADMM的迭代更新步骤为

子问题（26）的解为（Dax，2014）

5 总结与展望

本文从模型和算法两方面系统地总结了谱压缩感知问题的结构低秩矩阵恢复方法.从模型层面而言，单通道、多通道和恒模这三类谱稀疏信号的优化模型虽都利用了Hankel-Toeplitz低秩矩阵，但在具体形式上却有着本质区别.从算法层面而言，三个优化模型都采用了ADMM算法求解.值得注意的是，单通道的模型可以看作多通道模型和恒模模型的特殊形式，当通道数L= 1时，以上针对多通道信号和恒模信号的结果均退化为单通道信号的结果.Wu et al.（2022a；2022b；2023）给出了大量的实验仿真，验证了相对于已有最先进的方法，上述基于Hankel-Toeplitz低秩矩阵的方法在算法精度上都有着显著提升.

由于上述方法中的ADMM 算法在每步迭代中都要进行K截断特征值分解，此分解通常有着较高的计算复杂度O(N2K)（Halko et al.，2011），制约了方法整体的计算速度，因此未来的一个研究方向是对于Hankel-Toeplitz低秩矩阵模型，设计加速算法，降低计算复杂度，以此来满足实际系统中低时延高速度的需求.另外，由于学界对ADMM 算法在求解非凸优化问题时的理论收敛性和最优性还处在研究之中，导致上述方法的收敛性结果（Wu et al.，2022a；2022b；2023）较弱，给出更强的理论保证也将是未来研究的方向.最后，我们考虑将上述的结构低秩矩阵恢复框架应用于具体的工程问题，结合实际系统的特性来改进和拓展模型.