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

摘要：随着新兴压缩传感(Compressive Sensing，CS)理论的出现，使用L1范数最小化(L1-min)算法进行信号处理和优化成为近几年的热门课题，由于传统的求解方法对于大规模数据的处理效率很低，例如内点法，越来越多的快速l1-min算法被提出，这些算法在速度和处理效果上都各有优势，该文首先介绍了L1-min算法以及影响算法效率的主要因素，然后通过实验数据对五种快速L1-min算法在处理大规模数据时的性能进行分析和客观评价。

关键词：L1范数；同伦算法；迭代收缩阈值；近端梯度；增广拉格朗日乘子；梯度投影

中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)19-4641-03

The Performance Analysis and Comparison for Fast L1-Minimization Algorithm

LIU Jie1,2, LI Kun-lun3

(1.Information Engineering College of NanChang University, Nanchang 330031, China; 2.Branch 92 of No.91388 Army, Zhanjiang 524001, China; 3.Science and Technology College of Nanchang University, Nanchang 330029, China)

Abstract: With the emergence of new compressive sensing theory, L1-norm minimization algorithm used in processing and optimizing signals has become a hot topic in recent years, because the conventional algorithms, for example, interior-point method, are inefficient in solving large-scale data. More and more fast L1-min algorithms have been proposed, all of which have their own advantages in speed and effect. This paper first introduces the L1-min algorithms and the main factors affecting the efficiency of the algorithms, and then introduces the present five major fast L1-min algorithms. Finally, based on the experimental data, it analyzes and gives an objective evaluation to the performance of these fast algorithms when dealing with large-scale data.

Key words: L1 norm; homotopy; iterative shrinkage-thresholding; proximal gradient; augmented lagrange multiplier; gradient projection

随着科技的进步，人们对信息需求量的要求越来越高，携带信息的信号带宽越来越宽，在传统的信号处理工程中，由于Nyquist 采样定理要求信号的采样率不得低于信号带宽的2倍，因此对带宽信号处理的困难日益加剧。另一方面，在实际应用中，为了降低存储、处理和传输的成本，人们常采用压缩方式以较少的比特数表示信号，大量的非重要的数据被抛弃，这种高速采样再压缩的方式浪费了大量的采样资源。为了更高效的处理这些数据以及最大限度的节省存储和传输的成本，D. Donoho和E. Candes在相关研究的基础上于2004年正式提出了压缩传感的概念[1-2]。压缩感知理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码，根据少量的测量编码信号，通过求解凸优化问题就可以实现信号的精确重建。

由于最优重构信号的求解计算复杂度很高，所以大多数研究聚焦在寻找可接受复杂度下的近似解，即次优解[3]。求次优解有两个基本方法, 一是匹配跟踪算法(MP)，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近。二是基跟踪算法(BP)，它是把L0范数放宽到L1范数通过线性规划求解的。基跟踪算法比匹配跟踪算法所求的解更加精确，但是需要更高的计算复杂度，为了克服这一缺点，越来越多的快速L1-min算法被提出。例如同伦算法、迭代收缩阈值、近端梯度、增广拉格朗日乘子和梯度投影算法。本文对这几种算法和传统的原始对偶内点法进行分析比较，以实验数据为依据，针对不同的使用环境，分析每种算法在运算速度和重构正确率两方面各自的优缺点。

1 L1-min问题

假定存在一个未知信号x0∈Rn，一个传感矩阵A∈Rd×n，一个测量向量b∈Rd(d

（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

（3）

2 快速L1-min算法的比较

L1-min问题是一个典型的凸优化问题，目前存在很多种求解方法。在实际使用中，由于信号维数的增加造成计算量特别大，为了提高使用效率，许多快速L1-min算法被提出，为了分析这些算法的使用性能，下面使用不同的虚拟信号对各种算法进行比较。由于目前快速L1-min算法非常多，无法全部进行比较，本文只对常见的五种快速L1-min算法（同伦算法(Homotopy)[6]、迭代收缩阈值(IST)[7]、近端梯度(PG)[8-9]、增广拉格朗日乘子(ALM)[10]、梯度投影(GP)[11]）和原始对偶内点法(PDIPA)[12]进行分析。

2.1 无噪音误差情况下的比较

这个试验主要是在没有干扰的情况下测试每个算法在重构稀疏信号时的正确率。图1表示在正确率为95%的情况下ρ-δ的分布情况，ρ=k/n∈(0,1)表示未知信号x0的稀疏度，δ=d/n∈(0,1 )表示降维比率，在试验中d=1000，A是一个高斯随机矩阵，符合标准正态分布，同时归一化列向量。对于每一个固定的(ρ,δ)点，x0都是统一产生的随机信号，每一个非0项都符合标准正态分布，整个向量通过L2范数归一化。在相同δ的情况下，ρ越大，说明算法重构稠密信号的能力越强。

从图1可以得出以下结论：

在不考虑速度和噪音的情况下，PDIPA的正确率是最高的，尤其是在信号变得稠密的情况下。GP和Homotopy算法的效果基本一样，在降维比率低的情况下，Homotopy算法比GP算法效果更好，这两种算法和PDIPA算法的效果最接近。IST和ALM算法效果基本一样，和上述三种算法相比，它们的正确率明显偏低。在这个实验中，PG算法的效果是最差的。

2.2 有噪音误差情况下的比较

实际使用中都会存在不同程度的噪音影响，为了清楚的比较不同算法在噪音影响情况下的性能，实验主要分两方面进行。

首先测试在低稀疏度情况下的性能，n=2000和稀疏度ρ=k/n=0.1是固定的，改变维数d的大小，d∈[800,1900]。

图2 图3 图4

图2和图3是运行时间随维数d变化的关系图，图4是计算误差随维数d变化的关系图。从实验可以得出如下结论：

PIDPA算法随着维数的增加，重构误差和运行时间增加的非常快。其余五种算法的效果都不错，Homotopy算法的误差稍微大一点， 在收敛速度方面，GP和Homoptopy算法比PG、IST和ALM算法更耗时，ALM算法的运算速度是最快的。

然后测试在高稀疏度情况下的性能，n=2000和d=1500是固定的，改变稀疏度ρ的大小，ρ=k/n∈[0.1,0.26]。

图5 图6 图7

图5和图6是运行时间稀疏度ρ变化的关系图，图7是计算误差随稀疏度ρ变化的关系图。从实验可以得出如下结论：

PDIPA算法速度上和正确率上比其余五种算法都要差。Homotopy算法随着稀疏度的增加，消耗是时间增加的非常快，误差基本不变，所以Homotopy算法适应于低稀疏度情况下的信号重构。GP、PG、IST和ALM算法随着ρ的增加误差和运算速度基本保持不变。在稀疏度小于0.24的情况下，ALM算法的运行速度是最快的。

通过两方面的对比可以看出在处理信号噪音干扰上，PDIPA算法明显比其余五种快速L1-min算法效果都要差。

3 总结

综上所述，以上五种快速L1-min算法各有优点，在运算速度和正确率两方面，无论是那一种算法都不可能在任何条件下都到达最好。实际的应用当中，我们必须充分考虑重构信号的特点以及应用环境，在运算速度和正确率之间找到平衡点，以到达最好的使用效果。

参考文献：

[1] 石光明,刘丹华,高大化,等. 压缩感知理论及其研究进展[J].电子学报,2009(5):1070-1081.

[2] Donoho D L . Compressed sensing[J].IEEE Trans. on Information Theory,2006,52(4):1289-1306.

[3] 叶志申,张绍钧,黄仁泰.压缩感知理论及其重构算法[J].东莞理工学院学报,2010,17(3):32-35.

[4] Bruckstein A,Donoho D,Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Review,2007.

[5] Candes E, Romberg J, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure and Appl,2006,59(8):1207-1223.

[6] Malioutov D, Cetin M, Willsky A. Homotopy continuation for sparse signal representation[J].In ICASSP,2005.

[7] Daubechies I, Defrise M, Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J].Communications on Pure and Applied Math,2004(57):1413-1457.

[8] Nesterov Y. Gradient methods for minimizing composite objective function[J]. ECORE Discussion Paper,2007.

[9] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].SIAM J.on Im. Sci,2009,2(1):183-202.

[10] Bertsekas D. Nonlinear Programming. Athena Scientific,2003.

[11] Figueiredo M, Nowak R, Wright S. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[j]. IEEE J. Sel. Top. in Sig.Proc,2007,1(4):586-597.

[12] Kojima M, Megiddo N, Mizuno S. Theoretical convergence of large-step primal-dual interior point algorithms for linear programming. Mathematical Programming,1993,59:1-21.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文