凸優(yōu)化理論與應(yīng)用-逼近與擬合課件

1凸優(yōu)化理論與應(yīng)用第五章逼近與擬合問題原型-回歸問題問題描述：給定一組維向量，對給定的向量，用向量組的線性組合近似表示，使誤差最小。誤差可用范數(shù)形式表示：將向量組依次按列排列，可形成矩陣原誤差可表示為：當(dāng)時(shí)，假設(shè)矩陣的秩為，則，為平凡情況。2問題原型-測量問題問題描述：線性測量模型為其中為測量值向量，為輸入值，為待測定的向量參數(shù)，而為測量誤差。測量問題希望估算獲得最佳的，使得測量誤差值盡可能的小，即盡可能小。3問題原型-幾何投射問題問題描述：設(shè)線性變換，其像集子空間，給定空間中的一點(diǎn)，子空間關(guān)于的投影是該子空間中距離最近的一點(diǎn)，即將用關(guān)于矩陣的參數(shù)表示，可表示成，則上述問題即可轉(zhuǎn)換為求最優(yōu)參數(shù)的問題：注：若，則為平凡情況。45范數(shù)逼近問題問題描述：殘差向量最小平方逼近范數(shù)采用范數(shù)，原問題為：等價(jià)問題：最優(yōu)解滿足：6切比雪夫逼近范數(shù)采用范數(shù)，原問題為即可轉(zhuǎn)換為LP問題7絕對值和最小逼近范數(shù)采用范數(shù)，原問題為即可轉(zhuǎn)換為LP問題89罰函數(shù)逼近問題描述：若罰函數(shù)為凸函數(shù)，則罰函數(shù)逼近問題為凸優(yōu)化問題。罰函數(shù)表示逼近問題誤差的代價(jià)，一般為對稱、非負(fù)且10罰函數(shù)的例范數(shù)：死區(qū)線性罰函數(shù)：對數(shù)門限罰函數(shù)罰函數(shù)的例罰函數(shù)對逼近問題的誤差分布影響1112魯棒的罰函數(shù)Huber罰函數(shù)若大到一定程度時(shí)，罰函數(shù)為的線性函數(shù)，則稱該罰函數(shù)為魯棒的罰函數(shù)。13最小范數(shù)問題問題描述： 其中為方程組的解?？梢韵サ仁郊s束將其轉(zhuǎn)換為范數(shù)逼近問題：14最小范數(shù)問題最小平方范數(shù)問題：范數(shù)，最優(yōu)解滿足：絕對值和最小問題：范數(shù)，原問題可轉(zhuǎn)換為LP問題：最小罰問題：15正則逼近二元矢量優(yōu)化問題描述：正則化問題： 最優(yōu)解描述了兩分量的一條折中曲線。16正則逼近Tikhonov正則化問題： 為二次優(yōu)化問題： 最優(yōu)解的形式：17正則逼近Tikhonov光滑正則化問題： 為二階差分算子：回歸問題的稀疏逼近18問題描述：稀疏性條件可轉(zhuǎn)換為范數(shù)：近似問題轉(zhuǎn)化為凸問題：壓縮感知方法假設(shè)信號在某種基下具有稀疏表示

其中是稀疏的。則對信號進(jìn)行測量，得到測量值，當(dāng)和滿足約束一致性條件時(shí)，優(yōu)化問題

的最優(yōu)解以接近1的概率可恢復(fù)得到信號。近似問題為凸優(yōu)化問題1920信號復(fù)原已知加噪信號： 信號復(fù)原問題的描述： 函數(shù)為正則函數(shù)或光滑函數(shù)。21信號復(fù)原22信號復(fù)原23信號復(fù)原24魯棒逼近問題描述：隨機(jī)魯棒逼近：為隨機(jī)變量，逼近問題轉(zhuǎn)換為最小化期望例： 隨機(jī)魯棒逼近為： 轉(zhuǎn)換為：25隨機(jī)魯棒逼近為隨機(jī)變量： 最小平方隨機(jī)魯棒逼近為： 轉(zhuǎn)換為： 其中26最壞情況魯棒逼近考慮，最壞情況魯棒逼近為： 若為有限集，可轉(zhuǎn)換為：函數(shù)擬合已知一函數(shù)族：函數(shù)用函數(shù)族擬合可表示為：函數(shù)族通常稱為基函數(shù)。基函數(shù)可以張出一個定義域上的函數(shù)子空間。向量稱為函數(shù)空間中的系數(shù)向量。27函數(shù)擬合多項(xiàng)式基函數(shù)三角基函數(shù)28函數(shù)擬合與內(nèi)插的約束條件內(nèi)插點(diǎn)約束Lipschitz約束一階微分約束二階微分約束29函數(shù)擬合問題最小化范數(shù)函數(shù)擬合：給定m個指定點(diǎn)，優(yōu)化問題：例：（多項(xiàng)式擬合）給定m組點(diǎn)，擬合多項(xiàng)式函數(shù)求解優(yōu)化問題

其中30傳統(tǒng)的信息獲取和處理過程受采樣定理的影響，需要先對信號進(jìn)行不低于最高頻率兩倍頻率進(jìn)行采樣，然后再進(jìn)行其他處理。信號壓縮根據(jù)信號之間存在相關(guān)性的特性，通過去除相關(guān)性達(dá)到數(shù)據(jù)壓縮的目的。理論上而言，通過那奎斯特采樣定理對信號進(jìn)行采樣太“保守”了。能否直接將采樣與去除相關(guān)性融合在一起完成？壓縮感知簡介31壓縮感知簡介壓縮感知思想由Cadanes和Donoho等人在2006年正式提出DonohoDL.Compressedsensing.IEEETransactionsonInformationTheory,2006,52(4):1289-1306CandésE,RombergJ,TaoT.Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation.IEEETransactionsonInformationTheory.2006,52(2):489-509具有稀疏表示的信源可以直接聯(lián)合采樣和壓縮，在編碼端進(jìn)行簡單的處理，以達(dá)到壓縮編碼的目的。32壓縮感知簡介信源進(jìn)行壓縮感知編碼的基本框架壓縮感知包括三個主要部分：稀疏表示、壓縮傳感測量和解碼重構(gòu)。33信號的稀疏表示定義：如果一個信號中只有少數(shù)信號不為零，則稱該信號是稀疏的。自然信號的時(shí)域表示通常是不稀疏的，但在某些變換域內(nèi)是稀疏的。設(shè)長度為離散時(shí)間域信號，存在一組標(biāo)準(zhǔn)正交基信號可表示為該組基的線性組合，即其中34信號的稀疏表示定義：若中只有個非零元素，則稱為信號的稀疏表示。注：信號的稀疏度與所選擇的基有密切關(guān)系。由于信號的稀疏性，理論上可以用較少數(shù)量的信號數(shù)表示原信號。35信號的壓縮傳感測量壓縮傳感測量是對原始信號的一種測量表示方法。給定一個測量矩陣，則原始信號的測量值為

其中稱為傳感矩陣。由于，因此對信號的重建問題變成一個解欠定方程組的問題，通常存在多解。若加上稀疏性的要求，則該問題成為一個優(yōu)化問題：36傳感矩陣約束等距性條件：對于任意稀疏信號和常數(shù)，若

成立，其中，為中由索引所指示的相關(guān)列構(gòu)成的大小為的子矩陣，則稱矩陣滿足約束等距性條件。通常對于一個稀疏信號，若滿足階約束等距性條件，則可精確重構(gòu)出原始信號。37傳感矩陣約束等距性條件的等價(jià)條件：若和不相關(guān)，則滿足約