小波變換及稀疏表述初步-梅樹立

1、梅樹立2022-7-41三維空間屬于線性空間大多數(shù)的信號(hào)如圖像等，無(wú)法在線性空間描述線性向量空間和泛函空間典型的泛函空間：距離空間，Banah空間，內(nèi)積空間，Hilbert空間。構(gòu)成線性空間的元素是向量（N維），構(gòu)成泛函空間的基本元素是函數(shù)（基函數(shù)）。因此，泛函簡(jiǎn)稱為“函數(shù)的函數(shù)”2022-7-422022-7-43如何用數(shù)學(xué)公式表達(dá)這種基函數(shù)逼近？2022-7-44如何用數(shù)學(xué)公式表達(dá)這種基函數(shù)逼近？如何提高逼近精度？2022-7-45V0: 在整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022-7-46V1: 在半整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以

2、下形式：2022-7-47V2: 在1/4整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022-7-48V0V2V12022-7-49Vj: 在1/2j整數(shù)區(qū)間內(nèi)為常數(shù)的所有平方可積函數(shù)構(gòu)成的空間，可表示為以下形式：2022-7-410思考：將一個(gè)函數(shù)分別表達(dá)在V0空間和V1空間，這兩種逼近表達(dá)之間的誤差是多少？換句話說(shuō)，我們能否找到誤差補(bǔ)空間W0，滿足:2022-7-411RECALL2022-7-41200.20.40.60.8100.20.40.60.81函數(shù)f(x)=a-(x-b)2在V0空間的映射（在V0空間被逼近）若a=b=1,則h=2/3101)(hhdxxf

3、22102103102101021023132)(babbaxbxdxbaxdxbdxxdxbxa2022-7-41300.20.40.60.8100.20.40.60.81 f(x)V0V1V1V1函數(shù)f(x)=a-(x-b)2在V1空間的映射（在V1空間被逼近）若a=b=1,則h1=5/12, h2=11/12225 . 0025 . 0035 . 0025 . 005 . 0025 . 0025 . 042415 . 032)(babbaxbxdxbaxdxbdxxdxbxa21122121*5 . 05 . 04241babhhbab2215 . 0215 . 0315 . 0215

4、. 015 . 0215 . 025 . 0432475 . 032)(babbaxbxdxbaxdxbdxxdxbxa222223127*5 . 05 . 043247babhhbab2022-7-41400.20.40.60.8100.20.40.60.81 f(x)V0V1V1V110VV V0的補(bǔ)空間？2022-7-415100VWV2022-7-41600.20.40.60.8100.20.40.60.81 f(x)V0V1V1V110VV 1h4123121212211bbabbabhhh2h41231231272222bbabbabhhh2411bh4122bh2022-7-41

5、700.20.40.60.8100.20.40.60.81 f(x)V0V1V1V10V0W2022-7-418TranslatingStretching2022-7-41900.20.40.60.8100.20.40.60.81 f(x)V0V1V1V1f(x)=a-(x-b)2在V0空間內(nèi)的逼近表達(dá)式（紅色直線）： xxg32)(0在V1空間內(nèi)的逼近表達(dá)式（綠藍(lán)色直線）：1212112125)(1xxxg在補(bǔ)空間W1空間內(nèi)的逼近表達(dá)式： xxw41)(02022-7-420)()()(100 xgxwxg)()()(211xgxwxg.)()()(11xgxwxgnnn)()()()()(

6、1100 xgxwxwxwxgnn因此，有進(jìn)一步可表示為 jkjkjknxaxbxg0)(2022-7-421通過平移和伸縮可以得到Haar小波族2022-7-4222022-7-4232022-7-424kxjjjk222/2022-7-425Only 0 function in all spaces如果某函數(shù)在所有空間中，必然在任意區(qū)間上是常數(shù)，而且平方可積，因此只能是0。所謂平方可積，即：dxxf2)(2022-7-426可以逼近所有的平方可積函數(shù)f (x)1)2 ()()(nnVxfVxfd00)()(VkxfVxfe以上盡管涉及到了內(nèi)積運(yùn)算，但實(shí)質(zhì)屬于插值。即以上討論內(nèi)容均在巴拿赫空

7、間進(jìn)行。完備的線性賦范空間稱為Banach空間由于沒有定義內(nèi)積概念，只能用線性泛函代替內(nèi)積。如插值算子，Laplace算子（微分算子）等。（算子是泛函的一種）。坐標(biāo)就是線性泛函。完備的內(nèi)積空間稱為Hilbert空間。數(shù)值逼近理論在Hilbert空間定義。設(shè)X是n維實(shí)向量空間，對(duì)其中向量nnyyyyxxxx2121,定義內(nèi)積nnTyxyxyxyxyx2211,正交的定義: (x,y)=0222yxyx任何n維空間都存在正交基正交推論：24681012141666.577.588.599.51010.511 插值逼近設(shè)n.,210是線性內(nèi)積空間X的n+1個(gè)線性無(wú)關(guān)元素，子集nSpan,.,10在中

8、尋求對(duì)X的某一元素f的最佳逼近時(shí)指在中存在一元素S*，使對(duì)于任意S都有SfSf*定理：niiicS0*1是集對(duì)f 的最佳逼近元素的充要條件是S1-f 與所有的njj,.,1 , 0正交。假設(shè)f 是集合中的元素，則，f 可以被集合中的基函數(shù)n.,210精確線性表達(dá)。誤差S1-f =0。若表達(dá)式的誤差不為零，且誤差仍然能被基函數(shù)表達(dá)，說(shuō)明表達(dá)式還不完整。nkfcnkfcnkfSkkniiikniiik,.,1 , 0,.,1 , 0, 0,.,1 , 0, 0,0*0*1即由下列方程組決定*ic.,.,.,.,.,*11*001*1*111*0010*0*110*000nnnnnnnnnnfccc

9、fcccfccc對(duì)應(yīng)的矩陣形式為 nnnnnnnnfffccc,.,.,.,.,10*1*01011101010008 , 0,)(2/2xexx2/)(2)()(ixieixx被逼近函數(shù)為2 , 0),cos(1)(xxxf01234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80

10、.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.9101234567800.10.20.30.40.50.60.70.80.91F=MC=F0123456700.20.40.60.811.21.41.61.8201234567-0.500.511.52 data1data239 Relation to measurements Denoising By Energy Minimization Thomas Baye

11、s 1702 - 1761Prior or regularizationy : Given measurements x : Unknown to be recovered xyxxfPr2122Many of the proposed denoising algorithms are related to the minimization of an energy function of the formq This is in-fact a Bayesian point of view, adopting the Maximum-Aposteriori Probability (MAP)

12、estimation.q Clearly, the wisdom in such an approach is within the choice of the prior modeling the images of interest. 40 The Evolution 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 a

13、s priors, 22xxPrEnergy 22xxPrLSmoothness 2xxPrWLAdapt+ Smooth xxPrLRobust Statistics 1xxPrTotal-Variation 1xxPrWWavelet Sparsity 00 xPrSparse & Redundant DxforImage Denoising Via Learned Dictionaries and Sparse representationsBy: Michael Elad41 The SparselandSparseland Model for Images MM KNDA f

14、ixed Dictionaryq Every column in D (dictionary) is a prototype signal (Atom).q The vector is generated randomly with few (say L) non-zeros at random locations and with random values. A sparse & random vectorxNx L. t . sy21minarg0022DDD -y = - Our MAP Energy Function q We Lo norm is effectively c

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

16、resentations, and its uses.x What Should D Be? Our Assumption: Good-behaved Images have a sparse representation. .21minarg0022DDxLtsyD 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 approa

17、ch to choose D is from a known set of transforms (Steerable wavelet, Curvelet, Contourlets, Bandlets, )欠定方程組的稀疏解欠定方程組的稀疏解測(cè)量矩陣則:009870065400321A97000X63000ZZ,X均為2-稀疏向量，且AX=AZ，但X=Z則表示矩陣A的列子矩陣(從N列中抽出S列構(gòu)成的子矩陣 )，類似地，對(duì)向量,我們用表示X中的S個(gè)元素構(gòu)成的子向量，即如果x和z都是s-稀疏的,且Ax=Az, 則x=z除0向量外，零空間核A中不包含任何2s-稀疏向量Proof. 設(shè)v是零空間A中一

18、2s-稀疏向量。若s-稀疏向量x和z中非0元素的位置不重疊，換句話說(shuō)，x-z屬于2s-稀疏向量。不失一般性，設(shè)v=x-z.根據(jù)(a), 對(duì)于任一s-稀疏N維向量X和Z，若滿足AX=AZ，則X=Z. 因此,v=0(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之間形成單一映射)009870065400321A97000X63000ZZ,X均為2-稀疏向量，且AX=AZ，但X=Z不符合前述哪些條件？矩陣的秩至少應(yīng)該為2s2s-稀疏N維向量V的支撐區(qū)間為S=supp(v). 因此， AV=AsVs.注意到S=suppV涵蓋了N所有的可能子集。根據(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的要求為：定理2 (s-稀N維疏信號(hào)的壓縮測(cè)量矩陣的存在