基于相干性框架的部分支集已知的信號重建

武思琪 儒瑛 關晉瑞

DOI：10.16246/j.issn.1673-5072.2024.04.004

收稿日期：2022-11-22? 基金項目：國家自然科學基金項目（12001395）；山西省應用基礎研究計劃項目（201901D211423）

作者簡介：武思琪（1997—），女，碩士研究生，主要從事壓縮感知方面的研究。

通信作者：宋儒瑛（1964—），男，博士，教授，碩士生導師，主要從事逼近論及壓縮感知方面的研究。E-mail：tysyr@126.com

引文格式：武思琪，宋儒瑛，關晉瑞.基于相干性框架的部分支集已知的信號重建［J］.西華師范大學學報（自然科學版），2024，45（4）：367-374.［WU S Q，SONG R Y，GUAN J R，et al.Signal reconstruction with known partial support based on coherence framework［J］.Journal of China West Normal University （Natural Sciences），2024，45（4）：367-374.］

摘? 要：文章使用2－α2（0<α1）最小化模型利用信號自身的先驗支撐信息來重建高維稀疏信號。這是首篇基于相干性框架的部分支集已知的信號重建，重點討論3種噪聲（2有界噪聲、Dantzig Selector噪聲和脈沖噪聲）情形下信號魯棒恢復的充分條件和誤差估計。

關鍵詞：壓縮感知；部分支集已知；1－α2最小化；相干性；誤差估計

中圖分類號：O211.5??? 文獻標志碼：A??? 文章編號：1673-5072（2024）04-0367-08

壓縮感知是從較少的測量值y=Ax+e中恢復一個可壓縮（或稀疏）信號x∈n，其中A∈m×n（mn）是一個感知矩陣，e∈m是噪聲，常見的噪聲情形分別是脈沖噪聲、2有界噪聲、Dantzig Selector（DS）噪聲。0最小化方法是重建稀疏信號最直接的方法，但其是NP-難的。因此，Candes等［1］對其進行凸松弛，技巧性地將涉及多個子問題的優化問題轉化為如下的凸優化問題：

minx∈n‖x‖1? s. t.? y=Ax。（1）

當前有若干方法能從y中恢復x。例如：1最小化［2］，q（0

minx∈n‖x‖1－α‖x‖2?? s. t.?? y=Ax。（2）

非凸1－α2最小化方法在稀疏信號恢復問題上優于許多現存的壓縮感知求解方法［7-10］。文獻［7-8］說明了使用1－2最小化方法得到的基于限制等距性的信號恢復的充分條件要優于許多現存的壓縮感知求解方法得到的充分條件；文獻［9-10］使用一種分解向量的新方法，說明了在高斯噪聲、脈沖噪聲和均勻噪聲下利用1－α2最小化方法恢復信號的性能優于許多現存的壓縮感知求解方法。在應用中，若想要提高信號恢復的效率，減少恢復中測量的次數，通常會用到信號自身存在的一些先驗信息，其中較常用的是先驗支撐信息。已有學者將其與1模型［2］、q（0

minx∈n‖xTc‖1－α‖xTc‖2 ?s.t.? y－Ax∈B，（3）

其中，T為x的部分已知支撐，Tc={1，2，…，n}/T，B代表噪聲類型。若B={0}（無噪情形），則

minx∈n‖xTc‖1－α‖xTc‖2，? s.t.? y=Ax。（4）

這是首篇在相干性的框架中，建立保證部分支集已知信號魯棒恢復的條件，并分別給出受3種噪聲干擾下的誤差估計。

1? 預備定義和引理

為敘述方便，在這里對符號進行說明：向量x，x^∈n，其中x是原始信號，x^是式（3）的解。令h=x^－x，假設x的部分已知支撐是T，T=s，xT=x－xTc。 r=x－xT是殘差，rT0是r的最佳k-項逼近，T0包含由r中最大k個絕對值項的指標，T∩T0=。令Tc={1，2，…，n}＼T是T的補集。T1包含hTc中最大k個絕對值項的指標，現設定T0—=T∪T0，T—0c=T∪T1，T—1c=（T∪T0）c，T1—c=（T∪T1）c。

定義1［19］? 矩陣A的相干性μ是A各列之間相互關聯的最大絕對值，即

μ∶=maxi≠j〈Ai，Aj〉‖Ai‖2‖Aj‖2。

定義2［20］? 若存在一個最小的常數θk1，k20，對每個k1-稀疏信號f和k2-稀疏信號g，使得

〈Af，Ag〉θk1，k2‖f‖2‖g‖2

成立，則稱矩陣A∈m×n滿足（k1，k2）階的限制正交性，其中θk1，k2是（k1，k2）階的限制正交常數。

引理1［16］? 對測量矩陣A的相干性μ和任意m-稀疏向量f，得到

1－（m－1）μ‖Af‖22‖f‖221+（m－1）μ。

引理2［20］? 令k1，k2n，η0，假設f，g∈n有不相交的支撐，且‖f‖0k1。若g滿足‖g‖1ηk2，‖g‖

SymboleB@ η，則

〈Af，Ag〉k2θk1，k2η‖f‖2。

引理3［20］? 假設ln，f1f2…fn0，γ0，且∑li=1fi+γ∑ni=l+1fi，則對所有p1，

∑ni=l+1fp ilp∑li=1fpil+γlp。

2? 主要結論

在恢復信號時，通常需要消除噪聲所帶來的影響。假定x是壓縮信號，現考慮以下3種噪聲情形：（1）B2（ε）={e：‖e‖2ε}； （2）BDS（ε）={e：‖ATe‖

SymboleB@ ε}；（3）B1（ε）={e：‖e‖1ε。}

定理1? 考慮y=Ax+e，其中‖e‖2ε。若矩陣A滿足

θk+s，n－k－sn－k－s+（s－1）kμ

則

‖x^2－x‖2C1C0‖xT—0c‖1+C2C0ε，

其中，常數C0=1－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n，

C1=2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s，

C2=22［1+（s－1）μ］1－（s－1）μ－θk+s，n－k－sn－k－sk。

證明? 因為x^是式（3）的解，得到

‖（x+h）Tc‖1－α‖（x+h）Tc‖2=‖x^Tc‖1－α‖x^Tc‖2‖xTc‖1－α‖xTc‖2，（6）

由Tc=T0∪T—0c和三角不等式，很容易得到

‖（x+h）Tc‖1－α‖（x+h）Tc‖2=‖（x+h）T0‖1+‖（x+h）T—0c‖1－α‖（x+h）Tc‖2

‖xT0‖1－‖hT0‖1+‖hT—0c‖1－‖xT—0c‖1－α‖xTc‖2－α‖hTc‖2，（7）

結合式（6）和式（7），可以得到

‖hT—0c‖1‖xT—0c‖1+‖hT0‖1－‖xT0‖1+‖xTc‖1－α‖xTc‖2+α‖xTc‖2+α‖hTc‖2

=‖hT0‖1+α‖hTc‖2+2‖xT—0c‖1。 （8）

由于‖hT0‖1‖hT1‖1，‖hT—1c‖1‖hT—0c‖1，‖hTc‖2n－sn‖h‖2，式（8）可轉化為

‖hT—1c‖1‖hT1‖1+2‖xT—0c‖1+αn－sn‖h‖2，（9）

又因為‖hT1—‖0s+k，

‖hT—1c‖

SymboleB@ ‖hT1‖1k‖hT1‖1+αn－sn‖h‖2+2‖xT—0c‖1kk‖hT1‖2+αn－sn‖h‖2+2‖xT—0c‖1k

‖hT1—‖2k+αn－sn‖h‖2+2‖xT—0c‖1k，

故

‖hT—1c‖1（n－k－s）‖hT—1c‖

SymboleB@ （n－k－s）‖hT1—‖2k+2‖xT0—c‖1+αn－sn‖h‖2k。

現應用引理2，其中令k1=k+s，k2=n－k－s，η=‖hT1—‖2k+2‖xT—0c‖1+αn－sn‖h‖2k，得到

〈AhT1—，AhT1—c〉θk+s，n－k－sn－k－s‖hT1—‖2k+2‖xT—0c‖1+αn－sn‖h‖2k‖hT1—‖2，

因此，得到

〈AhT1—，Ah〉‖AhT1—‖22－〈AhT1—，AhT—1c〉

［1－（s－1）μ］‖hT1—‖22－θk+s，n－k－sn－k－s‖hT1—‖2k+2‖xT—0c‖1+αn－sn‖h‖2k‖hT1—‖2。（10）

此外，由于

〈AhT1—，Ah〉‖AhT1—‖2‖Ah‖2［1+（s－1）μ］‖hT1—‖2（‖A－b‖2+‖b－Ax‖2）

2ε［1+（s－1）μ］‖hT1—‖2，（11）

結合式（10）和式（11），得到

［1－（s－1）μ］‖hT1—‖22－θk+s，n－k－sn－k－sk‖hT1—‖22－θk+s，n－k－sα（n－s）（n－k－s）nk2‖h‖2‖hT1—‖2－

2θk+s，n－k－sn－k－sk‖xT0—c‖1‖hT1—‖22ε［1+（s－1）μ］‖hT1—‖2，

整理得：

［1－（s－1）μ－θk+s，n－k－sn－k－sk］‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk2‖h‖2+2θk+s，n－k－sn－k－sk‖xT—0c‖1+2ε［1+（s－1）μ］，

由于條件式（5）保證1－（s－1）μ－θk+s，n－k－sn－k－sk>0成立，所以

‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk‖h‖2+2θk+s，n－k－sn－k－s1－（s－1）μ－θk+s，n－k－sn－k－sk‖xT—0c‖1+

2ε［1－（s－1）μ］1－（s－1）μ－θk+s，n－k－sn－k－sk? 。

因為‖hT1‖1<‖hT1—‖1，則由式（9）可以得到

‖hT—1c‖1‖hT1—‖1+2‖xT—0c‖1+αn－sn‖h‖2。

再應用引理3，其中令l=k+s，γ=αn－sn‖h‖2+2‖xT—0c‖1，

‖hT—1c‖2‖hT1—‖2+2‖xT—0c‖1+αn－sn‖h‖2k+s，（12）

所以

‖h‖2‖hT1—‖22+‖hT—1c‖22

=‖hT1—‖22+‖hT1—‖2+2‖xT—0c‖1+αn－sn‖h‖2k+s2

2‖hT1—‖2+2‖xT—0c‖1+αn－sn‖h‖2k+s

2θk+s，n－k－sα（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk‖h‖2+2θk+s，n－k－sn－k－s1－（s－1）μ－θk+s，n－k－sn－k－sk‖xT—0c‖1+

2ε［1－（s－1）μ］1－（s－1）μ－θk+s，n－k－sn－k－sk+2‖xT—0c‖1+αn－sn‖h‖2k+s，

移項整理得

‖h‖21－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n－1×

2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s‖xT—0c‖1+22ε［1+（s－1）μ］1－（s－1）μ－θk+s，n－k－sn－k－sk。

定理2? 考慮y=Ax+e，其中‖ATe‖

SymboleB@ ε。若矩陣A滿足

θk+s，n－k－sn－k－s+（s－1）kμ

則

‖DS－x‖2C1C0‖xT—0c‖1+C3C0ε，

其中，常數C0=1－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n，

C1=2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s，

C3=22（s+k）1－（s－1）μ－θk+s，n－k－sn－k－sk。

證明? 由于

〈AhT1—，Ah〉=〈hT1—，ATAh〉‖hT1—‖1‖ATAh‖

SymboleB@ =‖hT1—‖1‖ATA（－x）‖

SymboleB@

‖hT1—‖1（‖AT（A－y）‖

SymboleB@ +‖AT（y－Ax）‖

SymboleB@ ）

2ε‖hT1—‖12εs+k‖hT1—‖2，（14）

結合式（10）和式（14），得到

1－（s－1）μ－θk+s，n－k－sn－k－sk‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk2‖h‖2+

2θk+s，n－k－sn－k－sk‖xT—0c‖1+2εs+k，

由于條件式（13）保證1－（s－1）μ－θk+s，n－k－sn－k－sk>0成立，所以

‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk‖h‖2+2θk+s，n－k－sn－k－s1－（s－1）μ－θk+s，n－k－sn－k－sk‖xT—0c‖1+

2εs+k1－（s－1）μ－θk+s，n－k－sn－k－sk。（15）

進一步，由式（12）和式（15），得到

‖h‖22‖hT1—‖2+2‖xT—0c‖1+αn－sn‖h‖2k+s

2θk+s，n－k－sα（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk‖h‖2+2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk‖xT—0c‖1+

2ε2（s+k）1－（s－1）μ－θk+s，n－k－sn－k－sk+2‖xT—0c‖1+αn－sn‖h‖2k+s，

移項整理得

‖h‖21－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n－1×

2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s‖xT—0c‖1+22（s+k）1－（s－1）μ－θk+s，n－k－sn－k－skε。

定理3? 考慮y=Ax+e，其中‖e‖1ε。若矩陣A滿足

θk+s，n－k－sn－k－s+（s－1）kμ

則

‖1－x‖2C1C0‖xT—0c‖1+C4C0ε，

其中常數C0=1－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n，

C1=2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s，

C4=2s+k1－（s－1）μ－θk+s，n－k－sn－k－sk? 。

證明? 由于

〈AhT1—，Ah〉‖AhT1—‖

SymboleB@ ‖Ah‖1‖hT1—‖2s+k‖Ah‖1=‖hT1—‖2s+k‖A（－x）‖1

‖hT1—‖2s+k‖A－y‖1+‖y－Ax‖12εs+k‖hT1—‖2，（17）

結合式（10）和式（17），得到

1－（s－1）μ－θk+s，n－k－sn－k－sk‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk2‖h‖2+

2θk+s，n－k－sn－k－sk‖xT—0c‖1+2εs+k，

由于條件式（16）保證1－（s－1）μ－θk+s，n－k－sn－k－sk>0成立，所以

‖hT1—‖2θk+s，n－k－sα（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk‖h‖2+2θk+s，n－k－sn－k－s1－（s－1）μ－θk+s，n－k－sn－k－sk‖xT—0c‖1+

2εs+k1－（s－1）μ－θk+s，n－k－sn－k－sk 。（18）

進一步，由式（12）和式（18）得

‖h‖21－θk+s，n－k－sα2（n－s）（n－k－s）nk21－（s－1）μ－θk+s，n－k－sn－k－sk－αn－s（k+s）n－1×

2θk+s，n－k－s2（n－k－s）1－（s－1）μ－θk+s，n－k－sn－k－sk+2k+s‖xT—0c‖1+2s+k1－（s－1）μ－θk+s，n－k－sn－k－skε。

注1? 若是式（4）的解，且矩陣A滿足

θk+s，n－k－sn－k－s+（s－1）kμ

則‖－x‖2C1C0‖xT—0c‖1。

注2? Geng和Chen［18］在文獻中使用1－2最小化方法提出了基于相干性的稀疏信號重建條件，證明了如果矩陣A滿足

μ<4k+1－24k+116k2－8k－3，（19）

那么就可以確保通過1－2最小化方法能夠穩定地重建出原始稀疏信號。

圖1中給出了式（5）和式（19）的相干性條件的上界。在實驗中，取n=100，已知支撐s=15，限制正

交常數θk+s，n－k－s=0.4。觀察可知當16k80時，本文得到的條件比Geng和Chen［18］的條件更弱，這意味著會有更多矩陣滿足式（5）。

3? 結? 論

文章使用1－α2最小化方法，在相干性的框架中提出了能夠保證部分支集已知的信號魯棒恢復的充分條件。文章創新之處在于首次在相干性的框架中，提出將1－α2最小化方法和信號的先驗支撐信息結合。由于一個給定矩陣的相干性常數比它的限制等距性常數更容易計算，所以在相干性的框架中討論信號恢復問題更實用且更有效率。

參考文獻：

［1］? CANDES E J，ROMBERG J，TAO T.Decoding by linear programming ［J］.IEEE Transactions on Information Theory，2005，51 （2）：4203-4215.

［2］? CHEN W G，LI Y L.Recovery of signals under the condition on RIC and ROC via prior support information ［J］.Applied and Computational Harmonic Analysis，2019，46（2）：417-430.

［3］? INCE T，NACAROGLU A，WATSUJI N.Nonconvex compressed sensing with partially known signal support ［J］.Signal Processing，2013，93（1）：338-344.

［4］? 劉洋鑠，劉宏宇，葛煥敏.無約束的2，1-分析法重構冗余緊框架下分塊稀疏信號的條件［J］.系統科學與數學，2022，42（3）： 509-527.

［5］? LOU Y F，YAN M.Fast L1－L2 minimization via a proximal operator［J］.Journal of Scientific Computing，2018，74（2）：767-785.

［6］? LIU T，PONG T K.Further properties of the forward-backward envelope with applications to difference-of-convex programing ［J］.Computational Optimization and Applications，2017，67（3）：489-520.

［7］? GE H，CHEN W，NG M K.New rip analysis for 1－2 minimization methods［J］.SIAM Journal on Imaging Sciences，2021，14 （2）：530-557.

［8］? 陳鵬清，黃尉.基于1－2范數的塊稀疏信號重構［J］.應用數學和力學，2017，38（8）：932-942.

［9］? LI P，CHEN W，GE H，et al.1－α2 minimization methods for signal and image reconstruction with impulsive noise removal ［J］.Inverse Problems，2020，36：055009.

［10］GE H M，LI P.The Dantzig selector： recovery of signal via 1－α2 minimization［J］.Inverse Problems，2022，38（1）：015006.

［11］武思琪，宋儒瑛.基于1－2最小化的部分支集已知的信號重建［J］.湖北民族大學學報（自然科學版），2022，40（1）：81-85.

［12］WANG W D，WANG J J.An improved sufficient condition of 1－2 minimisation for robust signal recovery［J］，Electronics Letters，2019，55（22）：1199-1201.

［13］ZHANG J，ZHANG S G，MENG X.1－2minimisation for compressed sensing with partially known signal support［J］.Electron-ics Letters，2020，56（8）：405-408.

［14］武思琪，宋儒瑛.基于1－α2最小化的部分支集已知的信號重建［J］.應用數學進展，2022（8）：6015-6028.

［15］JEFFREY D B，ANDRE T.On support sizes of restricted isometry constants［J］.Applied and Computational Harmonic Analysis，2010，29（3）：382-390.

［16］HUANG J，ZHANG F，LIU X，et al.Stable recovery of sparse signals with non-convex weighted r-Norm minus 1-Norm［EB/OL］.（2022-01-09）［2022-05-10］.http：//www.optimization-online.org/wp-content/uploads/2022/01/8762.pdf.

［17］LI P，CHEN W G.Signal recovery under mutual incoherence property and oracle inequalities［J］.Frontiers of Mathematics in Ch- ina，2019，13（6）：1369-1396.

［18］GENG P B，CHEN W G.Unconstrained 1－2 minimization for sparse recovery via mutual coherenve［J］.Mathematical Fou-ndations of Computing，2020，3（2）：65-79.

［19］CAI T T，WANG L，XU G.Stable recovery of sparse signals and an oracle inequality［J］.IEEE Transactions on Information The-ory，2010，56（7）：3516-3522.

［20］CAI T T，WANG L，XU G.Shifting inequality and recovery of sparse signals ［J］.IEEE Transactions on Signal Processing：A Publication of the IEEE Signal Processing Society，2010，58（3）：1300-1308.

Signal Reconstruction with Known Partial SupportBased on Coherence Framework

WU Si-qi，SONG Ru-ying，GUAN Jin-rui

（School of Mathematics and Statistics，Taiyuan Normal University，Jinzhong Shanxi 030619，China）

Abstract：In this paper，1－α 2（0<α1） minimization model is employed to reconstruct the high-dimensional sparse signals by the prior support information of the signal itself.It is the first paper on signal reconstruction with known partial support that is based on coherence framework.It focuses on the sufficient conditions and error estimation for robust signal recovery under three kinds of noise circumstance，including 2 bounded noise，Dantzig Selector noise and impulse noise.

Keywords：compressed sensing；known partial support；1－α2 minimization；coherence；error estimation