压缩感知及算法


ISSN1009-3044
第年7月)电脑知识与技术7卷第Knowledge19期(2011ComputerandTechnology
Vol.7,No.19,July2011.E-mail:eduf@cccc.net.cn电脑知识与技术ComputerKnowledgeandTechnologydoc.guandang.net快速L1范数最小化算法的性能分析和比较
刘杰1,2,李昆仑3
(1.南昌大学信息工程学院,江西南昌330031;2.91388部队92分队,广东湛江524001;3.南昌大学科学技术学院,江西南昌330029)
摘要:随着新兴压缩传感(CompressiveSensing,CS)理论的出现,使用L1范数最小化(L1-min)算法进行信号处理和优化成为近几年的热门课题,由于传统的求解方法对于大规模数据的处理效率很低,例如内点法,越来越多的快速L1-min算法被提出,这些算法在速度和处理效果上都各有优势,该文首先介绍了L1-min算法以及影响算法效率的主要因素,然后通过实验数据对五种快速L1-min算法在处理大规模数据时的性能进行分析和客观评价。
关键词:L1范数;同伦算法;迭代收缩阈值;近端梯度;增广拉格朗日乘子;梯度投影
中图分类号:TP391文献标识码:A文章编号:1009-3044(2011)19-4641-03
ThePerformanceAnalysisandComparisonforFastL1-MinimizationAlgorithm
LIUJie1,2,LIKun-lun3
(1.InformationEngineeringCollegeofNanChangUniversity,Nanchang330031,China;2.Branch92ofNo.91388Army,Zhanjiang524001,China;3.ScienceandTechnologyCollegeofNanchangUniversity,Nanchang330029,China)
Abstract:Withtheemergenceofnewcompressivesensingtheory,L1-normminimizationalgorithmusedinprocessingandoptimizingsignalshasbecomeahottopicinrecentyears,becausetheconventionalalgorithms,forexample,interior-pointmethod,areinefficientinsolvinglarge-scaledata.MoreandmorefastL1-minalgorithmshavebeenproposed,allofwhichhavetheirownadvantagesinspeedandeffect.ThispaperfirstintroducestheL1-minalgorithmsandthemainfactorsaffectingtheefficiencyofthealgorithms,andthenintroducesthepresentfivemajorfastL1-minalgorithms.Finally,basedontheexperimentaldata,itanalyzesandgivesanobjectiveevaluationtotheperformanceofthesefastalgorithmswhendealingwithlarge-scaledata.
Keywords:L1norm;homotopy;iterativeshrinkage-thresholding;proximalgradient;augmentedlagrangemultiplier;gradientprojection
随着科技的进步,人们对信息需求量的要求越来越高,携带信息的信号带宽越来越宽,在传统的信号处理工程中,由于Nyquist采样定理要求信号的采样率不得低于信号带宽的2倍,因此对带宽信号处理的困难日益加剧。另一方面,在实际应用中,为了降低存储、处理和传输的成本,人们常采用压缩方式以较少的比特数表示信号,大量的非重要的数据被抛弃,这种高速采样再压缩的方式浪费了大量的采样资源。为了更高效的处理这些数据以及最大限度的节省存储和传输的成本,D.Donoho和E.Candes在相关研究的基础上于2004年正式提出了压缩传感的概念[1-2]。压缩感知理论对信号的采样、压缩编码发生在同一个步骤,利用信号的稀疏性,以远低于Nyquist采样率的速率对信号进行非自适应的测量编码,根据少量的测量编码信号,通过求解凸优化问题就可以实现信号的精确重建。
由于最优重构信号的求解计算复杂度很高,所以大多数研究聚焦在寻找可接受复杂度下的近似解,即次优解[3]。求次优解有两个基本方法,一是匹配跟踪算法(MP),它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近。二是基跟踪算法(BP),它是把L0范数放宽到L1范数通过线性规划求解的。基跟踪算法比匹配跟踪算法所求的解更加精确,但是需要更高的计算复杂度,为了克服这一缺点,越来越多的快速L1-min算法被提出。例如同伦算法、迭代收缩阈值、近端梯度、增广拉格朗日乘子和梯度投影算法。本文对这几种算法和传统的原始对偶内点法进行分析比较,以实验数据为依据,针对不同的使用环境,分析每种算法在运算速度和重构正确率两方面各自的优缺点。
1L1-min问题
假定存在一个未知信号x0∈Rn,一个传感矩阵A∈Rd×n,一个测量向量b∈Rd(d<n),A是满秩矩阵同时存在b=Ax0的关系,通过求上述线性方程组得出x0。因为测量向量b的维数d小于未知信号x0的维数,线性方程组是欠定的,一种传统的方法是通过最小二乘法找出线性方程组(1)的最小L2范数解,但是这种方法计算量非常大。
(1)
由压缩传感理论可知,当x0足够稀疏(稀疏度为x0中非0值的个数k与维数n的比值k/n)同时传感矩阵A是不相关的情况下,通过求解最小L1范数能够准确的得到x0[4-5]。所以(1)式可以转换成下列的式子。
(2)
式2就是L1-min问题的基本形式,在实际使用中由于噪音误差e的存在,将式子b=Ax改写成b=Ax+e,假定误差e满足||e||2<收稿日期:2011-05-15
本栏目责任编辑:唐一东人工智能及识别技术4641
快速L1范数最小化算法的性能分析和比较_专业资料。随着新兴压缩传感(Compressive Sensing,cs)理论的出现,使用L1范数最小化(L1-min)算法进行信号处理和优化成为近...
再看一下信号处理领域的Sparse,我们应该熟悉JPEG跟JPEG2000的区别吧,JPEG的核心... 快速L1范数最小化算法的... 3页 1下载券 L1范数最小法粗差探测与... 5...
快速L1范数最小化算法的性... 3页 2财富值 l_1范数最近邻凸包分类器在....(L1CHDD)¥f11NN算法、SVM算法的比较与分析L1 观测样本按照步长R=5进行抽取m=...
快速L1范数最小化算法的... 3页 1下载券 复杂机械系统动态特性分... 130...最小二乘类辨识算法的性能分析 9.1 最小二乘类辨识算法的收敛速度分析 9.1...
基于L1范数稀疏距离测度... 43人阅读 7页 2.00 快速L1范数最小化算法的... 249人阅读 3页 1.00 超定线性方程组极小l1范... 26人阅读 3页 ...
基于L1范数主成分分析的颅脑图像恢复_天文/地理_自然科学_专业资料 暂无评价
进行粗差探浏与定位通过 实例 对两种方法进行了比较得到一些有用的结论关 镶词...范数最小法粗差探测与定位的研究 一 7 用 单纯 形 算法 求解线性规划问题 6...
内点法基于主对偶内点框架,通过迭代方法求取稀疏解,其性能没有梯度下 降算法... lasso算法 4页 免费 快速L1范数最小化算法的... 3页 1下载券...
较其它方 法直观, 算法简单, 区间方法过于复杂, 无最优解 区间的检验比较麻烦...2 1 1 -1 2 -1 -1 1 2 3 求该方程组的极小 l1 范数解。 分析与解...
热门文档