稀疏恢復(fù)與稀疏優(yōu)化的_1極小化理論及其計算.pdf

1、根據(jù)模型的低復(fù)雜性結(jié)構(gòu)（如向量的稀疏性、矩陣的低秩性等），如何高效地從病態(tài)的線性逆問題中唯一且穩(wěn)健地恢復(fù)出特定的信息是當(dāng)代應(yīng)用與計算數(shù)學(xué)家、工程技術(shù)人員、以及統(tǒng)計學(xué)家們共同關(guān)心的重要問題.由于其普遍性，該問題在以稀疏恢復(fù)與稀疏優(yōu)化為重點內(nèi)容的壓縮感知、圖像/信號處理、機(jī)器學(xué)習(xí)、大數(shù)據(jù)處理、高維統(tǒng)計等領(lǐng)域均有重大的理論與應(yīng)用價值.本文圍繞稀疏恢復(fù)和稀疏優(yōu)化的l1極小化理論和計算展開研究并做出了以下四個主要的創(chuàng)新性結(jié)果：
　　第一是關(guān)

2、于l1極小化的稀疏恢復(fù)條件的研究.l1極小化解的唯一性和穩(wěn)健性條件是稀疏恢復(fù)理論的核心內(nèi)容，文獻(xiàn)中已存在大量的相關(guān)工作，如連貫性條件、零空間條件、RIP條件等等，這些工作共同關(guān)心的是條件的充分性而非必要性，同時，驗證這些條件是否成立的有效算法非常匱乏.針對這些問題，本文運(yùn)用原對偶思想研究了對偶子條件，證明了該條件不僅是充分的還是必要的，并且可用來分析大量的l1極小化相關(guān)模型，例如l1分析極小化模型、可分解范數(shù)極小化模型、度規(guī)函數(shù)極小化模

3、型等等.由于對偶子條件將l1極小化解的唯一性和穩(wěn)健性的分析轉(zhuǎn)化成滿足特定條件的對偶子存在性的討論，從而可設(shè)計算法驗證特殊對偶子的存在性，以判斷l(xiāng)1極小化解的唯一性和穩(wěn)健性，基于這一思路本文給出了相應(yīng)的驗證算法.
　　第二是關(guān)于結(jié)構(gòu)隨機(jī)矩陣限制特征值的研究.隨機(jī)矩陣是壓縮感知和數(shù)據(jù)降維問題中的重要分析工具.相對于一般的隨機(jī)矩陣，結(jié)構(gòu)隨機(jī)矩陣的優(yōu)勢是具備低復(fù)雜度、低存儲的快速算法，如結(jié)構(gòu)隨機(jī)循環(huán)矩陣與結(jié)構(gòu)隨機(jī)Fourier矩陣均可利用

4、快速Fourier算法進(jìn)行矩陣向量乘法.基于最新的解耦技術(shù)和矩陣值Bernstein不等式以及Laplace變換技術(shù)，本文針對一類列向量帶隨機(jī)符號的隨機(jī)循環(huán)矩陣證明了聚中性質(zhì)，進(jìn)而推導(dǎo)了基于該類隨機(jī)矩陣的Johnson-Lindenstrauss引理，在某些參數(shù)范圍內(nèi)，該引理優(yōu)于當(dāng)前文獻(xiàn)中最好的結(jié)果.新的理論結(jié)果可用于隨機(jī)矩陣RIP性質(zhì)和一致稀疏恢復(fù)條件的研究.
　　第三是關(guān)于兩類經(jīng)典的稀疏優(yōu)化算法的研究.線性Bregman算法和

5、奇異值閾值算法分別是壓縮感知和矩陣補(bǔ)全中最有效的算法之一，這兩類算法的主要缺陷是參數(shù)的選擇以及算法的加速缺乏理論依據(jù).為了克服這些缺陷，一方面，本文提出了強(qiáng)凸化的模型并推導(dǎo)了算法中參數(shù)的估計公式；另一方面，從強(qiáng)凸化模型出發(fā)，在近似點算子理論的框架下，利用對偶分析的思想提出了對偶梯度算法及其Nesterov加速格式.傳統(tǒng)的觀點認(rèn)為梯度法的全局線性收斂性依賴于目標(biāo)函數(shù)的強(qiáng)凸性，然而本文的研究表明限制強(qiáng)凸性質(zhì)（嚴(yán)格弱于強(qiáng)凸性的新型函數(shù)性質(zhì)）是

6、保證全局線性收斂的充分必要條件.新的概念不僅突破了傳統(tǒng)的觀念，還豐富了凸分析與優(yōu)化的相關(guān)內(nèi)容.
　　第四是關(guān)于近似線性迭代重加權(quán)算法的研究.首先，總結(jié)出了一類非凸非光滑的最優(yōu)化問題，該問題囊括了本文涉及到的幾乎所有凸型和非凸型的l1極小化模型；其次，結(jié)合近似線性化技術(shù)和迭代重加權(quán)思想以及函數(shù)光滑化技術(shù)，提出了求解該類問題的近似線性迭代重加權(quán)算法；最后，利用Kurdyka-Lojasiewicz性質(zhì)并定義局部梯度Lipschitz性

7、質(zhì)，證明了新提出的稀疏優(yōu)化算法的全局收斂性.值得一提的是，本文提出的算法是第一個具有全局收斂性的非凸非光滑的迭代重加權(quán)算法，可廣泛應(yīng)用于大量非凸非光滑模型的求解.
　　本文的結(jié)尾總結(jié)了七個將來的研究方向：凸型優(yōu)化與分析的理論和應(yīng)用、隨機(jī)采樣與投影的技術(shù)和理論、基于高維幾何的高維估計理論、面向大規(guī)模問題的次梯度算法、非凸優(yōu)化算法及其全局收斂性、大數(shù)據(jù)背景下的高效并行算法、以及隨機(jī)化算子分裂和原對偶方法，并遺留了三個公開問題.作者相信