譜壓縮感知的非凸低秩矩陣優(yōu)化模型與方法綜述*

楊在， 吳訓(xùn)蒙， 徐宗本

西安交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710049

考慮由少量單頻正弦波疊加構(gòu)成的譜稀疏信號(hào)，譜壓縮感知旨在從少量采樣中恢復(fù)出譜稀疏信號(hào)及其頻率參數(shù)，是信號(hào)與信息處理領(lǐng)域的基本問題.由于譜稀疏信號(hào)的頻率取值具有連續(xù)性，譜壓縮感知又被稱為連續(xù)壓縮感知、無限維壓縮感知或無柵格壓縮感知（Duarte et al.，2013；Tang et al.，2013）.數(shù)學(xué)上，譜稀疏信號(hào)X∈CN×L可以表示為

其中A(f) =[a(f1)，…，a(fK)]是一個(gè)N×K維的Vandermonde矩陣，

其中E∈CN×L為噪聲.譜壓縮感知的目標(biāo)是從Y中恢復(fù)出原信號(hào)X和頻率向量f.

在信息技術(shù)中，譜稀疏信號(hào)及其參數(shù)恢復(fù)又稱信號(hào)頻譜分析（Stoica et al.，2005），其領(lǐng)域中經(jīng)典的快速傅里葉變換方法（FFT，F(xiàn)ast Fourier Transform）被譽(yù)為20世紀(jì)十大算法之一（Dongarra et al.，2000）.當(dāng)通道數(shù)L= 1時(shí)，X=x∈CN×1被稱為單通道譜稀疏信號(hào)

當(dāng)L＞1時(shí)，X∈CN×L被稱為多通道譜稀疏信號(hào)

信號(hào)頻譜分析問題在陣列與雷達(dá)信號(hào)處理中有著廣泛應(yīng)用（Krim et al.，1996；Yang et al.，2018）.在國防軍事上，為通過雷達(dá)偵查空中飛行目標(biāo)，若干接收天線被布置成天線陣列，監(jiān)測飛行目標(biāo)的方位信息.每個(gè)信源均可引起空間中無線電信號(hào)的周期變化，其反映在天線陣列中的變化周期/頻率與信源方位密切相關(guān).在短時(shí)間內(nèi)采集多個(gè)時(shí)刻點(diǎn)的陣列輸出信號(hào)，這些信號(hào)組成了多通道的譜稀疏信號(hào).基于信號(hào)頻譜分析便可從陣列輸出信號(hào)中估計(jì)出信源方位信息.另外，信號(hào)頻譜分析問題亦常見于無線通信和用戶感知定位（Garcia et al.，2017）等實(shí)際問題.

當(dāng)L＞1 且S=BΦ，其中B= diag(b) ∈RK×K，bk＞0 且Φ ∈CK×L，Φkl= ei?kl時(shí)（即S在通道間的模恒定），X∈CN×L被稱為恒模譜稀疏信號(hào)（Leshem et al.，1999）：

顯然，恒模譜稀疏信號(hào)是一類具有恒模結(jié)構(gòu)的多通道譜稀疏信號(hào).由于無線通信和雷達(dá)中的發(fā)射信號(hào)經(jīng)常采用相位調(diào)制、頻率調(diào)制、相移鍵控和頻移鍵控等恒模調(diào)制方式，恒模譜稀疏信號(hào)普遍存在于陣列信號(hào)處理和通感一體化等實(shí)際問題中（Liu et al.，2018）.Wax（1992）、Williams et al.（1992）和Leshem et al.（1999）的研究表明，通過利用恒模結(jié)構(gòu)，可以在頻率的可辨識(shí)個(gè)數(shù)和估計(jì)精度上帶來顯著的性能增益.

對于單通道和多通道譜稀疏信號(hào)，傳統(tǒng)頻譜分析方法對數(shù)據(jù)質(zhì)量要求高，精度有限.早期基于FFT的波束成形方法雖然計(jì)算速度快，易于實(shí)現(xiàn)，但精度較低，需要充足的樣本數(shù)據(jù).極大似然估計(jì)具有漸近有效性，是統(tǒng)計(jì)估計(jì)的基本準(zhǔn)則和終極目標(biāo).然而參數(shù)域上的極大似然估計(jì)方法（Feder et al.，1988；Starer et al.，1992）需要求解高度非凸的優(yōu)化問題，其性能通常嚴(yán)重依賴于優(yōu)化算法的初始化選取，導(dǎo)致其在實(shí)際中難以應(yīng)用.上世紀(jì)70 年代提出的子空間方法（Paulraj et al.，1986；Schmidt，1986；Stoica et al.，1989）在理想數(shù)據(jù)環(huán)境下取得了不錯(cuò)的性能，但在數(shù)據(jù)稀缺（即通道數(shù)少）和數(shù)據(jù)缺失等非理想數(shù)據(jù)環(huán)境下，子空間方法的性能急劇下降.本世紀(jì)初建立起來的基于原子范數(shù)最小化的凸優(yōu)化方法（Candès et al.，2013；Tang et al.，2013；Candès et al.，2014；Yang et al.，2016）雖然顯著降低了對數(shù)據(jù)質(zhì)量的要求，但凸松弛導(dǎo)致其具有嚴(yán)格的分辨率限制，只能恢復(fù)相距較遠(yuǎn)的頻率參數(shù)，算法精度受限.對于恒模譜稀疏信號(hào)，由于恒模結(jié)構(gòu)會(huì)引入大量的非凸約束，現(xiàn)有的算法（Veen et al.，1996；Leshem et al.，1999；Leshem，2000；Stoica et al.，2000）要么無法完整利用信號(hào)先驗(yàn)結(jié)構(gòu)，要么對初始化高度敏感，從而導(dǎo)致性能不穩(wěn)定.

為提高算法精度，學(xué)界近期提出了針對譜壓縮感知的結(jié)構(gòu)低秩矩陣非凸優(yōu)化框架（Wu et al.，2022a；2022b；2023）.在此框架內(nèi)，通過精確刻畫譜稀疏信號(hào)的幾何結(jié)構(gòu)，將譜稀疏信號(hào)嵌入到結(jié)構(gòu)低秩矩陣中，從而將原參數(shù)域極大似然估計(jì)問題等價(jià)刻畫為信號(hào)域中的結(jié)構(gòu)低秩矩陣恢復(fù)問題，進(jìn)一步借助低秩矩陣恢復(fù)領(lǐng)域的前沿成果，提出了切實(shí)可行的信號(hào)域非凸優(yōu)化算法，避免了傳統(tǒng)參數(shù)域極大似然方法對于初始化敏感的根本缺陷，為譜壓縮感知問題求解提供了全新思路.本文綜述了針對單通道（Wu et al.，2022a）、多通道（Wu et al.，2023）和恒模（Wu et al.，2022b）這三類譜稀疏信號(hào)的結(jié)構(gòu)低秩矩陣恢復(fù)模型，總結(jié)了相應(yīng)的優(yōu)化求解算法，分析了這些模型的共性和特性，并對未來研究方向進(jìn)行了展望.

1 結(jié)構(gòu)低秩矩陣恢復(fù)框架

1.1 從參數(shù)域到信號(hào)域

假設(shè)頻率f和系數(shù)S是確定但未知的，E為隨機(jī)高斯白噪聲，頻譜分析中的參數(shù)域極大似然估計(jì)可以表述為以下非線性最小二乘問題

當(dāng)f給定時(shí)，通過最小二乘法可以容易地得到S的估計(jì)，因此問題關(guān)鍵是求解f.Stoica et al.（2005）的研究表明，問題（6）中的目標(biāo)函數(shù)關(guān)于頻率參數(shù)f高度非凸，難以設(shè)計(jì)算法找到全局最優(yōu)點(diǎn).

為解決問題（6）的可求解問題，Candès et al.（2013），Tang et al.（2013），Candès et al.（2014）和Yang et al.（2016）提出了基于原子范數(shù)最小化的凸優(yōu)化方法，帶來了譜壓縮感知領(lǐng)域的技術(shù)變革，但凸優(yōu)化方法本質(zhì)上是對原參數(shù)域非凸極大似然問題（6）的凸松弛，這種松弛帶來了精度和速度上的弊端.具體而言，凸松弛導(dǎo)致凸優(yōu)化方法具有嚴(yán)格的分辨率限制，只能恢復(fù)相距較遠(yuǎn)的頻率參數(shù)，算法精度受限.事實(shí)上，即使在無噪環(huán)境中，凸優(yōu)化方法也需要頻率間保持適當(dāng)距離.此外，凸優(yōu)化方法最終需求解半正定規(guī)劃問題，而針對后者的算法往往都存在計(jì)算復(fù)雜度過高的缺陷，這導(dǎo)致凸優(yōu)化方法在計(jì)算速度上受限.精度和速度的兩大弊端嚴(yán)重制約了凸優(yōu)化方法在實(shí)際場景中的應(yīng)用.近幾年，學(xué)界在上述凸優(yōu)化框架下探索了精度與速度的折中（Morgenshtern et al.，2016；Wang et al.，2018；Zhang et al.，2022），但無法在兩方面同時(shí)進(jìn)行改進(jìn).

不同于上述的參數(shù)域極大似然方法和凸優(yōu)化方法，Wu et al.（2022a）提出了信號(hào)域的極大似然方法，其將問題（6）等價(jià)表述為頻譜稀疏結(jié)構(gòu)約束下的信號(hào)恢復(fù)問題

其中譜稀疏信號(hào)集合

其具體形式根據(jù)考慮的譜稀疏信號(hào)種類不同而有所變化.問題（7）的變量為信號(hào)X，故其被稱為信號(hào)域上的極大似然估計(jì)問題.通過將問題（6）等價(jià)為問題（7），目標(biāo)函數(shù)的非凸性被轉(zhuǎn)移到約束中.針對問題（7）設(shè)計(jì)切實(shí)可行的非凸優(yōu)化算法，有望避免傳統(tǒng)參數(shù)域非凸優(yōu)化方法對于初始化敏感的根本缺陷，取得精度上的提升.

1.2 信號(hào)域上的結(jié)構(gòu)低秩矩陣優(yōu)化

要使問題（7）變成一個(gè)可求解的優(yōu)化問題，關(guān)鍵是為S0構(gòu)造一個(gè)等價(jià)且可計(jì)算的代理集合.注意到S0中蘊(yùn)含了Vandermonde和稀疏這兩大類幾何結(jié)構(gòu)，為刻畫這兩類結(jié)構(gòu)同時(shí)保證問題的可求解性，學(xué)界提出了構(gòu)造結(jié)構(gòu)低秩矩陣的思想（Andersson et al.，2014；Wu et al.，2022a；Wu et al.，2022b；Wu et al.，2023），其中矩陣的特殊結(jié)構(gòu)用于刻畫Vandermonde結(jié)構(gòu)，矩陣的低秩性則是為了利用信號(hào)的稀疏性.在這一結(jié)構(gòu)低秩矩陣框架下，問題（7）被等價(jià)轉(zhuǎn)化為低秩矩陣優(yōu)化問題：

其中SM是結(jié)構(gòu)低秩矩陣約束下的信號(hào)集合，它滿足SM=S0.

值得注意的是，SM的構(gòu)造并非易事.根據(jù)所利用的矩陣結(jié)構(gòu)的不同，現(xiàn)有方法大致可以分為三類：基于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方法中的優(yōu)化問題雖然易于求解，但其沒有利用譜稀疏信號(hào)的無衰減（即=1，j= 1，…，N）這一先驗(yàn)結(jié)構(gòu)，導(dǎo)致構(gòu)造出的SM要大于S0.為利用無衰減的先驗(yàn)，Yang et al.（2023）提出了基于double Hankel 矩陣的方法，其構(gòu)造出的SM比Hankel方法的要更接近S0，但仍然無法保證完全等價(jià).相反，Toeplitz方法通過引入新的Toeplitz矩陣變量，保證了其構(gòu)造出的SM和S0間的等價(jià)性，但其非凸優(yōu)化問題中新引入變量的最優(yōu)解不唯一且無界，導(dǎo)致難以設(shè)計(jì)有效的非凸優(yōu)化算法進(jìn)行求解.Wu et al.（2022a）提出的基于Hankel-Toeplitz 矩陣的方法克服了Hankel 方法和Toeplitz 方法的缺陷，并同時(shí)繼承了它們的優(yōu)點(diǎn)，即其構(gòu)造的SM等價(jià)于S0，且對應(yīng)的問題（8）的最優(yōu)解唯一.

本文重點(diǎn)介紹基于Hankel-Toeplitz 矩陣的這類方法.如前所述，單通道、多通道和恒模這三類譜稀疏信號(hào)雖然都屬于S0，但其各自系數(shù)S的具體形式各有特點(diǎn)，因此需要基于Hankel-Toeplitz矩陣構(gòu)造不同的SM.在接下來的三節(jié)中，我們將對三類信號(hào)對應(yīng)的基于Hankel-Toeplitz 低秩矩陣的模型和優(yōu)化算法進(jìn)行逐一介紹.

2 單通道譜壓縮感知

2.1 單通道信號(hào)的Hankel-Toeplitz低秩矩陣模型

對于式（3）中的單通道譜稀疏信號(hào)x∈CN，對應(yīng)的信號(hào)集合

不失一般性，假設(shè)N= 2n- 1，Wu et al.（2022a）中構(gòu)造了基于Hankel-Toeplitz低秩結(jié)構(gòu)矩陣的集合

和兩個(gè)互為共軛的Hermitian Toeplitz矩陣

定理1（Wu et al.，2022a） 假設(shè)K＜n，則如下命題成立：

假設(shè)原極大似然估計(jì)問題（6）的最優(yōu)解是{fML，sML}，其中sMLk≠0 幾乎成立（若不成立，則y可以由K- 1 個(gè)或更少的正弦波疊加而成，當(dāng)有噪聲存在時(shí)，這種情況出現(xiàn)的概率為零）.根據(jù)唯一性，問題（11）具有如下唯一最優(yōu)解

最優(yōu)解唯一使得我們能夠設(shè)計(jì)非凸優(yōu)化算法有效地求解問題（11），繼而頻率f可以通過使用子空間方法（Paulraj et al.，1986；Schmidt，1986；Stoica et al.，1989）計(jì)算式（12）中Topelitz 矩陣的Vandermonde 分解得到.

2.2 優(yōu)化算法

由于秩約束的存在，問題（11）是非凸優(yōu)化問題.近年來交替方向乘子法（ADMM，Alternating Direction Method of Multipliers）（Boyd et al.，2011）在求解凸優(yōu)化和非凸優(yōu)化問題時(shí)都取得了優(yōu)異的性能表現(xiàn)（Andersson et al.，2014），因此Wu et al.（2022a）采用ADMM對問題（11）進(jìn)行求解，具體求解過程如下：

問題（13）的增廣Lagrange函數(shù)

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

子問題（14）的解為（Dax，2014）

其中投影是通過對Hermitian矩陣做截?cái)嗵卣髦捣纸鈱?shí)現(xiàn)，截?cái)嗟姆绞綖椋喝粽卣髦档臄?shù)量大于或等于K，則保留前K個(gè)特征值，令其余特征值為0；若正特征值的數(shù)量小于K，則保留所有的正特征值，令其余特征值為0.

其中I為單位陣，HH和TH分別表示Hankel 算子和Toeplitz 算子的伴隨算子，DH= diag{1，2，…，n，n- 1，…，1} 和DT= diag{n，n- 1，…，1}.

3 多通道譜壓縮感知

3.1 多通道信號(hào)的Hankel-Toeplitz低秩矩陣模型

對于式（4）中的多通道譜稀疏信號(hào)X∈CN×L，其對應(yīng)的信號(hào)集合= S0.與單通道信號(hào)相比，多通道信號(hào)不僅擁有更多的通道數(shù)據(jù)，更重要的是各通道間都共享著相同的頻率參數(shù)，即聯(lián)合稀疏性.因此，有效地利用聯(lián)合稀疏性是解決多通道譜壓縮感知問題的核心.為刻畫中的信號(hào)幾何結(jié)構(gòu)，Wu et al.（2023）構(gòu)造了基于Hankel-Toeplitz低秩結(jié)構(gòu)矩陣的集合

且其最優(yōu)解唯一.

3.2 優(yōu)化算法

與單通道情形相同，Wu et al.（2023）提出采用ADMM 對秩約束下的非凸優(yōu)化問題（17）進(jìn)行求解.不同的是，此處問題（17）中的變量{tl}和t耦合在一起，不能分離求解.Wu et al.（2023）的求解過程簡要概況如下：

問題（18）的增廣Lagrange函數(shù)

ADMM的算法迭代步驟如下

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

子問題（19）的解為（Dax，2014）

對于關(guān)于{{tl}，t}的子問題，使用Lagrange乘子法，可以得到如下更新公式

4 恒模譜壓縮感知

4.1 恒模信號(hào)的Hankel-Toeplitz低秩矩陣模型

對于式（5）中的恒模譜稀疏信號(hào)X∈CN×L，其對應(yīng)的信號(hào)集合

與多通道信號(hào)相比，恒模信號(hào)的特性在于系數(shù)S在其通道間的模是恒定的.針對恒模信號(hào)去構(gòu)造結(jié)構(gòu)低秩矩陣的關(guān)鍵在于有效利用恒模結(jié)構(gòu).Wu et al.（2022b）構(gòu)造了基于Hankel-Toeplitz低秩矩陣的集合

其中CM是constant modulus的縮寫，并給出了如下定理：

定理3假設(shè)K＜n，則如下命題成立：

和單通道情形類似，由定理3 知問題（23）的最優(yōu)解是唯一的.由于實(shí)際計(jì)算中難以保證兩個(gè)矩陣的秩相等，Wu et al.（2022b）考慮松弛后的問題

通過分析和實(shí)驗(yàn)得出，這種松弛是近似緊的，一般不會(huì)改變問題的最優(yōu)解.

4.2 優(yōu)化算法

和問題（17）相比，問題（24）中變量有所減少.Wu et al.（2022b）同樣采用了ADMM 求解.首先簡記引入一系列輔助變量{Ql∈C2n×2n}，問題（24）可以等價(jià)為

問題（25）的增廣Lagrange函數(shù)

ADMM的迭代更新步驟為

子問題（26）的解為（Dax，2014）

5 總結(jié)與展望

本文從模型和算法兩方面系統(tǒng)地總結(jié)了譜壓縮感知問題的結(jié)構(gòu)低秩矩陣恢復(fù)方法.從模型層面而言，單通道、多通道和恒模這三類譜稀疏信號(hào)的優(yōu)化模型雖都利用了Hankel-Toeplitz低秩矩陣，但在具體形式上卻有著本質(zhì)區(qū)別.從算法層面而言，三個(gè)優(yōu)化模型都采用了ADMM算法求解.值得注意的是，單通道的模型可以看作多通道模型和恒模模型的特殊形式，當(dāng)通道數(shù)L= 1時(shí)，以上針對多通道信號(hào)和恒模信號(hào)的結(jié)果均退化為單通道信號(hào)的結(jié)果.Wu et al.（2022a；2022b；2023）給出了大量的實(shí)驗(yàn)仿真，驗(yàn)證了相對于已有最先進(jìn)的方法，上述基于Hankel-Toeplitz低秩矩陣的方法在算法精度上都有著顯著提升.

由于上述方法中的ADMM 算法在每步迭代中都要進(jìn)行K截?cái)嗵卣髦捣纸?，此分解通常有著較高的計(jì)算復(fù)雜度O(N2K)（Halko et al.，2011），制約了方法整體的計(jì)算速度，因此未來的一個(gè)研究方向是對于Hankel-Toeplitz低秩矩陣模型，設(shè)計(jì)加速算法，降低計(jì)算復(fù)雜度，以此來滿足實(shí)際系統(tǒng)中低時(shí)延高速度的需求.另外，由于學(xué)界對ADMM 算法在求解非凸優(yōu)化問題時(shí)的理論收斂性和最優(yōu)性還處在研究之中，導(dǎo)致上述方法的收斂性結(jié)果（Wu et al.，2022a；2022b；2023）較弱，給出更強(qiáng)的理論保證也將是未來研究的方向.最后，我們考慮將上述的結(jié)構(gòu)低秩矩陣恢復(fù)框架應(yīng)用于具體的工程問題，結(jié)合實(shí)際系統(tǒng)的特性來改進(jìn)和拓展模型.