摘 要

当下是信息爆炸的时代，和以前相比，以前大家只能飞鸽传书，人力传达信息。现在我们有了手机，卫星等各种先进工具。做到了无论身处何地，只要有信号，就能马上传达我们给别人的信息。面对当下数量如此庞大的信息，怎么样使它们能被更高效更准确的传达就成了我们的主要任务。随着时代的进一步发展，稀疏表示，压缩感知等相关理论被提了出来。这些理论都在贯彻一个思想：简化一个信号的表示，争取用部分内容去准确表示整个信号。而完成这个想法的方法就是通过范数最小化问题去解决，在这里面，L1范数最小化问题最具有典型性和广泛的适用性。但目前常用的解决L1范数最小化的问题方法是通过迭代，用时较长，准确度有时不会太高。

在上述的背景下，提出了本文的毕设课题：在超平面约束条件下，找到L1范数最小化的解析解。具体做法如下：相对于传统的L1范数求解通过迭代方式完成，对大规模数据情况下，问题的求解只能是近似解，而且在规定的步数内如果仍不收敛，此时的解尚不满足次优的条件，精度更是无法保证。因此，本文提出了一种解析的计算方法，理论证明了在点到超平面的距离及投影的解析计算方法，相对于已有的迭代方法而言，不仅精度高，而且求解速度更快。最后，在MATLAB的仿真实验上，以线性规划和L1最小化范数的经典求解方法——同伦法为参照对象，从计算时间和计算精度两个方面进行实验对比，进一步验证了提出方法的有效性和正确性。

关键词：L1范数最小化；解析解；迭代算法；MATLAB；

An Analytical Solution for L1 Norm Minimization Problem

ABSTRACT: Now this is the era of information explosion, compared with the previous work, we can only convey information by pigeons or human convey information. Now we have cell phones, satellite and other advanced tools. As long as there is signal, we can immediately convey information we want to give to others no matter where. Facing such a large number of information, how to make them to be more efficient and convey accurately become our main task. With the further development of the era and sparse representation, compression perception and related theory are raised. These theories are to implement an idea: simplify the representation of a signal, using part of the signal to accurate the entire signal. And if we want to complete the idea, the method is through the norm minimization problem. In this idea, The L1 norm minimization problem is the most typical and it has extensive applicability. But the common method of L1 norm minimization is through iteration, it takes longer and sometimes

has no high accuracy.

Under the above background, we put forward the subject of this project: A kind of analytical calculation method about L1 norm minimization problem.

L1 norm minimization problem is mainly introduced in this paper and we put forward some relevant background and application about it, as well as the current mainstream research to this problem and performance comparison between these methods, then give the analytic solution of theoretical derivation, and carry on the experimental comparison and iterative algorithm by MATLAB, at last, get the relevant conclusions.

Key words: the L1 norm minimization; Analytical solution; Iterative algorithm; MATLAB;

目 录

第1章 绪论 - 4 -

1.1课题背景 - 4 -

1.2课题意义 - 5 -

1.3 国内外研究现状 - 6 -

1.4 本文主要内容 - 6 -

第2章 L1范数最小化问题研究 - 7 -

2.1 L1范数最小化求解意义 - 7 -

2.2常见的L1范数最小化求解方法 - 8 -

2.3常见快速求解方法的性能比较 - 9 -

2.3.1无噪音误差情况下的比较 - 9 -

2.3.2 有噪音误差情况下的比较 - 10 -

2.3 其他相关迭代算法的理论基础 - 11 -

2.3.1 原对偶内点法解决 - 11 -

2.3.2 迭代收缩算法解决 - 12 -

2.3.3 同伦算法 - 13 -

2.4 L1范数最小化的一些应用问题 - 13 -

2.4.1 在曲线族重构上的应用 - 13 -

2.4.2 在人脸识别上的应用 - 14 -

第3章 L1范数的解析计算方法 - 16 -

3.1 解析解的理论推导 - 16 -

3.2 线性规划求解方法 - 17 -

3.3 解析解结论分析 - 19 -

第4章 实验验证 - 20 -

4.1实验对比设计 - 20 -

4.2 比对代码 - 21 -

4.3实验验证 - 23 -

第5章 总结与展望 - 29 -

5.1 总结 - 29 -

5.2 展望 - 29 -

致谢 - 30 -

参考文献 - 31 -

第1章 绪论

最近这些年，学者发现了用冗余的基元素集合来表示信号能够取得更好的结果，在需要处理大量信号时，我们理性的状态是可以有一种简化信号的方法去准确表示原始信号，这就提出了信号的稀疏表示理论，这种颠覆性的理论与传统用正交基来表示信号有很大区别，传统的信号采样需满足香农定理，即采样频率应该大于等于模拟信号频谱中最高频率的2倍。2006年，Candes证明了当信号可压缩时，可从部分傅里叶变换系数准确重构初始信号，这为压缩感知奠定了理论基础，之后他们几人在上面基础上正式提出了压缩感知的说法。根本思想是将压缩与采样融合进行，首先采集信号的测量值，再由重构算法将这些测量值还原原始信号。这种信号的稀疏重构可以归结为一个非线性L0范数优化问题，但这问题本身是个NP难问题。所幸的是，Donoho证明了L0范数最优化问题在一定条件下可以抓换成L1范数最优化问题 ，L1范数最优化问题是个典型的可以用线性规划有效解决的凸优化问题，所以目前主要用L1范数最小化去重构信号的稀疏表示。基于此提出的稀疏重构的分类方法SRC即：待测样本能用从相同的基获得的训练样本线性表示。它已在实验中证实无论是有噪音还是无噪音的情况下，它对人脸识别的效果均比当前的识别算法好。

虽然L1范数最优化问题目前已被广泛应用在稀疏表示、压缩感知、图像处理等领域。但是已有的L1最小化方法只能通过迭代计算，因而只能获得问题的近似解。本文针对L1范数最小化问题，约束条件限定在超平面上时，期望能够获得解析解，且所讨论的问题能够应用到分类器设计中。

1.1课题背景

当下，各种信号变换技术在信号处理领域占有重要地位，随着这些技术的飞速发展，人们越来越要面对比如高分辨率图像处理，脑功能数据分析等高维信号处理问题，于是关于信号稀疏表示的方法就被提的越来越多。稀疏表示根据信号结构特征将给定信号在冗余基上进行分解，能在变换域上合适的选择一些少量的基来准确表示初始信号，从而有效的解释了信号的本质，有利于对信号的集成处理，降低处理信号的成本。