【作者】 谢志鹏；

【导师】 陈松灿；

【作者基本信息】 南京航空航天大学 ， 计算机应用技术， 2012， 博士

【摘要】 压缩感知(Compressive Sensing)包括压缩采样(Compressive sampling)与稀疏重构(Sparsereconstruction)。压缩采样通过随机投影获得降维的观测数据，是一种新型的压缩采样方法，适用于核磁共振成像(MRI),超宽带信号处理，天文图象复原等海量数据实时采集与处理领域。稀疏重构利用信号的稀疏性，由低维观测恢复高维稀疏信号。稀疏重构算法的设计与分析已成为压缩感知的研究热点。现有的大规模稀疏重构算法主要包括三类:匹配追踪(Matching pursuit),迭代式硬阈值与L1范数最优化方法。本文对这三类算法进行了拓展性的研究、分析与实现。本文的主要工作包括：1)提出了压缩感知匹配追踪(compressive sensing matching pursuit)算法CSMP。其重构s稀疏信号的充分收敛条件是3s阶约束等距常数不超过0.23,由此放宽了匹配追踪的收敛条件,加快了收敛速率。针对大规模稀疏信号重构，该算法提供的矩阵向量乘算子可进行投影测量子集与稀疏基子集的选择，因此可利用离散余弦变换测量算子与小波变换稀疏基算子，避免显式存储大规模矩阵。2)提出了基于Barzilai-Borwein步长的稀疏约束迭代式硬阈值(Sparsity constrained IterativeHard thresholding with Barzilai–Borwein step size)算法SCIHTBB.该算法包含单调与非单调两个版本。基于非对称约束等距性质进行了相应的收敛分析.针对未知稀疏度问题，利用割线法实现了自适应稀疏度检测。SCIHTBB可应用于组(Group)稀疏、非负稀疏与矩阵补全(matrix completion)。3)设计并分析了一种稀疏重构算法FPSP3。该算法包含3个要素:不动点迭代(Fixed Pointiteration),SPG2非单调线搜索及热启动技术。由前向后向算子分裂推导出最优解的不动点迭代，并将该迭代分解为前向梯度步与后向邻近步。引入邻近算子表明后向邻近步对应软阈值收缩.通过证明梯度算子逆是强单调的从而获得收敛步长条件。采用SPG2非单调线搜索因而显著加快了不动点迭代收敛效率。在稀疏重构实验中将该算法与L1范数方法GPSR,SPARSA,SPGL1进行比较，结果表明FPSP3具有运算速度与重构精度的优势。4)提出了对偶交替方向乘子法(Dual Alternate Direction Multiplier Method)算法DADMM.其通过将交替方向乘子法（ADMM）运用于原始稀疏重构问题的对偶形式发展而得,并且形成了一个灵活的稀疏罚框架，可处理各种Lasso型稀疏罚，包括Lasso,Group Lasso,SparseGroup Lasso及Overlapping Group Lasso.最后理论上通过Douglas Rachford算子分裂法证明了其收敛性，实验比较验证了DADMM的快速计算效率。更多还原

【Abstract】 Compressive Sensing consists of compressive sampling and sparse reconstruction.Compre-ssive sampling acquires the dimension-reduced observation data by random projections andturns out to be a novel compressed sampling technology, which can be applied to real-timeacquisition and recovery of massive data, i.e., Magnetic Resonance Imaging, Ultra-WidebandSignal Processing and Astronomic Image Recovery. Sparse reconstruction exploits signal’ssparse feature thereby recovering the original high-dimension signal from the low dimensionalobservations. Sparse recovery algorithm is the active research area of compressive sensing.Large–scale sparse recovery algorithm mainly includes three classes: Matching pursuit,iterative hard thresholding and L1norm optimization methods. This paper expands the study,analysis and implementation of aforementioned three type methods.The major works in thispaper are listed as following:1)Proposing the algorithm named Compressive sensing matching pursuit(CSMP). It has theguarantee to recover s-sparse signal provided that3s order Restricted Isometry Constant(RIC)is less than0.23, which relaxes the RIC condition for recovering s sparse signal by matchingpursuit and improves the convergence speed. In order to adaptfor large scale sparse recovery,matrix-vector multiplication operator is equipped to select subsets of both random projectionmeasurements and sparse bases, therefore being able to utilize discrete cosine transform andwavelet transform and avoid explicit storage of large scale matrix.2)Proposing the algorithm named SCIHTBB(Sparsity constrained Iterative Hard thresholdingwith Barzilai–Borwein step size), which has Monotone and Non-Monotone versions.Convergence analysis are developed respectively based on asymmetrical restricted isometryproperty. To tackle the unknown sparsity problem, an adaptive sparsity framework is presentedutilizing secant method. Extensions are provided to handle group sparsity, non-negative sparsityand matrix completion.3) Design and analysis of the algorithm named FPSP3, which has three components includingfixed point iteration, the SPG2nonmonotone line search and warm start skill. The fixed pointiteration is derived from forward backward operator splitting and is decomposed into forwardgradient and backward proximal steps.The introduction of proximity operator indicates backwardproximal step reducing to soft-thresholding thrinkage. Convergent step-size condition is obtainedby proving the strong monotonicity of inverse of gradient operator. The use of nonmonotone linesearch SPG2significantly speed up the covergence of fixed point iteration. In sparse recoveryexperiment, the comparison with L1norm methods GPSR,SPARSA and SPGL1shows thatFPSP3has the advantages of speed and recovery accuracy.4) Proposing the algorithm named DADMM(Dual Alternate Direction Multiplier Method),which is obtained by applying ADMM(Alternate Direction Multiplier Method) to the dual formof primal sparse recovery problem. DADMM is a flexible framework for sparse penalty and hasthe capability to handle various lasso-style sparse penalty, including lasso, group lasso, sparse group lasso and overlapping group lasso. The convergence analysis of DADMM is developedbased on Douglas Rachford operator splitting technology.The experimental comparisions verifythe highly computational efficiency of DADMM.更多还原