小波變換及稀疏表述初步梅樹(shù)立

1、小波變換及稀疏表示初步2022/9/301三維空間屬于線性空間大多數(shù)的信號(hào)如圖像等，無(wú)法在線性空間描述線性向量空間和泛函空間典型的泛函空間：距離空間，Banah空間，內(nèi)積空間，Hilbert空間。構(gòu)成線性空間的元素是向量（N維），構(gòu)成泛函空間的基本元素是函數(shù)（基函數(shù)）。因此，泛函簡(jiǎn)稱為“函數(shù)的函數(shù)”2022/9/302概述-從空間解析幾何談起2022/9/303基函數(shù)和三角板如何用數(shù)學(xué)公式表達(dá)這種基函數(shù)逼近？2022/9/304基函數(shù)如何用數(shù)學(xué)公式表達(dá)這種基函數(shù)逼近？如何提高逼近精度？2022/9/305基函數(shù)V0: 在整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022/

2、9/306基函數(shù)空間V1: 在半整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022/9/307基函數(shù)空間V2: 在1/4整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022/9/308基函數(shù)空間V0V2V12022/9/309Vj: 在1/2j整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022/9/3010基函數(shù)空間思考：將一個(gè)函數(shù)分別表達(dá)在V0空間和V1空間，這兩種逼近表達(dá)之間的誤差是多少？換句話說(shuō)，我們能否找到誤差補(bǔ)空間W0，滿足:2022/9/3011RECALL2022/9/3012函數(shù)f(x)=a-(x-b)2在V0空間

3、的映射（在V0空間被逼近）若a=b=1,則h=2/32022/9/3013函數(shù)f(x)=a-(x-b)2在V1空間的映射（在V1空間被逼近）若a=b=1,則h1=5/12, h2=11/122022/9/3014V0的補(bǔ)空間？2022/9/30152022/9/30162022/9/30172022/9/3018TranslatingStretching2022/9/3019f(x)=a-(x-b)2在V0空間內(nèi)的逼近表達(dá)式（紅色直線）：在V1空間內(nèi)的逼近表達(dá)式（綠藍(lán)色直線）：在補(bǔ)空間W1空間內(nèi)的逼近表達(dá)式：2022/9/3020.因此，有進(jìn)一步可表示為2022/9/3021Haar小波通過(guò)平

4、移和伸縮可以得到Haar小波族2022/9/3022平移2022/9/3023伸縮2022/9/3024小波的一般表達(dá)式Haar小波的正交特性2022/9/3025多尺度分析Only 0 function in all spaces如果某函數(shù)在所有空間中，必然在任意區(qū)間上是常數(shù)，而且平方可積，因此只能是0。所謂平方可積，即：2022/9/3026多尺度分析可以逼近所有的平方可積函數(shù)f (x)以上盡管涉及到了內(nèi)積運(yùn)算，但實(shí)質(zhì)屬于插值。即以上討論內(nèi)容均在巴拿赫空間進(jìn)行。完備的線性賦范空間稱為Banach空間由于沒(méi)有定義內(nèi)積概念，只能用線性泛函代替內(nèi)積。如插值算子，Laplace算子（微分算子）等。

5、（算子是泛函的一種）。坐標(biāo)就是線性泛函。完備的內(nèi)積空間稱為Hilbert空間。數(shù)值逼近理論在Hilbert空間定義。Banach空間和Hilbert空間27設(shè)X是n維實(shí)向量空間，對(duì)其中向量?jī)?nèi)積舉例定義內(nèi)積28正交的定義: (x,y)=0利用內(nèi)積定義正交任何n維空間都存在正交基正交推論：29Hilbert空間中的最佳逼近30設(shè)線性內(nèi)積空間的最佳逼近是線性內(nèi)積空間X的n+1個(gè)線性無(wú)關(guān)元素，子集在中尋求對(duì)X的某一元素f的最佳逼近時(shí)指在中存在一元素S*，使對(duì)于任意都有31定理：作為最佳逼近元素的充要條件是集對(duì)f 的最佳逼近元素的充要條件是S1-f 與所有的正交。假設(shè)f 是集合中的元素，則，f 可以被集

6、合中的基函數(shù)精確線性表達(dá)。誤差S1-f =0。若表達(dá)式的誤差不為零，且誤差仍然能被基函數(shù)表達(dá)，說(shuō)明表達(dá)式還不完整。32根據(jù)定理推導(dǎo)逼近向量表達(dá)式由下列方程組決定33對(duì)應(yīng)的矩陣形式為34舉例被逼近函數(shù)為3536F=MC=F373839 Relation to measurements Denoising By Energy Minimization Thomas Bayes 1702 - 1761Prior or regularizationy : Given measurements x : Unknown to be recoveredMany of the proposed denoisi

7、ng algorithms are related to the minimization of an energy function of the formThis is in-fact a Bayesian point of view, adopting the Maximum-Aposteriori Probability (MAP) estimation.Clearly, the wisdom in such an approach is within the choice of the prior modeling the images of interest. 40 The Evo

8、lution Of Pr(x)During the past several decades we have made all sort of guesses about the prior Pr(x) for images: Mumford & Shah formulation, Compression algorithms as priors, EnergySmoothnessAdapt+ SmoothRobust StatisticsTotal-VariationWavelet SparsitySparse & RedundantBy: Michael Elad41 The Sparse

9、land Model for Images MKNA fixed DictionaryEvery column in D (dictionary) is a prototype signal (Atom).The vector is generated randomly with few (say L) non-zeros at random locations and with random values. A sparse & random vectorN41D-y = - Our MAP Energy Function We Lo norm is effectively counting

10、 the number of non-zeros in . The vector is the representation (sparse/redundant).The above is solved (approximated!) using a greedy algorithm - the Matching Pursuit Mallat & Zhang (93).In the past 5-10 years there has been a major progress in the field of sparse & redundant representations, and its

11、 uses.42 What Should D Be? Our Assumption: Good-behaved Images have a sparse representationD should be chosen such that it sparsifies the representationsThe approach we will take for building D is training it, based on Learning from Image Examples One approach to choose D is from a known set of tran

12、sforms (Steerable wavelet, Curvelet, Contourlets, Bandlets, )43欠定方程組的稀疏解測(cè)量矩陣44有關(guān)欠定方程組的兩個(gè)等價(jià)特性則:45Z,X均為2-稀疏向量，且AX=AZ，但X=Z46欠定方程組稀疏解的唯一性表達(dá)式則表示矩陣A的列子矩陣(從N列中抽出S列構(gòu)成的子矩陣 )，類(lèi)似地，對(duì)向量,我們用表示X中的S個(gè)元素構(gòu)成的子向量，即47四個(gè)等價(jià)的唯一性表達(dá)式如果x和z都是s-稀疏的,且Ax=Az, 則x=z除0向量外，零空間核A中不包含任何2s-稀疏向量Proof. 設(shè)v是零空間A中一2s-稀疏向量。若s-稀疏向量x和z中非0元素的位置不重疊

13、，換句話說(shuō)，x-z屬于2s-稀疏向量。不失一般性，設(shè)v=x-z.根據(jù)(a), 對(duì)于任一s-稀疏N維向量X和Z，若滿足AX=AZ，則X=Z. 因此,v=048(b) (a)設(shè)x,z是s-稀疏向量，且滿足Ax=Az. X-z是2s-稀疏向量，且A(x-z)=0。 如果A中不包含2s-稀疏非0向量，則x=z以上兩條等價(jià)性定理說(shuō)明：s-稀疏信號(hào)對(duì)應(yīng)的測(cè)量矩陣A中不包含2s-稀疏向量；A的行數(shù)m=2s取矩陣A的S列（card(S)Cm之間的單一映射矩陣(Y和X之間形成單一映射)49Z,X均為2-稀疏向量，且AX=AZ，但X=Z不符合前述哪些條件？矩陣的秩至少應(yīng)該為2s502s-稀疏N維向量V的支撐區(qū)間為

14、S=supp(v). 因此， AV=AsVs.注意到S=suppV涵蓋了N所有的可能子集。51根據(jù)測(cè)量矩陣A得到的壓縮信號(hào)：Y=AX，XCN，Y Cm稀疏表示的目標(biāo)：根據(jù)壓縮信號(hào)Y Cm恢復(fù)稀疏信號(hào)X CN該目標(biāo)對(duì)A的要求是：由于稀疏表示對(duì)A的要求為：52定理2 (s-稀N維疏信號(hào)的壓縮測(cè)量矩陣的存在性)對(duì)于N維s-稀疏信號(hào)X，一定存在2s*N測(cè)量矩陣A, 使得壓縮測(cè)量得到的向量Y可以唯一恢復(fù)。53定理254因此，As可逆且是一單射矩陣，符合定理1中的等價(jià)性質(zhì)c,定理得證。符合以上要求的矩陣還有很多，如55上述討論告訴我們：Y=AX，測(cè)量矩陣A對(duì)N維s-稀疏信號(hào)進(jìn)行壓縮測(cè)量得到的壓縮數(shù)據(jù)Y，當(dāng)A滿足一定條件時(shí)，可由Y唯一恢復(fù)原始信號(hào)X。A是m*N（Nm）矩陣，即A不存在逆矩陣。如何由Y恢復(fù)X？56設(shè)N維向量x是s-稀疏向量，假設(shè)該向量是通過(guò)2s個(gè)離散Fourier變換系數(shù)： 觀測(cè)。其中考慮以下三角多項(xiàng)式當(dāng)時(shí)，上式精確消失，因此我們重點(diǎn)尋找集合S57欠定方程組的稀疏解Mohimani G H, Babaie-Zadeh M, Jutten C. Fast sparse representation based on smoothed l0 morm. Proc 7th Int Conf Independ