文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 快速L1范数最小化算法的性能分析和比较
侵权投诉

快速L1范数最小化算法的性能分析和比较

压缩感知及算法

快速L1范数最小化算法的性能分析和比较

快速L1范数最小化算法的性能分析和比较

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

第1页

你可能喜欢

  • 算法分析
  • 最小割
  • 密码算法
  • 算法初步
  • 排名算法
  • 算法报告
  • 经典算法
  • 高中算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email