基于缩放梯度下降的点源信号快速且可证明的同步盲超分辨率与解混方法

《Digital Signal Processing》：Fast and Provable Simultaneous Blind Super-Resolution and Demixing for Point Source Signals via Scaled Gradient Descent

　　陈金池|向泽宇 中国上海华东理工大学数学学院 摘要 我们研究如何从低频观测到的多个点源信号的叠加卷积中同时恢复这些信号，且这些信号的点扩散函数是未知的。利用信号和点扩散函数固有的低维结构，我们将该问题转化为一个结构化的低秩矩阵解混问题。为了解决这个问题，我们改进了缩放梯度下降算法，加入了专为解混问题设计的新的收敛性保证。理论分析表明，在光谱初始化下，只要满足轻微的非相干性假设，缩放梯度下降算法就能线性收敛到真实值，而且其收敛速率与底层矩阵的条件数无关。数值实验进一步验证了该方法的有效性，其恢复性能可与最先进的凸优化方法相媲美，同时计算效率也有显著提升。引言 盲态超分辨率问题是指在点扩散函数未知的情况下，从信号的低频谱测量数据中估计出高分辨率信息。这项技术被广泛应用于地震数据分析[1]、核磁共振波谱分析[2]以及3D单分子显微镜技术[3]等领域。在本文中，我们探讨了一个更为复杂的问题，即需要从单个低频观测数据中提取多个点源信号。这类问题出现在集成感测与通信[4]、[5]、空中计算[6]、[7]以及物联网[8]等多种应用场景中。具体来说，考虑如下形式的点源信号序列：xk(t)=∑p=1rdk,pu(t?τk,p)，其中K表示信号或用户的数量，u(·)表示狄拉克函数，r表示第k个信号的脉冲数，{τk,p}p=1r?[0,1)是点源信号的位置，dk,pp=1r?C则是它们各自的幅度。设y(t)为这些点源信号与未知点扩散函数卷积后的结果，即y(t)=∑k=1K(∑p=1rdk,pu(t?τk,p)*gk,p(t))=∑k=1K∑p=1rdk,pgk,p(t?τk,p)。其中*表示卷积运算，gk,p代表未知的点扩散函数。对式(1)取傅里叶变换后，可得y^(f)=∑k=1K∑p=1rdk,p∫gk,p(t?τk,p)e?2?πftdt=∑k=1K∑p=1rdk,pg^k,p(f)e?2?πfτk,p，其中g^k,p(f)是gk,p(t)的傅里叶变换。经过采样后，我们有：y^[j]=∑k=1K∑p=1rdk,pe??2π(j?1)τk,pg^k,p[j]，此处gk,p:=[g^k,p[0]?g^k,p[n?1]]T∈Cn是未知的，j=0,?,n?1。我们的目标是从式(2)中同时恢复{dk,p, τk,p}和{gk,p}。我们将这个问题称为同步盲态超分辨率与解混问题。特别地，当只有一个用户（K=1）时，式(2)中的测量模型就简化为盲态超分辨率问题，相关研究可见[9]、[10]、[11]、[12]。此外，如果存在两种类型的信号（K=2），一种与通信相关，另一种与雷达相关，那么式(2)描述的问题可视为双盲反卷积问题，相关研究见[13]。由于式(2)中未知数的数量O(Knr)大于样本数量，因此同步盲态超分辨率与解混问题属于病态问题。为了解决这一问题，我们采用与[9]、[10]、[12]、[14]中相同的思路，假设与第k个未知点扩散函数相关的向量集{gk,p}p=1r属于由Bk∈Cn×s的列所构成的已知低维子空间，其中s??1情况）。不过，我们的方法与现有方法存在显著差异。 [22]中提出的PGD-VHL方法依赖于额外的投影操作来保持非相干性，并通过显式正则化手段来平衡两个低秩因子的范数。而我们的方法则无需此类投影或平衡项。同时，也有研究提出了带有理论保证的用于盲态超分辨率的缩放梯度下降方法[24]。不过，我们的研究解决的则是更为复杂的同步盲态超分辨率与解混问题。我们方法的关键在于构建合适的吸引域，并理解在线性感知算子被限制在块对角子空间时的特性。因此，我们的研究成果具有独特性，尚未被现有研究涵盖。这项工作也与低秩矩阵解混问题相关，后者涉及从单个测量向量中同时恢复多个低秩矩阵。具体而言，McCoy和Tropp[25]研究了由y=A(∑k=1KXk)表示的压缩解混模型，并提出了核范数最小化方法来恢复{Xk}。Strohmer和Wei[26]则基于高斯测量模型提出了一种具有理论保证的非凸解混算法。此外，还有研究探讨了从秩为一的观测数据中恢复秩为一矩阵的凸优化[27]、[28]和非凸优化[29]、[30]方法。但由于我们研究中的目标矩阵和感知算子结构与前述研究不同，这些研究中的理论保证无法直接应用于我们的模型。近年来，人们在开发用于低秩矩阵恢复的缩放或预处理算法方面取得了显著进展。这类缩放算法的设计理念类似于（黎曼）梯度下降法，只是加入了适当选择的预处理技术。实证和理论研究都表明，这类缩放方法在处理病态的低秩矩阵恢复问题时更具鲁棒性，且其计算成本与梯度下降法相当。此外，缩放梯度下降法还具有隐式正则化特性，无需像传统方法那样显式平衡低秩因子的范数（相关内容可见[31]、[32]、[33]及其中的参考文献）。关于缩放（交替）梯度下降法在低秩矩阵补全问题上的应用效果，已有研究在[34]、[35]、[36]中进行了阐述。最近，人们还建立了该方法的理论收敛性保证。Tong等人[37]证明，若进行光谱初始化，缩放梯度下降法在处理低秩矩阵感知问题时可实现线性收敛。Zhang等人[38]将[37]的研究结果扩展到了过参数化情况。Xu等人[39]给出了在小随机初始化条件下缩放梯度下降法的收敛性保证，而Cheng和Zhao[40]则进一步将Zhang等人[38]的成果推广到了非对称情况。尽管这些研究与我们的框架存在一些共通之处，但两者之间的重叠度其实很低。尽管盲态超分辨率和低秩矩阵恢复领域已经取得了很大进展，但仍有一些关键问题尚未解决：（i）将单用户场景下的盲态超分辨率理论（K=1）扩展到同步盲态超分辨率与解混场景（K?>?1）仍然是一个未解决的问题。（ii）现有的最先进算法通常依赖显式正则化或投影操作来平衡低秩因子，这就需要耗费大量精力进行超参数调整。（iii）当点源信号的位置过于集中时，相关的向量化汉克尔矩阵会变得极为病态，从而导致传统梯度下降法运行速度大幅降低。最近关于缩放（预处理）梯度方法的研究表明，这类方法能够在不增加额外计算成本的情况下缓解病态性问题，并隐式实现因子范数的平衡。受这些研究的启发，我们将同步盲态超分辨率与解混问题重新定义为结构化的低秩矩阵解混任务，并针对该任务对缩放梯度下降算法进行了优化。我们的主要贡献如下：•首个具有理论保证的非凸算法。利用块对角低秩结构，我们提出了首个在计算效率上具有优势且具有收敛性保证的同步盲态超分辨率与解混算法，该算法既不需要平衡正则化项，也不需要投影步骤。•无需考虑条件数的线性收敛性。在标准的非相干性假设下，我们分析了缩放梯度下降法的收敛速率，发现其在无噪声条件下，从光谱初始化开始可线性收敛到真实值，其样本复杂度为O(K2s2r2κ2μ02μ1log2(sn))。此外，其收敛速率与真实值的条件数无关，这进一步体现了该方法的高效性。•更优的实证性能。我们通过实验验证了缩放梯度下降法的恢复性能。数值实验表明，该方法的恢复能力可与原子范数最小化法和向量化汉克尔提升法等凸优化方法相媲美，同时计算效率却更高。本文的结构如下：第2节介绍恢复流程及缩放梯度下降算法；第3节给出所提方法的理论保证；第4节讨论数值实验结果；第5节至5-B节详细阐述我们主要结果的证明过程；第6节是对全文的总结。在整篇文章中，向量、矩阵和算子分别用粗体小写字母、粗体大写字母和花体字表示。给定一系列矩阵{Lk}k=1,?,K，令L=blkdiag(L1,?,LK)表示对应的块对角矩阵，其中blkdiag是MATLAB中用于构造块对角矩阵的函数。对于块对角矩阵V和W，基于L、R定义的缩放范数为：dS(V,W)=∥V(RHR)12∥F2+∥W(LHL)12∥F2，其对偶范数为dS*(V,W)=∥V(RHR)?12∥F2+∥W(LHL)?12∥F2。对于任意矩阵X，我们用∥X∥、∥X∥F分别表示X的谱范数和弗罗贝尼乌斯范数。两个矩阵X1和X2的内积定义为〈X1,X2〉:=trace(X1HX2)，其实部记为?X1, X2??。设σi(Z)表示Zk,?的第i个奇异值。我们用f(n)=O(g(n))表示当n足够大时，有|f(n)|?≤?C|g(n)|，其中C为某个常数。“以较高概率”这一表述意味着某事件的发生概率至少为1?(sn)?γ，这里的γ是常数，其具体数值在不同行中可能有所不同。为便于查阅，表1汇总了文中出现的主要符号。所有符号都在正文或附录首次出现时进行了定义，该表格可作为集中参考。算法 设Xk,?=[xk,1?xk,n]∈Cs×n，其第i列记为xk,i∈Cs，H为向量化汉克尔提升算子，该算子可将一个s?×?n矩阵转换为sn1?×?n2矩阵，即H(Xk,?)=[xk,1xk,2?xk,n2xk,2xk,3?xk,n2+1????xk,n1xk,n1+1?xk,n]，其中n1+n2=n+1。已有研究表明，Zk,?:=H(Xk,?)是一个秩为r的矩阵[12]。设G=HD?1:Cs×n→Csn×n2为加权向量化汉克尔提升算子，其中算子D:Cs×n→Cs×n的定义为D(Xk,?)=[w1xk,1?wnxk,n]，标量wi表示第i行的元素个数。主要结果 在本节中，我们将为所提出的方法提供理论保证。为此，我们先引入两个基本假设。假设3.1（μ0-非相干性）：假设BkH的各列{bk,i}，其中k=1,…,K，是来自均值为零的各向同性分布F的独立同分布样本。具体而言，E{b}=0，E{bbH}=I，这样的设定通过各向同性归一化确定了模型的尺度。此外，这些向量还满足以下非相干性条件：max1≤p≤s|b[p]|≤μ0。注3.1：这一假设最早是在……中提出的。数值实验 在本节中，我们通过一系列数值实验来评估所提方法在同步盲态超分辨率与解混问题中的性能。数值模拟是在配备多核Intel CPU（主频2.3 GHz）和16 GB内存的macOS机器上，使用MATLAB R2022b进行的。我们的代码可在“https://github.com/jcchen2017/Simultaneous-Blind-Super-Resolution-and-Demixing”获取。在最初的实验中，我们将所提出的方法与凸恢复技术进行了比较。

主要结果证明：为得出我们的主要结果，我们首先将公式（11）重新表述为一个块对角低秩矩阵恢复问题。设A为一个运算符，它可将Ks×Kn块对角矩阵映射为n×1向量，即A(X):=∑k=1KAk(Xk)，其中Ak的定义见公式（4），X=blkdiag(X1,?,XK)。A的伴随运算符记为A*，对于任意属于Cn的向量y，有A*(y)=blkdiag(A1*(y),?AK*(y))∈CKs×Kn。定义G?:CKs×Kn→CKsn1×Kn2，其表达式为G?(X)=blkdiag(G(X1),?G(XK))∈CKsn1×Kn2，则G?*的运算符形式为G?*(Z)=blk。

结论：在这项工作中，我们通过将同时盲超分辨率与解混问题转化为结构化的低秩矩阵解混任务来加以处理。借助最近在缩放梯度下降优化方面的进展，我们对原本用于低秩矩阵感知的缩放梯度下降算法进行了调整和改进，以适应这一更具挑战性的解混场景。我们的分析得出了样本复杂度界限，以及在与条件数无关的情况下的线性收敛速率。

参考文献：图5、表2。

作者致谢：陈金驰负责写作、审阅与编辑工作以及方法论设计；向泽宇负责可视化、数据分析和数值实验工作。

利益冲突声明：作者声明不存在任何可能影响本文研究结果的已知财务利益或个人关系。