壓縮感知理論與應(yīng)用(附重建算法詳述)

1、壓縮感知理論與應(yīng)用壓縮感知理論與應(yīng)用Compressed sensing: theorem and Applications一一. .壓縮感知背景知識(shí)壓縮感知背景知識(shí)二二. .壓縮感知理論壓縮感知理論三三. .壓縮感知重建方法壓縮感知重建方法四四. .壓縮感知應(yīng)用壓縮感知應(yīng)用內(nèi)容概覽內(nèi)容概覽一一. . 壓縮感知背景知識(shí)壓縮感知背景知識(shí)Nyquist-ShannonNyquist-Shannon采樣定理采樣定理1928年由美國(guó)電信工程師年由美國(guó)電信工程師H.奈奎斯特首先提出奈奎斯特首先提出1933年由蘇聯(lián)工程師科捷利尼科夫首次用公式嚴(yán)年由蘇聯(lián)工程師科捷利尼科夫首次用公式嚴(yán) 格地表述這一定理格地表

2、述這一定理1949 年信息論的創(chuàng)始人香農(nóng)對(duì)該定理加以明確年信息論的創(chuàng)始人香農(nóng)對(duì)該定理加以明確 地說(shuō)明并正式作為定理引用，因此在許多文地說(shuō)明并正式作為定理引用，因此在許多文 獻(xiàn)中又稱(chēng)為香農(nóng)采樣定理獻(xiàn)中又稱(chēng)為香農(nóng)采樣定理Harry Nyquist Claude Shannon 插值重建插值重建數(shù)字信號(hào)的獲取數(shù)字信號(hào)的獲取-Nyquist-Shannon-Nyquist-Shannon采樣定理采樣定理信號(hào)采樣信號(hào)采樣非帶限信號(hào)非帶限信號(hào)香農(nóng)定理的數(shù)學(xué)表示香農(nóng)定理的數(shù)學(xué)表示香農(nóng)采樣定理后采樣理論的發(fā)展香農(nóng)采樣定理后采樣理論的發(fā)展Nyquist-Nyquist-Shannon采樣定理局限性采樣定理局限性

3、問(wèn)題問(wèn)題1:真實(shí)信號(hào)沒(méi)有真正帶限的；真實(shí)信號(hào)沒(méi)有真正帶限的；問(wèn)題問(wèn)題2:理想的低通濾波器不存在；理想的低通濾波器不存在；獲取的大量數(shù)字信號(hào)為處理、存儲(chǔ)、傳輸?shù)能浻布黾恿撕塬@取的大量數(shù)字信號(hào)為處理、存儲(chǔ)、傳輸?shù)能浻布黾恿撕芏嘭?fù)擔(dān)多負(fù)擔(dān)高分辨率高分辨率大量的傳感器大量的傳感器圖像數(shù)據(jù)庫(kù)，照相陣列，分布式無(wú)線傳感網(wǎng)圖像數(shù)據(jù)庫(kù)，照相陣列，分布式無(wú)線傳感網(wǎng)越來(lái)越多的成像形式越來(lái)越多的成像形式X-Ray，Gamma Ray, PET，MRI, 紅外，超聲波，毫米波紅外，超聲波，毫米波SAR 成像成像海量的數(shù)據(jù)海量的數(shù)據(jù)問(wèn)題問(wèn)題3: 當(dāng)信號(hào)的帶寬過(guò)寬時(shí)，采樣率過(guò)高難于實(shí)現(xiàn)當(dāng)信號(hào)的帶寬過(guò)寬時(shí)，采樣率過(guò)高難

4、于實(shí)現(xiàn) 限制了超寬帶通信和超寬帶雷達(dá)的發(fā)展；限制醫(yī)學(xué)圖限制了超寬帶通信和超寬帶雷達(dá)的發(fā)展；限制醫(yī)學(xué)圖像成像的發(fā)展，比如像成像的發(fā)展，比如MRI；等等。；等等。多種成像形式多種成像形式采樣采樣壓縮壓縮傳輸傳輸/存儲(chǔ)存儲(chǔ)NKx小波系數(shù)小波系數(shù)局部放大局部放大大量采樣數(shù)據(jù)有無(wú)必要性？大量采樣數(shù)據(jù)有無(wú)必要性？1M 25K 項(xiàng)系數(shù)近似項(xiàng)系數(shù)近似原始圖像原始圖像 近似后的圖像近似后的圖像20042006， E Candes（加州理工大學(xué)）加州理工大學(xué)） D.Donoho (斯坦福大學(xué)斯坦福大學(xué)) （ Ridgelet和Curvelet的創(chuàng)始人） 一種新的采樣方法一種新的采樣方法 以不確定準(zhǔn)則為基礎(chǔ)以不確定

5、準(zhǔn)則為基礎(chǔ)Romberg (佐治亞理工大學(xué)佐治亞理工大學(xué)) Tao （加州大學(xué)洛杉磯分校）加州大學(xué)洛杉磯分校）CS提出者提出者用更一般的測(cè)量值代替信號(hào)樣本值用更一般的測(cè)量值代替信號(hào)樣本值壓縮感知或壓縮采樣壓縮感知或壓縮采樣直接獲取壓縮后的信號(hào)；直接獲取壓縮后的信號(hào)；壓縮壓縮采樣采樣傳輸傳輸/存儲(chǔ)存儲(chǔ)NxMy接收接收 重建重建y二二. . 壓縮感知理論壓縮感知理論2.1 壓縮感知問(wèn)題描述壓縮感知問(wèn)題描述假假設(shè)設(shè) x 是是一一離離散散時(shí)時(shí)間間信信號(hào)號(hào)：NxR，這這樣樣壓壓縮縮感感知知問(wèn)問(wèn)題題簡(jiǎn)簡(jiǎn)化化為為是是否否存存在在一一組組測(cè)測(cè)量量信信號(hào)號(hào)MyR能能完完全全恢恢復(fù)復(fù)出出 x ，其其中中 MN 。

6、設(shè)設(shè) y 的的每每個(gè)個(gè)分分量量ky 是是x與與一一組組測(cè)測(cè)量量矢矢量量,1NkRkM 的的內(nèi)內(nèi)積積，即即：,kkyx，1kM ，測(cè)測(cè)量量矩矩陣陣 的的行行向向量量為為k， 的的大大小小為為MN，則則測(cè)測(cè)量量信信號(hào)號(hào)y 可可以以寫(xiě)寫(xiě)為為 yx （2.1.1） 問(wèn)問(wèn)題題為為： 是是否否存存在在一一種種測(cè)測(cè)量量， 能能使使原原始始信信號(hào)號(hào)NxR由由測(cè)測(cè)量量信信號(hào)號(hào)MyR恢恢復(fù)復(fù)，這這里里MN。可可以以看看出出，式式（2 2. .1 1. .1 1）是是一一個(gè)個(gè)欠欠定定方方程程，存存在在無(wú)無(wú)窮窮多多組組解解。要要想想唯唯一一恢恢復(fù)復(fù) x ，信信號(hào)號(hào) x 和和矩矩陣陣 還還需需要要滿(mǎn)滿(mǎn)足足什什么么條條件

7、件。 三種線性方程組三種線性方程組 根據(jù)變量個(gè)數(shù)和方程個(gè)數(shù)來(lái)確定是根據(jù)變量個(gè)數(shù)和方程個(gè)數(shù)來(lái)確定是欠定、適定欠定、適定還是還是超定超定方程組方程組MN欠定方程組，無(wú)窮多解欠定方程組，無(wú)窮多解MN適定方程組，有唯一解適定方程組，有唯一解MN超定方程組，無(wú)解超定方程組，無(wú)解良態(tài)問(wèn)題良態(tài)問(wèn)題1923年年Hadamard提出了良態(tài)問(wèn)題（提出了良態(tài)問(wèn)題（Well-posed problem）的）的概念，根據(jù)其定義，如果下述條件滿(mǎn)足，稱(chēng)為良態(tài)問(wèn)題概念，根據(jù)其定義，如果下述條件滿(mǎn)足，稱(chēng)為良態(tài)問(wèn)題（1）方程的解是存在的；）方程的解是存在的；（2）解是唯一的；）解是唯一的；（3）解連續(xù)地依賴(lài)于數(shù)據(jù)（觀測(cè)矩陣或數(shù)據(jù)

8、微小變化導(dǎo)致解很大）解連續(xù)地依賴(lài)于數(shù)據(jù)（觀測(cè)矩陣或數(shù)據(jù)微小變化導(dǎo)致解很大變動(dòng)）變動(dòng)）病態(tài)問(wèn)題病態(tài)問(wèn)題 如果良態(tài)問(wèn)題的三個(gè)條件任意一個(gè)不能滿(mǎn)足，如果良態(tài)問(wèn)題的三個(gè)條件任意一個(gè)不能滿(mǎn)足，就稱(chēng)問(wèn)題是病態(tài)的（就稱(chēng)問(wèn)題是病態(tài)的（ill-posed problem） 良態(tài)與病態(tài)問(wèn)題：良態(tài)與病態(tài)問(wèn)題：1212400201200800401200 xxxx12100200 xx 1212401201200800401200 xxxx124000079800 xx病態(tài)問(wèn)題舉例病態(tài)問(wèn)題舉例系數(shù)矩陣系數(shù)矩陣A或者觀測(cè)項(xiàng)或者觀測(cè)項(xiàng)(常數(shù)項(xiàng)常數(shù)項(xiàng))y的微小變化引起解的的微小變化引起解的巨大變化巨大變化,該問(wèn)題為病態(tài)問(wèn)題

9、該問(wèn)題為病態(tài)問(wèn)題 病態(tài)問(wèn)題求解：病態(tài)問(wèn)題求解：用規(guī)整化（用規(guī)整化（Regularization）理論）理論處理病態(tài)問(wèn)題處理病態(tài)問(wèn)題目的目的是修改一個(gè)病態(tài)問(wèn)題為一個(gè)良態(tài)問(wèn)題，使得問(wèn)是修改一個(gè)病態(tài)問(wèn)題為一個(gè)良態(tài)問(wèn)題，使得問(wèn)題的解在物理上合理，并且解連續(xù)依賴(lài)于數(shù)據(jù)。題的解在物理上合理，并且解連續(xù)依賴(lài)于數(shù)據(jù)。基本思想基本思想是利用關(guān)于解的先驗(yàn)知識(shí)，構(gòu)造附加約束或改是利用關(guān)于解的先驗(yàn)知識(shí)，構(gòu)造附加約束或改變求解策略，使得逆問(wèn)題的解變得確定且穩(wěn)定。即對(duì)解變求解策略，使得逆問(wèn)題的解變得確定且穩(wěn)定。即對(duì)解進(jìn)行約束進(jìn)行約束J(x)約束信號(hào)約束信號(hào)x為平滑的為平滑的應(yīng)用應(yīng)用Lagrange乘子，將乘子，將P2問(wèn)題

10、約束轉(zhuǎn)換為無(wú)約束問(wèn)題約束轉(zhuǎn)換為無(wú)約束問(wèn)題問(wèn)題 2. 如何設(shè)計(jì)測(cè)量矩陣，讓其作用于信號(hào)后如何設(shè)計(jì)測(cè)量矩陣，讓其作用于信號(hào)后 能保持信號(hào)的所有信息不丟失？能保持信號(hào)的所有信息不丟失？ （對(duì)應(yīng)于香農(nóng)采樣定理中對(duì)采樣率的要求）（對(duì)應(yīng)于香農(nóng)采樣定理中對(duì)采樣率的要求）3. 如何從測(cè)量中重建原信號(hào)？如何從測(cè)量中重建原信號(hào)？ （對(duì)應(yīng)依據(jù)香農(nóng)采樣定理采樣后內(nèi)插實(shí)現(xiàn)重建）（對(duì)應(yīng)依據(jù)香農(nóng)采樣定理采樣后內(nèi)插實(shí)現(xiàn)重建）信號(hào)應(yīng)滿(mǎn)足什么要求，方可重建？信號(hào)應(yīng)滿(mǎn)足什么要求，方可重建？ （對(duì)應(yīng)香農(nóng)采樣定理中對(duì)信號(hào)的帶寬要求）（對(duì)應(yīng)香農(nóng)采樣定理中對(duì)信號(hào)的帶寬要求） CS關(guān)注的問(wèn)題關(guān)注的問(wèn)題 信號(hào)表示信號(hào)表示將信號(hào)表示為一組正交基

11、的線性組合將信號(hào)表示為一組正交基的線性組合 如果合理選擇基底，處理系數(shù)序列比直接處理信號(hào)簡(jiǎn)單；如果合理選擇基底，處理系數(shù)序列比直接處理信號(hào)簡(jiǎn)單； 如果系數(shù)序列如果系數(shù)序列 具有稀疏結(jié)構(gòu)，可以從實(shí)質(zhì)上降低信號(hào)具有稀疏結(jié)構(gòu)，可以從實(shí)質(zhì)上降低信號(hào)處理的成本，提高壓縮效率。處理的成本，提高壓縮效率。 二二. . 壓縮采樣理論壓縮采樣理論2.2 信號(hào)的稀疏與可壓縮性信號(hào)的稀疏與可壓縮性信號(hào)的稀疏（信號(hào)的稀疏（Sparsity）與可壓縮性）與可壓縮性( (Compressibility) )設(shè)設(shè),1iiN 為為一組標(biāo)準(zhǔn)正交基，由這組基張成的空間為一組標(biāo)準(zhǔn)正交基，由這組基張成的空間為NR，設(shè)信號(hào)設(shè)信號(hào)NxR

12、，1Niiix，或用矩陣表示，或用矩陣表示x ， （， （的列為的列為i，是是元素為元素為i的列的列向向量） 。量） 。 x ， 其中其中,iix 如果矢量如果矢量的大多數(shù)元素都為的大多數(shù)元素都為 0，稱(chēng)，稱(chēng) x 為為域稀疏的。將其不為域稀疏的。將其不為零的個(gè)數(shù)記為零的個(gè)數(shù)記為 S，0S，稱(chēng)，稱(chēng) x 為為 S-稀疏。稀疏。如果如果矢量矢量的元素按幅值的元素按幅值大小排列，其幅度衰減很快，大小排列，其幅度衰減很快，具有冪次速度（具有冪次速度（Power law）衰減趨勢(shì)。）衰減趨勢(shì)。則稱(chēng)信號(hào)則稱(chēng)信號(hào) x 為為域可壓縮的域可壓縮的(Compressible)。 光滑信號(hào)光滑信號(hào)其其Fourier變

13、換變換,Wavelet,Wavelet變換系數(shù)呈現(xiàn)冪次衰減變換系數(shù)呈現(xiàn)冪次衰減趨勢(shì)趨勢(shì)其全變差（其全變差（Total Variation）呈現(xiàn)冪次衰減趨勢(shì)）呈現(xiàn)冪次衰減趨勢(shì)有界變差函數(shù)有界變差函數(shù) 給定一個(gè)定義于有界開(kāi)集給定一個(gè)定義于有界開(kāi)集上的可微函數(shù)上的可微函數(shù) f，其全變，其全變差（差（the total variation） 為為對(duì)于圖像對(duì)于圖像x而言，其而言，其TV范數(shù)為范數(shù)為Cameraman 原圖4層小波分解傅里葉幅頻MRI圖像圖像4層小波分解傅里葉幅頻原圖原圖垂直垂直水平水平全變差全變差 根據(jù)信號(hào)根據(jù)信號(hào) x x 的先驗(yàn)知識(shí)的先驗(yàn)知識(shí)，可以設(shè)計(jì)規(guī)整可以設(shè)計(jì)規(guī)整化項(xiàng)為化項(xiàng)為 R2

14、空間，一維子空間用空間，一維子空間用lp范數(shù)進(jìn)行約束的解范數(shù)進(jìn)行約束的解2.3.1不確定原理（測(cè)不準(zhǔn)原理不確定原理（測(cè)不準(zhǔn)原理 Uncertainty Principle, UP）物理學(xué)中經(jīng)典的測(cè)不準(zhǔn)原理物理學(xué)中經(jīng)典的測(cè)不準(zhǔn)原理兩個(gè)共軛的物理量，如微觀粒子的位置和動(dòng)量，不能同時(shí)兩個(gè)共軛的物理量，如微觀粒子的位置和動(dòng)量，不能同時(shí)測(cè)準(zhǔn)，測(cè)準(zhǔn)，其中一個(gè)量越確定，另一個(gè)量的不確定程度就越大其中一個(gè)量越確定，另一個(gè)量的不確定程度就越大 2.3 測(cè)量測(cè)量離散時(shí)間不確定準(zhǔn)則離散時(shí)間不確定準(zhǔn)則（Discrete Time Uncertainty Principle）令令( )x t是是長(zhǎng)長(zhǎng)度度為為N的的離離散

15、散序序列列，0 1 , ,tN， 其其離離散散F Fo ou ur ri ie er r 變變換換為為 x，0 1 , ,N，tN ，N分分別別為為 ( )x t 和和 x中中不不為為零零元元素素的的個(gè)個(gè)數(shù)數(shù)，則則 2ttN NNNNN 或或者者將將記記:supTp x，:sup p x；TN ； 2TN 注：集的勢(shì)：集合元素的個(gè)數(shù)注：集的勢(shì)：集合元素的個(gè)數(shù)05010015000.10.20.30.40.50.60.70.80.9105010015000.10.20.30.40.50.60.70.80.91 10 110,tm NmNx t其他 其其F Fo ou ur ri ie er r變

16、變換換 x與與x完完全全一一樣樣。 xx ； 此此時(shí)時(shí)2tNNN， 或或者者說(shuō)說(shuō)2TN 如如果果信信號(hào)號(hào)的的長(zhǎng)長(zhǎng)度度N為為質(zhì)質(zhì)數(shù)數(shù)， 排排除除了了上上述述Dirac Comb的的情情況況， 則則離離散散不不確確定定準(zhǔn)準(zhǔn)則則為為 tNNN x x t2.3.2 部分部分Fourier變換已知的信號(hào)重建與變換已知的信號(hào)重建與 Robust Uncertainty PrinciplesCS提出的最初研究：提出的最初研究：2004年，年，Emmanuel Candes, Justin Romberg和和Terence Tao 對(duì)以下問(wèn)題進(jìn)行了研究對(duì)以下問(wèn)題進(jìn)行了研究離離散散時(shí)時(shí)間間信信號(hào)號(hào)NxC， 其

17、其離離散散 Fourier 變變換換 :NNFxx CC，如如果果已已知知 x 的的 N 點(diǎn)點(diǎn) Fourier 系系數(shù)數(shù) ,Nx kkZ，可可以以通通過(guò)過(guò) Fourier反反變變換換完完全全恢恢復(fù)復(fù)出出x。 問(wèn)問(wèn)題題： 如如果果只只是是已已知知部部分分的的 Fourier 系系數(shù)數(shù) ,x kk ， 其其中中為為NZ 的的子子集集，NZ ，N ，是是否否可可以以恢恢復(fù)復(fù)出出原原信信號(hào)號(hào)？ 注注：集集的的勢(shì)勢(shì)：集集合合元元素素的的個(gè)個(gè)數(shù)數(shù) MRI圖像圖像Fourier 采樣，采樣，22線線Fourier幅度幅度定定理理 2.1：假假設(shè)設(shè)信信號(hào)號(hào)x的的長(zhǎng)長(zhǎng)度度 N，且且 N 為為質(zhì)質(zhì)數(shù)數(shù)，x的的支支

18、撐撐集集為為T(mén) ，T 為為0 11, ,N 的的子子集集，若若令令其其傅傅里里葉葉變變換換 x 的的支支撐撐集集也也為為0 11, ,N 的的子子集集，如如果果 滿(mǎn)滿(mǎn)足足： 12T 則則x可可以以從從和和 x唯唯一一恢恢復(fù)復(fù)。反反之之，當(dāng)當(dāng)N 時(shí)時(shí)，存存在在兩兩個(gè)個(gè)不不同同的的信信號(hào)號(hào)1x 和和2x ，1T和和2112T ，并并且且12xx。 定定理理 2.2：NxC是是離離散散信信號(hào)號(hào)，其其支支撐撐集集為為未未知知集集NTZ，在在所所有有M 的的集集合合中中，隨隨機(jī)機(jī)選選擇擇一一個(gè)個(gè)頻頻率率集集合合，對(duì)對(duì)于于給給定定的的精精確確度度參參數(shù)數(shù) m，如如果果 1mTCN(log)， 其其中中常常

19、數(shù)數(shù)0mC ，能能以以至至少少1mO N()的的概概率率，從從求求解解下下式式 10min . . Nng ns tg kx kfor all k 得得到到的的解解是是唯唯一一的的，且且等等于于x。 對(duì)對(duì)于于,20,24NNm ，有有1231mCm M=logN.S以往的：以往的：2TN (1)(1) 如果如果 N N 為質(zhì)數(shù)，則有為質(zhì)數(shù)，則有TN （2） 有有NZ的兩個(gè)子集的兩個(gè)子集T和和， 討論， 討論T 應(yīng)為多大才可能構(gòu)造出一個(gè)信應(yīng)為多大才可能構(gòu)造出一個(gè)信號(hào)使得其時(shí)域和頻域的支撐分別為號(hào)使得其時(shí)域和頻域的支撐分別為T(mén)和和。 由于由于 Dirac Comb 代表的是特例，當(dāng)其幅值不為代表的

20、是特例，當(dāng)其幅值不為 1 時(shí)，則時(shí)，則 x在在 N 點(diǎn)均點(diǎn)均不為不為 0；對(duì)多數(shù)信號(hào)而言，；對(duì)多數(shù)信號(hào)而言，(2)比（比（1）更接近實(shí)際情況；如果隨機(jī)選擇一）更接近實(shí)際情況；如果隨機(jī)選擇一對(duì)對(duì)( ,)T ，如果，如果 1 logNTN （RUPRUP） （3 3） 定理與定理與UP的關(guān)系，以及的關(guān)系，以及RUP （Robust Uncertainty Principle）是是預(yù)預(yù)先先確確定定的的數(shù)數(shù)， 則則能能以以超超過(guò)過(guò)1()O N的的概概率率找找到到一一個(gè)個(gè)信信號(hào)號(hào)其其時(shí)時(shí)域域和和頻頻域域的的支支撐撐分分別別為為T(mén) 和和。 2.3.3 隨機(jī)采樣與重建隨機(jī)采樣與重建 定義定義2.1 2.1

21、互相干互相干 互 定理定理2.32.3 幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明：2. 信號(hào)表示越稀疏信號(hào)表示越稀疏、兩組基之間的互相干性越小，所需兩組基之間的互相干性越小，所需 要的樣本數(shù)就越少要的樣本數(shù)就越少3. 常用的測(cè)量矩陣有高斯和伯努利分布，因?yàn)槠渑c常用的測(cè)量矩陣有高斯和伯努利分布，因?yàn)槠渑c 大多數(shù)的稀疏表示基相干性小。大多數(shù)的稀疏表示基相干性小。測(cè)量結(jié)果測(cè)量結(jié)果稀疏信號(hào)稀疏信號(hào)x x隨機(jī)投影隨機(jī)投影（測(cè)量）矩陣（測(cè)量）矩陣壓縮采樣的情況壓縮采樣的情況1: 信號(hào)本身稀疏信號(hào)本身稀疏 信號(hào)是時(shí)域稀疏的，頻域測(cè)量結(jié)果含有信號(hào)的所有信息信號(hào)是時(shí)域稀疏的，頻域測(cè)量結(jié)果含有信號(hào)的所有信息；信號(hào)信號(hào)測(cè)量測(cè)量010203

22、04050607080901000123456789signal x05101520253035404550-1-0.8-0.6-0.4-0.200.20.40.60.8measurement result y原信號(hào)原信號(hào)xx*xM=50；S=19；N=100重建信號(hào)重建信號(hào)x時(shí)域信號(hào)時(shí)域信號(hào)頻域頻域1-維信號(hào)維信號(hào)信號(hào)是頻域稀疏的，時(shí)域測(cè)量結(jié)果信號(hào)是頻域稀疏的，時(shí)域測(cè)量結(jié)果；壓縮采樣的情況壓縮采樣的情況2信號(hào)可以用一組基稀疏表示信號(hào)可以用一組基稀疏表示2-維圖像信號(hào)維圖像信號(hào)2.3.4 一致不確定準(zhǔn)則一致不確定準(zhǔn)則（Uniform Uncertainty Principle, UUP） 22

23、22221322MMxxxNN 假設(shè)假設(shè)為為 FourierFourier 變換，變換，為為隨機(jī)隨機(jī)抽取抽取行行，上上式說(shuō)明，式說(shuō)明，2lx至多為至多為232lMxN由于由于22nlZlxx， 可以看到， 時(shí)域稀疏的信號(hào)， 可以看到， 時(shí)域稀疏的信號(hào)x將將在頻域內(nèi)平鋪，而不是集中在在頻域內(nèi)平鋪，而不是集中在內(nèi)。除非內(nèi)。除非 M 選得接近選得接近 N，即測(cè)，即測(cè)量點(diǎn)數(shù)量點(diǎn)數(shù)要足夠要足夠多。多。 對(duì)對(duì) G Ga au us ss si ia an n 和和 B Bi in na ar ry y 矩矩陣陣，是是以以log N，而而傅傅立立葉葉矩矩陣陣以以6log N滿(mǎn)滿(mǎn)足足 U UU UP P； 嚴(yán)

24、格重建準(zhǔn)則（嚴(yán)格重建準(zhǔn)則（Exact Reconstruction Principle, ERP）稱(chēng)測(cè)量矩陣稱(chēng)測(cè)量矩陣以過(guò)采樣因子以過(guò)采樣因子服從服從 ERPERP，如果對(duì)足夠小的，如果對(duì)足夠小的 a0 和固定和固定的正參數(shù)的正參數(shù)0，對(duì)于每個(gè)滿(mǎn)足，對(duì)于每個(gè)滿(mǎn)足MTa的 T，定義在定義在 T 上的每個(gè)符上的每個(gè)符號(hào)向量號(hào)向量 1t，以，以1()aO N的概率存在具有下述性質(zhì)的向量的概率存在具有下述性質(zhì)的向量NPR， （， （i） P tt 對(duì)所有對(duì)所有tT (ii) P 是是行向量的線性組合行向量的線性組合 （iiiiii） 12P t ，對(duì)所有，對(duì)所有01:,CtTNT 定定義義 2.2：可

25、可壓壓縮縮信信號(hào)號(hào)：設(shè)設(shè),1iiN 為為一一組組標(biāo)標(biāo)準(zhǔn)準(zhǔn)正正交交基基，由由這這組組基基張張成成的的空空間間為為NR ，設(shè)設(shè)信信號(hào)號(hào)NxR，1Niiix，將將這這些些系系數(shù)數(shù)的的絕絕對(duì)對(duì)值值按按降降序序重重新新排排列列 12N 對(duì)對(duì)于于0p , 如如果果對(duì)對(duì)于于每每個(gè)個(gè)1nN，有有 1pnR n 則則稱(chēng)稱(chēng)屬屬于于半半徑徑為為 R 弱弱-lp 球球，或或者者將將 x 記記為為 pxwlR，換換句句話話說(shuō)說(shuō)，p 控控制制衰衰減減的的速速度度，其其值值越越小小，則則衰衰減減越越快快。 可壓縮信號(hào)（近似稀疏信號(hào)）的重建可壓縮信號(hào)（近似稀疏信號(hào)）的重建定理定理 1 1.4.4： 令令分別以分別以1滿(mǎn)足滿(mǎn)足

26、 UUPUUP，以，以2滿(mǎn)足滿(mǎn)足 ERPERP，令，令12max, ，假，假設(shè)設(shè)M，如果信號(hào)，如果信號(hào)NxR，且對(duì)，且對(duì)01p，有，有 1pnR n，或者或者1p 時(shí)，時(shí)，1xR，令，令112rp，則對(duì)任意足夠小的，則對(duì)任意足夠小的a，P1問(wèn)題問(wèn)題的的解解*x至少以概率至少以概率1()aO N滿(mǎn)足滿(mǎn)足 2rp aMxxCR*, 對(duì)對(duì) GaussianGaussian 和和 Binary Binary 矩陣， 是以矩陣， 是以logN滿(mǎn)足滿(mǎn)足 UUPUUP 和和 ERPERP；而而FourierFourier矩陣以矩陣以6log N滿(mǎn)足滿(mǎn)足UUPUUP， 以， 以log N滿(mǎn)足滿(mǎn)足ERPERP，

27、因此，定理因此，定理 2 2.4.4 對(duì)對(duì) GuassianGuassian 和和 BinaryBinary 矩陣而言矩陣而言 2rp aMxxCRN*,log 1min,.styx （P1） 定理定理2.42.42 2. .3.53.5 等距常數(shù)等距常數(shù) Isometry ConstantS、約束約束等距等距性質(zhì)性質(zhì)（Restricted Isometry Property, RIP） 、） 、S,S-約束約束正交常數(shù)正交常數(shù),S S 定定義義2.3： 對(duì)對(duì)每每個(gè)個(gè)整整數(shù)數(shù)1 2, ,S ， 定定義義矩矩陣陣的的約約束束等等距距常常數(shù)數(shù)S為為對(duì)對(duì)于于所所有有S 稀稀疏疏的的矢矢量量x，式式（

28、2.7.1）成成立立的的最最小小常常數(shù)數(shù)， 22222211STSxxx （2.7.1） 如如果果S不不接接近近于于，稱(chēng)稱(chēng)矩矩陣陣滿(mǎn)滿(mǎn)足足 S S- - -階階的的 R RI IP P。 或或者者抽抽取取矩矩陣陣的的列列向向量量構(gòu)構(gòu)成成矩矩陣陣T ，1,TN是是MT維維矩矩陣陣，對(duì)對(duì)于于每每個(gè)個(gè)整整數(shù)數(shù)S，定定義義矩矩陣陣的的約約束束等等距距常常數(shù)數(shù)S為為滿(mǎn)滿(mǎn)足足下下式式的的最最小小的的常常數(shù)數(shù)： 22222211STSccc （2.7.2） 保證信號(hào)不在測(cè)量的零空間，信號(hào)的范數(shù)近似保持定義定義 2.32.3定定義義 2 2. .4 4 對(duì)對(duì)于于所所有有不不相相交交的的,1,T TN，集集合合

29、的的勢(shì)勢(shì) TS和和TS ，對(duì)對(duì)于于SSN， S,S-約約束束正正交交常常數(shù)數(shù),S S為為使使 ,TTS Sccc c 最最小小的的數(shù)數(shù)。幾幾何何意意義義是是由由T 和和T 張張成成的的列列矢矢量量的的兩兩個(gè)個(gè)子子空空間間最最小小夾夾角角的的余余弦弦。其其值值越越小小，說(shuō)說(shuō)明明兩兩個(gè)個(gè)子子空空間間接接近近正正交交。 S和和,S S度量了矢量度量了矢量 njj JvR接近于正交基的程度。當(dāng)接近于正交基的程度。當(dāng)滿(mǎn)足滿(mǎn)足S S- -階階 RIPRIP， 則說(shuō)明， 則說(shuō)明近似保持了近似保持了 S S- -稀疏的信號(hào)的歐幾里得距離。 也說(shuō)明稀疏的信號(hào)的歐幾里得距離。 也說(shuō)明了了 S S- -稀疏信號(hào)不在

30、稀疏信號(hào)不在的零空間。這對(duì)唯一性的保證很重要的零空間。這對(duì)唯一性的保證很重要。關(guān)于關(guān)于 RIP條件的另一種等價(jià)說(shuō)法是矩陣中所有可能的條件的另一種等價(jià)說(shuō)法是矩陣中所有可能的 S S 個(gè)列向量近似正交。個(gè)列向量近似正交。 定理定理2.52.5定理定理2.62.6定理定理 2.7 假設(shè)假設(shè) x 是一個(gè)是一個(gè) S-稀疏的信號(hào)稀疏的信號(hào)且且231SS ，或者，或者，221,SSS ，則，則 1min,. .xstyx 的解為的解為x 定理定理 2 2. .8 8（無(wú)噪聲恢復(fù)）（無(wú)噪聲恢復(fù)） 假設(shè)假設(shè)221s ，則，則 1min,. .xstyx 的解的解*x 服從服從*011sxxCxx 和和 1*20

31、12sxxC Sxx 0C 為為常數(shù)，常數(shù)，Sx 是保留是保留 x中的中的 S S 個(gè)最大元素，其余元素都置個(gè)最大元素，其余元素都置零的矢量。如果零的矢量。如果 x是是 S S- -稀疏的，則可完全恢復(fù)。稀疏的，則可完全恢復(fù)。 2.3.6 魯棒測(cè)量魯棒測(cè)量對(duì)對(duì)于于實(shí)實(shí)際際應(yīng)應(yīng)用用，C CS S 應(yīng)應(yīng)該該既既能能處處理理稀稀疏疏信信號(hào)號(hào)，也也能能對(duì)對(duì)可可壓壓縮縮信信 號(hào)號(hào) 進(jìn)進(jìn) 行行 處處 理理 ， 可可 壓壓 縮縮 信信 號(hào)號(hào) 也也 可可 視視 為為 稀稀 疏疏 信信 號(hào)號(hào) 加加 入入 噪噪 聲聲 的的 結(jié)結(jié)果果；另另外外，在在測(cè)測(cè)量量中中也也不不可可避避免免的的引引入入噪噪聲聲，對(duì)對(duì)于于這這

32、兩兩種種情情況況，統(tǒng)統(tǒng)一一建建模模為為： yzAz 定理定理 1.9：假設(shè)：假設(shè)221s，則，則 12min,. .llastAay 的解的解*x滿(mǎn)足滿(mǎn)足 *0112sCaaCS C0, C1為常數(shù)，為常數(shù)，s是是矢量矢量的的 S 個(gè)大分量置保留，其余為個(gè)大分量置保留，其余為 0 結(jié)果。結(jié)果。 定理定理2.92.9測(cè)量測(cè)量A的零空間的零空間如果想從測(cè)量中重建所有的稀疏信號(hào)如果想從測(cè)量中重建所有的稀疏信號(hào)x，則對(duì)任意一對(duì)不，則對(duì)任意一對(duì)不同的信號(hào)同的信號(hào)x和和x ， 必然有必然有Ax與與Ax。如果來(lái)觀測(cè)。如果來(lái)觀測(cè)Ax=Ax，則得到，則得到x-x是是2K稀疏的，稀疏的， 因此，因此，A能唯能唯一

33、表示所有一表示所有 ，則，則 中不能含有中不能含有 的向量。有許多的向量。有許多方式可以表征這種性質(zhì)，其中之一為方式可以表征這種性質(zhì)，其中之一為A的的Spark定義定義Spark：一給定矩陣：一給定矩陣A的的Spark是其最少的線性相關(guān)列是其最少的線性相關(guān)列的個(gè)數(shù)。的個(gè)數(shù)。 2.3.7 最小化問(wèn)題的唯一解最小化問(wèn)題的唯一解P0 問(wèn)題的唯一解問(wèn)題的唯一解 ( )/ 2kspark AP1 問(wèn)題的唯一解問(wèn)題的唯一解 101(1( ) )2xA稱(chēng)稱(chēng)A有有則則A具有具有k階零空間性質(zhì)階零空間性質(zhì)( )0hN A1112hh k MRI圖像Fourier 采樣，22線令能量最小 ，未采樣的Fourier

34、系數(shù)置0CS重建，令圖像的TV范數(shù)最小 利用計(jì)算機(jī)解決實(shí)際問(wèn)題，通常要按以下步驟進(jìn)行：利用計(jì)算機(jī)解決實(shí)際問(wèn)題，通常要按以下步驟進(jìn)行： （1）建立數(shù)學(xué)模型，即把實(shí)際問(wèn)題抽象為一個(gè)數(shù)學(xué)）建立數(shù)學(xué)模型，即把實(shí)際問(wèn)題抽象為一個(gè)數(shù)學(xué)問(wèn)題，可以是一個(gè)方程組問(wèn)題，可以是一個(gè)方程組 、一個(gè)函數(shù)、一個(gè)微分方程、一個(gè)函數(shù)、一個(gè)微分方程等。等。 （2）選擇數(shù)值方法，要考慮所能達(dá)到的精度，計(jì)）選擇數(shù)值方法，要考慮所能達(dá)到的精度，計(jì)算量，方法對(duì)數(shù)據(jù)微小擾動(dòng)的靈敏度。算量，方法對(duì)數(shù)據(jù)微小擾動(dòng)的靈敏度。 （3）編寫(xiě)程序，上機(jī)計(jì)算。）編寫(xiě)程序，上機(jī)計(jì)算。第二部分第二部分 CSCS中的信號(hào)重建中的信號(hào)重建兩類(lèi)主要方法：兩類(lèi)主要

35、方法：一、貪婪搜索一、貪婪搜索 （Matched Pursuit, 匹配追蹤）匹配追蹤）二、基追蹤二、基追蹤 （Basis Pursuit， 基追蹤）基追蹤） 稱(chēng)為基追蹤問(wèn)題，（稱(chēng)為基追蹤問(wèn)題，（Basis Pursuit，BP）匹配追蹤（匹配追蹤（Matched Pursuit，MP）一、匹配追蹤（一、匹配追蹤（Matched Pursuit，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)MPMP）MP算法的步驟算法的步驟1. 初始化初始化稀疏稀疏矢量矢量x為為0，留數(shù)，留數(shù)r0=y，循環(huán)索引，循環(huán)索引 t=1； 2. 確定索引確定索引1argmax,ttr, %讓矩陣讓矩陣的每個(gè)列的每個(gè)列向量向量（或稱(chēng)為原子）與（或稱(chēng)為原子

36、）與rt-1作內(nèi)積，找到是的該內(nèi)積最大的作內(nèi)積，找到是的該內(nèi)積最大的列向量的序號(hào)給列向量的序號(hào)給t； 3. 更新更新系數(shù)：系數(shù)： 1()(),ttttxxr， 4更新留數(shù)更新留數(shù) 11,tttttrrr， 5. 更新更新 t=t+1； 6如果如果 tS, 則停止迭代，否則則停止迭代，否則返回步驟返回步驟 2 正交匹配追蹤（正交匹配追蹤（Orthogonal Orthogonal Matched Pursuit，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)OMPOMP） OMP算法步驟算法步驟 t=t+1;5：如果：如果 tS, 則停止迭代，否則重復(fù)步驟則停止迭代，否則重復(fù)步驟1體現(xiàn)正體現(xiàn)正交思想交思想22minxxyx min

37、( )minTxxxf xyxyx( )0f xx由多元函數(shù)的微分學(xué)知，上式的解一定是駐點(diǎn)由多元函數(shù)的微分學(xué)知，上式的解一定是駐點(diǎn)( )20Tf xyxx TTxy 1TTxy 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 s.t.其中其中 為為MN階階矩陣矩陣 min A =b0Tc xxx11121N21222NM1M2MNaa.aaa.aA=.aa.a12n=(c ,c ,c )Tc12N=( ,)Txx xx12Nb=(b ,b ,b )T二、基追蹤問(wèn)題（二、基追蹤問(wèn)題（BPBP） 約束條件以及目標(biāo)約束條件以及目標(biāo)函數(shù)都是決策變量函數(shù)都是決策變量的線性函數(shù)的規(guī)劃的線性函數(shù)的規(guī)劃問(wèn)題稱(chēng)為

38、問(wèn)題稱(chēng)為線性規(guī)劃線性規(guī)劃(Linear Programming),A by1;1c ,xuvuxv為 中的正元素,為負(fù)元素的絕對(duì)值uvya 1min as.t. 線性規(guī)劃問(wèn)題解的概念：線性規(guī)劃問(wèn)題解的概念： (1) (1) 可行解可行解。滿(mǎn)足約束條件的解。滿(mǎn)足約束條件的解可行解集稱(chēng)為線性規(guī)劃問(wèn)題的可行域?？尚薪饧Q(chēng)為線性規(guī)劃問(wèn)題的可行域。 (2) (2) 最優(yōu)解最優(yōu)解。使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱(chēng)為最優(yōu)解，。使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱(chēng)為最優(yōu)解，最優(yōu)解常用最優(yōu)解常用 表示。表示。 (3) (3) 基基。若是中。若是中M MM M階非奇異矩陣，即階非奇異矩陣，即| |0|0，則稱(chēng)是線性規(guī)，則

39、稱(chēng)是線性規(guī)劃問(wèn)題的一個(gè)基。劃問(wèn)題的一個(gè)基。 min Tc xA =b0 xx*x12N=( ,)Txx xxD= / A =b ,0 xxx s.t.基向量，基變量基向量，基變量 若是線性規(guī)劃問(wèn)題的一個(gè)基，那么一定是若是線性規(guī)劃問(wèn)題的一個(gè)基，那么一定是由由M M個(gè)線性無(wú)關(guān)的列向量組成，不失一般性，可設(shè)個(gè)線性無(wú)關(guān)的列向量組成，不失一般性，可設(shè) 稱(chēng)稱(chēng) 為為基向量基向量，與基向量相對(duì)應(yīng)的變量稱(chēng)為與基向量相對(duì)應(yīng)的變量稱(chēng)為基變量基變量。 基的個(gè)數(shù)基的個(gè)數(shù) 一個(gè)線性規(guī)劃的基通常不是唯一的，但是一個(gè)線性規(guī)劃的基通常不是唯一的，但是基的個(gè)數(shù)基的個(gè)數(shù)也不也不會(huì)超過(guò)會(huì)超過(guò) 個(gè)。一旦線性規(guī)劃的基確定了，那么相應(yīng)的基

40、向量、基變量個(gè)。一旦線性規(guī)劃的基確定了，那么相應(yīng)的基向量、基變量和非基變量也就確定了。和非基變量也就確定了。11121M21222M12MM1M2MMaa.aaa.aB=(P,P ,P ).aa.aMNCj1j2jMjp =(a ,a ,a), (j=1,2,M)jPjx , (j=1,2,M)( (4) 4) 基本解基本解。設(shè)。設(shè)B B是線性規(guī)劃的一個(gè)基，若令是線性規(guī)劃的一個(gè)基，若令n-mn-m個(gè)非基變量等于個(gè)非基變量等于0 0，則，則所得的方程組所得的方程組=b=b的解稱(chēng)為線性規(guī)劃問(wèn)題的一個(gè)基本解（簡(jiǎn)稱(chēng)基解）。的解稱(chēng)為線性規(guī)劃問(wèn)題的一個(gè)基本解（簡(jiǎn)稱(chēng)基解）。 有一個(gè)基就可以求得一個(gè)基本解。有

41、一個(gè)基就可以求得一個(gè)基本解。 由基的有限性可知，基本解的個(gè)數(shù)也不會(huì)超過(guò)由基的有限性可知，基本解的個(gè)數(shù)也不會(huì)超過(guò) 個(gè)。個(gè)。 由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5) (5) 基本可行解基本可行解。滿(mǎn)足非負(fù)條件的基本解稱(chēng)為基本可行解。滿(mǎn)足非負(fù)條件的基本解稱(chēng)為基本可行解 （簡(jiǎn)稱(chēng)基可行解）。（簡(jiǎn)稱(chēng)基可行解）。與基本可行解對(duì)應(yīng)的基稱(chēng)為與基本可行解對(duì)應(yīng)的基稱(chēng)為可行基可行基。 基本可行解的非零向量的個(gè)數(shù)小于等于基本可行解的非零向量的個(gè)數(shù)小于等于m m，并且都是非負(fù)的。，并且都是非負(fù)的。 由于基本可行解的數(shù)目一般少于基本解的

42、數(shù)目，因此可行基由于基本可行解的數(shù)目一般少于基本解的數(shù)目，因此可行基 的數(shù)目也要少于基的數(shù)目。的數(shù)目也要少于基的數(shù)目。 當(dāng)基本可行解中有一個(gè)或多個(gè)基變量是取零值時(shí)，稱(chēng)此解為當(dāng)基本可行解中有一個(gè)或多個(gè)基變量是取零值時(shí)，稱(chēng)此解為 退化的基本可行解退化的基本可行解。MNC可行解可行解基本解基本解求解線性規(guī)劃：求解線性規(guī)劃：圖解法圖解法單純形法單純形法內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法70單純形法的一般步驟如下：?jiǎn)渭冃畏ǖ囊话悴襟E如下：（1 1）尋找一個(gè)）尋找一個(gè)初始的基本可行解初始的基本可行解。（2 2）檢查現(xiàn)行的基本可行解是否）檢查現(xiàn)行的基本可行解是否最優(yōu)最優(yōu)，如果為最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則

43、轉(zhuǎn)一步。則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3 3）移至目標(biāo)函數(shù)值有所改善的）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解另一個(gè)基本可行解，然后轉(zhuǎn)回到步驟（然后轉(zhuǎn)回到步驟（2 2）。）。 其其基本思路基本思路是從一個(gè)初始的基本可行解出發(fā)，是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。 19471947年，年，DantzigDantzig提出的單純形法把尋優(yōu)提出的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。中。 單純形法單純形法Lasso問(wèn)題問(wèn)題 yx 1min xs.t.BPD

44、N（Basis Pursuit Denoising）BP（Basis Pursuit ）1min xs.t.22yx(1) 約束問(wèn)約束問(wèn)題題(2) 約束約束問(wèn)題問(wèn)題問(wèn)題問(wèn)題(2)的解要么是的解要么是x=0, 要么是問(wèn)題要么是問(wèn)題(3)的解的解,因此說(shuō)因此說(shuō)BPDN問(wèn)題與問(wèn)題與LASSO等價(jià)等價(jià)(3)無(wú)約束無(wú)約束問(wèn)題問(wèn)題3.13.1無(wú)約束最優(yōu)化方法無(wú)約束最優(yōu)化方法min( ),nf xxR 無(wú)約束問(wèn)題無(wú)約束問(wèn)題定義定義：設(shè)函數(shù)：設(shè)函數(shù) f(x) 存在一階偏導(dǎo)數(shù)，存在一階偏導(dǎo)數(shù)，xRn ，向量，向量 )(xf=Tnxfxfxf ,21為為f(x)在點(diǎn)在點(diǎn)x處的梯度。處的梯度。定義定義 設(shè)函數(shù)設(shè)函數(shù)

45、 存在二階偏導(dǎo)數(shù)，存在二階偏導(dǎo)數(shù)，xR ，則稱(chēng)矩陣，則稱(chēng)矩陣 )(xfn 2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxf為為 在點(diǎn)在點(diǎn)x處的處的Hesse矩陣。矩陣。 )(xf)(2xf =三、三、BPDNBPDN 問(wèn)題問(wèn)題定理定理: (一階必要條件一階必要條件） 凸集凸集和和凸函數(shù)凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識(shí)。給出凸集和凸函數(shù)的一些基本知識(shí)。 設(shè)設(shè) ，若對(duì)，若對(duì)D中任意兩點(diǎn)中任意兩點(diǎn) ，連接，連接 的線段仍屬于的線段仍屬于D；換言之，對(duì)；換言之，對(duì) ,

46、則稱(chēng)則稱(chēng)D為為凸集凸集。 稱(chēng)為稱(chēng)為 的的凸組合凸組合。NDR(1)(2),xxD(1)(2)1xxD(1)(2),xx(1)(2),xx0,1(1)(2)1xx(1)(2),xx定義定義: 凸集凸集對(duì)凸的一元函數(shù)對(duì)凸的一元函數(shù) 的幾的幾何意義為：在曲線上任取何意義為：在曲線上任取兩點(diǎn)兩點(diǎn)P1(x1, ), P2(x2, )弦弦 位于位于弧弧 之上（見(jiàn)圖）。之上（見(jiàn)圖）。)(xf)(1xf(x2)f21PP21PPx x1x x2x x(x, y)p p1p p2)(xf 設(shè)設(shè)D為為RN 中非空凸集，若對(duì)中非空凸集，若對(duì) , 恒有恒有則稱(chēng)則稱(chēng)f(x) 為為D上的上的凸函數(shù)凸函數(shù)；進(jìn)一步，若；進(jìn)一

47、步，若 時(shí)，上式時(shí)，上式僅僅0)，修改，修改 為為x .01miig x x 求解問(wèn)題求解問(wèn)題(5)式就變?yōu)榍蠼鉄o(wú)約束問(wèn)題式就變?yōu)榍蠼鉄o(wú)約束問(wèn)題(8)式式 miigMfMp1,xxx 7 miigMfMp12, 0min,xxx 8 稱(chēng)函數(shù)稱(chēng)函數(shù) 為懲罰函數(shù)（或罰函數(shù)），其中為懲罰函數(shù)（或罰函數(shù)），其中第二項(xiàng)第二項(xiàng) 為懲罰項(xiàng)。稱(chēng)為懲罰項(xiàng)。稱(chēng)M為罰因?yàn)榱P因子。子。 懲罰函數(shù)只對(duì)不滿(mǎn)足約束條件的點(diǎn)實(shí)行懲罰。當(dāng)懲罰函數(shù)只對(duì)不滿(mǎn)足約束條件的點(diǎn)實(shí)行懲罰。當(dāng) 時(shí)，滿(mǎn)足各個(gè)時(shí)，滿(mǎn)足各個(gè) ，故罰項(xiàng)等于，故罰項(xiàng)等于0，不受懲罰；當(dāng)不受懲罰；當(dāng) 時(shí)，必有時(shí)，必有 ，故罰，故罰項(xiàng)項(xiàng)0，對(duì)極小化罰函數(shù)的問(wèn)題，就要受懲

48、罰。，對(duì)極小化罰函數(shù)的問(wèn)題，就要受懲罰。x 0 xigx 0 xigMp, x miigM12, 0minx 在實(shí)際計(jì)算中，罰因子在實(shí)際計(jì)算中，罰因子M的值選得過(guò)小或過(guò)大都不好。如的值選得過(guò)小或過(guò)大都不好。如果選得過(guò)小，則罰函數(shù)的極小點(diǎn)遠(yuǎn)離約束問(wèn)題的最優(yōu)解，果選得過(guò)小，則罰函數(shù)的極小點(diǎn)遠(yuǎn)離約束問(wèn)題的最優(yōu)解，計(jì)算效率很差；如果計(jì)算效率很差；如果M過(guò)大，則給罰函數(shù)的極小化增加計(jì)過(guò)大，則給罰函數(shù)的極小化增加計(jì)算上的困難。因此，一般策略是取一個(gè)趨向無(wú)窮大的嚴(yán)格算上的困難。因此，一般策略是取一個(gè)趨向無(wú)窮大的嚴(yán)格遞增正數(shù)列遞增正數(shù)列 ，從某個(gè)，從某個(gè) 開(kāi)始，對(duì)每個(gè)開(kāi)始，對(duì)每個(gè) 求解：求解：kM1MkM l

49、jjmiikkhgMfMp1212, 0min,minxxxx 11當(dāng)當(dāng) 趨向于正無(wú)窮大時(shí)，點(diǎn)列趨向于正無(wú)窮大時(shí)，點(diǎn)列 就從可行域外部趨于原就從可行域外部趨于原問(wèn)題的極小點(diǎn)，問(wèn)題的極小點(diǎn)，“外點(diǎn)法外點(diǎn)法”正是因此而得名正是因此而得名kM kx 第第1步：給定初始點(diǎn)步：給定初始點(diǎn) ，初始罰因子，初始罰因子 （例如（例如 ），），放大系數(shù)放大系數(shù) （如?。ㄈ缛?或或10），允許誤差），允許誤差 。令令 。 第第2步：求解罰函數(shù)步：求解罰函數(shù) 的無(wú)約束極小化問(wèn)題。的無(wú)約束極小化問(wèn)題。 以以 為初始點(diǎn)，選擇適當(dāng)?shù)姆椒ㄇ鬄槌跏键c(diǎn)，選擇適當(dāng)?shù)姆椒ㄇ蠼饨?，得其極小點(diǎn)，得其極小點(diǎn) 。 第第3步：判斷精度。步

50、：判斷精度。 在在 點(diǎn)，若罰項(xiàng)點(diǎn)，若罰項(xiàng) ，則停止計(jì)算，得到原問(wèn)題的，則停止計(jì)算，得到原問(wèn)題的近似極小點(diǎn)近似極小點(diǎn) ；否則令；否則令 ，置，置 ，返回第返回第2步。步。 0 x1M11M1501:kkMp, x1kxkMp,minx kx kx kx1:kkkkMM1外點(diǎn)法外點(diǎn)法 考慮非線性規(guī)劃考慮非線性規(guī)劃 s.t 記記 為可行域內(nèi)部。即為可行域內(nèi)部。即 是可行域是可行域 中所有嚴(yán)格內(nèi)點(diǎn)中所有嚴(yán)格內(nèi)點(diǎn)（即不包括可行域邊界上的點(diǎn)）的集合。（即不包括可行域邊界上的點(diǎn)）的集合。 ；xfmin migi, 2 , 1, 0 x migi, 2 , 1, 01xx 131213.2.2 內(nèi)點(diǎn)法內(nèi)點(diǎn)法

51、與外點(diǎn)法不同，內(nèi)點(diǎn)法要求整個(gè)迭代過(guò)程始終在與外點(diǎn)法不同，內(nèi)點(diǎn)法要求整個(gè)迭代過(guò)程始終在可行域可行域內(nèi)部?jī)?nèi)部進(jìn)行，初始點(diǎn)是一個(gè)嚴(yán)格的內(nèi)點(diǎn)，再在可行域邊界上設(shè)進(jìn)行，初始點(diǎn)是一個(gè)嚴(yán)格的內(nèi)點(diǎn)，再在可行域邊界上設(shè)置一道置一道“障礙障礙”，以阻止搜索點(diǎn)到可行域邊界上去。，以阻止搜索點(diǎn)到可行域邊界上去。 構(gòu)造構(gòu)造障礙函數(shù)障礙函數(shù)（取倒數(shù)或?qū)?shù)函數(shù)）：（取倒數(shù)或?qū)?shù)函數(shù)）： 或或 其中其中 是很小的正數(shù)，通常稱(chēng)為障礙因子，稱(chēng)是很小的正數(shù)，通常稱(chēng)為障礙因子，稱(chēng) 或或 為障礙項(xiàng)。為障礙項(xiàng)。 miikkgrfrp11,xxx miikkgrfrp1ln,xxx 1514kr miikgr11x miikgr1lnx

52、障礙函數(shù)應(yīng)具備的功能：可行域內(nèi)部或離邊界較遠(yuǎn)障礙函數(shù)應(yīng)具備的功能：可行域內(nèi)部或離邊界較遠(yuǎn)處，障礙函數(shù)與處，障礙函數(shù)與原目標(biāo)函數(shù)盡可能接近原目標(biāo)函數(shù)盡可能接近，而在，而在邊界上時(shí)，邊界上時(shí)，應(yīng)變成很大的值應(yīng)變成很大的值，因此滿(mǎn)足該要求的障礙函數(shù)其極小值，因此滿(mǎn)足該要求的障礙函數(shù)其極小值不會(huì)在可行域的邊界上達(dá)到。不會(huì)在可行域的邊界上達(dá)到。內(nèi)點(diǎn)法計(jì)算步驟 第第1步：給定嚴(yán)格內(nèi)點(diǎn)步：給定嚴(yán)格內(nèi)點(diǎn) 為初始點(diǎn)，初始障礙因子為初始點(diǎn)，初始障礙因子 （如取（如取 ），縮小系數(shù)），縮小系數(shù) （如取（如取 或或0.2），），允許誤差允許誤差 ，置，置 。 第第2步：構(gòu)造障礙函數(shù)步：構(gòu)造障礙函數(shù) ，障礙函數(shù)可取，障

53、礙函數(shù)可取(14)式形式，式形式，也可取也可取(15)式形式。式形式。 第第3步：求解障礙函數(shù)步：求解障礙函數(shù) 的無(wú)約束極小化問(wèn)題。的無(wú)約束極小化問(wèn)題。 以以 為初始點(diǎn)，求解為初始點(diǎn)，求解 得其極小點(diǎn)得其極小點(diǎn) 。 是可行域中所有嚴(yán)格內(nèi)點(diǎn)的集合。是可行域中所有嚴(yán)格內(nèi)點(diǎn)的集合。 第第4步：判斷精度。步：判斷精度。 若收斂準(zhǔn)則得到滿(mǎn)足，則迭代停止，取若收斂準(zhǔn)則得到滿(mǎn)足，則迭代停止，取 作為原問(wèn)作為原問(wèn)題極小點(diǎn)題極小點(diǎn) 的近似值。否則取的近似值。否則取 ，置，置 ，轉(zhuǎn)，轉(zhuǎn)第第3步。 0 x01r11r1 , 01 . 001:kkrp, xkrp, x1kxkrp,minx1x kx1 kx *xk

54、krr11: kk內(nèi)點(diǎn)法的優(yōu)缺點(diǎn)內(nèi)點(diǎn)法的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：由于迭代總是在可行域內(nèi)進(jìn)行，每一個(gè)中優(yōu)點(diǎn)：由于迭代總是在可行域內(nèi)進(jìn)行，每一個(gè)中間結(jié)果都是可行解，可以作為近似解。間結(jié)果都是可行解，可以作為近似解。 缺點(diǎn)：選取初始可行點(diǎn)較困難，且只適用于含有缺點(diǎn)：選取初始可行點(diǎn)較困難，且只適用于含有不等式約束的非線性規(guī)劃問(wèn)題。不等式約束的非線性規(guī)劃問(wèn)題。3.3 其他算法其他算法3.3.1 ISTA(Iterative Shrinkage-Thresholding Algorithm）1.考慮無(wú)約束的最小化連續(xù)可微函數(shù)考慮無(wú)約束的最小化連續(xù)可微函數(shù)f(x),解決這個(gè)問(wèn)題的最簡(jiǎn)單方法就是用梯度算法產(chǎn)生解決這個(gè)問(wèn)題的最簡(jiǎn)單方法就是用梯度算法產(chǎn)生x序列序列這個(gè)公式可以等價(jià)為如下二次形式這個(gè)公式可以等價(jià)為如下二次形式把這種梯度算法應(yīng)用到非光滑把這種梯度算法應(yīng)用到非光滑l1正則化問(wèn)題中正則化問(wèn)題中那么那么x的迭代序列為的迭代序列為 將公式將公式(5)的第二項(xiàng)和第三項(xiàng)結(jié)合，并去掉常數(shù)項(xiàng)，則公的第二項(xiàng)和第三項(xiàng)結(jié)合，并去掉常數(shù)項(xiàng)，則公式式(5)可表示為可表示為 L1范數(shù)是可分離的那么范數(shù)是可