鄭巖 李健

摘要：為了提高壓縮感知中隨機濾波器采樣信號的重構(gòu)性能，該文采用L1最小化重構(gòu)算法對壓縮信號進行重構(gòu)。通過數(shù)值試驗表明，對于隨機濾波器采樣的信號，L1最小化重構(gòu)算法的重構(gòu)效果優(yōu)于正交匹配追蹤算法的重構(gòu)效果。

關(guān)鍵詞：隨機濾波器；L1最小化算法；正交匹配追蹤算法

中圖分類號：TN911.7 文獻標識碼：A 文章編號：1009-3044（2014）35-8584-02

The Research of Reconstruction Algorithm for Compressive Signals from Random Filters

ZHENG Yan， LI Jian

（College of Electronics and Info. Eng. ， Sichuan Univ. ，Chengdu 610065， China）

Abstract： To improve the reconstruction performance of compressive signals from random filters，L1 minimization algorithms is used. The numerical experiments show reconstruction performance of L1 minimization algorithms outperforms reconstruction performance of orthogonal matching pursuit algorithms.

Key words： random filters； L1 minimization algorithms； orthogonal matching pursuit algorithms

隨機濾波器是由Joel A.Tropp， Michael B.Wakin等人提出，它是通過原始的稀疏信號或可壓縮信號與有隨機抽頭的FIR濾波器進行卷積，然后降采樣來獲得測量值[1]。這種壓縮采樣信號的方法有如下好處：1） 測量值是是不變的和非自適應的；2） 可以用更長的濾波器來換取更少的測量值；3） 在硬件和軟件上，此種方法是很容易被實現(xiàn)。常見的恢復算法有凸優(yōu)化算法和貪婪算法。該文采用凸優(yōu)化算法中的最小化L1算法[2]來重構(gòu)隨機濾波器采樣的信號。

1 正交匹配追蹤算法和最小化L1算法

正交匹配追蹤算法（OMP）[3]通過測量值y和矩陣[AΨ]的列之間的關(guān)聯(lián)性求解原始信號x的近似值。以下算法詳細描述了OMP恢復算法的過程。

算法：OMP恢復算法

輸入：1） [N×d] 的測量矩陣A；

2） 長度為N的壓縮數(shù)據(jù)y；

3） 原始信號x的稀疏級m；

算法：

1） 設(shè)置殘差[r0=y] ，迭代次數(shù)t=1；

2） 找到恢復矩陣[Θ=AΨ]的[it]列：

[it=argmaxirt-1，Θi， t=1，2，…，m] （1）

3） 構(gòu)造增量矩陣：

[Θt=Θt-1θit] （2）

其中[Θ0]是一個空矩陣。

4） 構(gòu)造索引集合[Λt]：

[Λt=Λt-1?it] （3）

其中[Λ0=?]。

5）計算

[xt=argminxy-Θtx2] （4）

以得到一個新的信號估計值。

6） 更新殘差

[rt=y-Θtxt] （5）

7） t=t+1，如果[t≤m]，返回到第三步。

輸出：

估計值[x]，[x]中非零元素所在的位置在列表[Λm]中，[x]在位置[ij]的值等于[xt]的第[j]個元素。

L1最小化算法是采用線性規(guī)劃來解決問題：

[minx∈Rdx?1 subject to y=Ax ] （6）

其中[x?1=i=1dxi ]。

2 仿真與分析

2.1 使用L1最小化算法對壓縮信號進行確切重建

假設(shè)信號長度d為128，濾波器長度B為128，測量值N為60，稀疏級m為14，圖1顯示了使用L1算法對壓縮信號的確切重建。

2.2 稀疏級與確切恢復率之間的關(guān)系

當信號長度d為128，濾波器長度B為128，測量值N為60，稀疏級m從1到18變化時，用OMP和L1最小化恢復算法分別對壓縮信號進行恢復，可以得出稀疏級m與確切恢復率p之間的關(guān)系如圖2所示。從圖2中可以得出當稀疏級m大于13時，L1最小化恢復算法的恢復效果要優(yōu)于OMP算法的恢復效果。

2.3 濾波器長度與確切恢復率之間的關(guān)系

當信號長度d為128，測量值N為60，稀疏級m為10，濾波器的長度B從10到80變化時，用OMP和L1最小化恢復算法分別對壓縮信號進行恢復，可以得出濾波器長度B與確切恢復率p之間的關(guān)系如圖3所示。從圖3中可以得出隨著濾波器長度的增加，L1最小化恢復算法的恢復效果總要優(yōu)于OMP算法的恢復效果。

2.4 測量值與確切恢復率之間的關(guān)系

當信號長度d為128，濾波器長度B為128，稀疏級m為10，測量值N從10到60變化時，用OMP和L1最小化恢復算法分別對壓縮信號進行恢復，可以得出測量值N與確切恢復率p之間的關(guān)系如圖4所示。從圖4中可以得出隨著測量值數(shù)目的增加，L1最小化恢復算法的恢復效果總要優(yōu)于OMP算法的恢復效果。

3 總結(jié)

對于隨機濾波器壓縮的信號，L1最小化算法能夠確切恢復原始信號。當信號長度，濾波器長度和測量值一定時，隨著稀疏級變大，L1最小化算法的恢復效果優(yōu)于OMP算法的恢復效果；當信號長度，稀疏級和測量值一定時，隨著濾波器長度的變大，L1最小化算法的恢復效果優(yōu)于OMP算法的恢復效果；當信號長度，濾波器長度和稀疏級一定時，隨著測量值數(shù)目的變多，L1最小化算法的恢復效果優(yōu)于OMP算法的恢復效果。由此可見，L1最小化算法的恢復效果要優(yōu)于OMP算法的恢復效果。

參考文獻：

[1] Tropp J A，Wakin M B，Duarte， M.F.，et al.Random filters for compressive sampling and reconstruction[C].2006 IEEE International Conference on Acoustics， Speech， and Signal Processing， IEEE， Piscataway， NJ， USA，2006， III-872-5.

[2] Kwangmo Koh， Seung-Jean Kim，Stephen P. Boyd.An Interior-Point Method for Large-Scale 1-Regularized Logistic Regression[J].Journal of Machine Research，2007，8：.

[3] Joel A. Tropp， Anna C. Gilbert.Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory， 2007， Vol.53

[4] David L. Donoho. Compressed sensing.[J].IEEE Transactions on Information Theory，2006，52：1289-1306.

[5] Emmanuel J. Candès，Justin K. Romberg，Terence Tao. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information.[J]. IEEE Transactions on Information Theory，2006，52：489-509.

[6] Gitta Kutyniok. Compressed Sensing： Theory and Applications[J].CoRR，2012，abs/1203.3：.