英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
第一章 序言
线性代数的中心成就就是对线性方程组解的问题的彻底考查。明确的、永恒的、深厚的结果给这个科目一个完全稳定的外观。线性方程组是很多工程发展和解决方案中的核心工程，大多数知识几乎成功的在应用系统中使用。令人惊讶的是，在这个很好理解的平台，却有一个不得不用线性系统的稀疏解来解决的只是最近才深入的探索的初级问题，我们会发现这个解有很令人惊讶的答案，它促进了很多的实际发展。在这一章中我们应该集中精力认真的定义这个问题，为在以后的章节中的问题答案做好准备。
1.1欠定线性系统
设有一个矩阵（），定义一个欠定线性系统方程组。这个系统比等式有更多的未知，如果b不在矩阵A的列数范围之内，它或许没有解，或许有无限多解。为了避免没有解的不规则性，我们以后应该设A是一个满秩矩阵，意味着它的列向量跨度了整个空间。
在工程学中，我们经常遇到用公式表示的问题，就像这个欠定线性方程组一样。以图像处理为例，考虑图像放大问题，在这一个未知的图像却经历了模糊和缩小的处理，结果是给出了一个低质量的缩小的图像b。矩阵A代表了这个降级的操作，我们的目的是从给定的b中修复原始图像x。显然，会有很多图像x来解释b,在这些图像中肯定有一些比另一些看起来好一些。我们怎么来找到合适的图像x呢？
1.2规则化
在上面的例子和假定有同样构想的许多其它问题中，我们希望得到一个唯一的解，事实上它们很多都代表了同一个障碍。想要减少得到一个定义明确的解的选择，是需要额外条件的。一个常见的方法就是规则化，优先考虑引进一个能求出x的解的有利条件的函数，定义一个一般的优化问题
（1.1）
现在我们可以得到由决定的解的种类。返回图像放大的例子，函数通常喜欢使用平滑的或者更好是分段平滑的图像。
关于最著名的选择就是平方欧几里德范数。这个问题源于一个唯一的实数解—所谓的最小形式解。用拉格朗日乘子，我们定义拉格朗日算符：
(1.2)
在这里lambda;是约束集合的拉格朗日乘子。用x来引出，得到这个必须条件
(1.3)
那么这个结果就得到了并且作为（1）
（1.4）
把这个解插入到约束中，导出
（1.5）
将这个分派给等式（1.4）给出了著名的封闭形式的伪反转解。
(1.6)
注意因为我们假设矩阵A是一个满秩矩阵，矩阵是积极定义的，因此是可逆的。我们也要注意对于更一般的的选择形式（就像是可逆的），这个解的关闭形式的表达式也是存在的
(1.7)
按照同样的一系列步骤。
在工程的各个领域使用很普遍,这主要是由于其简洁的体现和独特的解决方案。在信号与图像处理中,该正规化已经在各种各样的逆问题中传承,信号的表达,和其他地方。然而,这决不是一个真正的最好的选择对于它的服务所带来的诸多问题宣言。在许多情况下,对于数学的简单的将是一种误导的事实，转移工程师作出了对于更好的选择。事实上,图像处理,在经过三十年的尝试之后成功激活(——规范基础)维纳滤波，它最终意识到不同的解决方案，粗略统计学是最基本的选择，在这本书中我们经常遇到的这种。
1.3凸性的诱惑
事实上，通向唯一解是一个更广泛的现象，因为选择任何严格凸性函数是唯一的保障。让我们回想一下凸性的定义,首先为集合,然后为函数。
定义1.1：一个结合是凸面的，如果和，凸面组合也是在内的。
用以上的定义很容易确认函数是凸性的。因此，在等式1.1中形成的优化问题的可行解决方案也是凸性的。为了实现这个目标是凸性优化问题作为一个整体,我们必须增加一个凸性问题作为限制。这一性质的核心定义就给出了：
定义1.2：一个函数：是凸面的，如果和，凸组合点满足
(1.8)
理解上面的定义的另一种方式就是：的题词（用来定义的一个区域）是中的一个凸集。
如果是两次连续可微的，它的衍生就可以用来作为凸面定义的选择：
定义1.3：一个函数：是凸面的，如果并且是只有（1.9）
或者是作为一种选择，当且仅当是正定的时候。
用Hessian的正定的定义来使的平方的形式的凸面的证据变的不重要，因为确实，平方形式是严格的凸面，因为Hessian对于所有的x都是正定的。返回到在等式（1.2）中提到的问题，由于这个约束集合是凸面的以及这个处罚是严格的，这样就能保证有一个唯一的解。
目前，我们细心的选择。然而，对于一个凸面的或者是严格的函数有很多其他的选择。尽管这些关于函数的选择几乎能导出一个关闭形式的解，事实就是它们是严格的凸面的也就意味着一个独一无二的解（2）。也许更重要的是，仔细的选择对于解（1.2）的最优算法已经通过收敛与最优解的所有最小值得到了保证。这些性能使凸性问题在一般的工程中很吸引人，尤其是在信号和图像处理中。又一次，这并不意味着对于非凸性问题就没有解了—它仅仅表达了这样一个意思，就是当处理非凸性问题时，我们应该意识到可能遇到的问题由于它们的缺点。
对于凸性问题的有趣的特别的例子就是对于（用Hessian来查证）的所有的形式。它们被定义为
(1.10)
特别的，形式（显然的，没有p-th3），形式是很有趣也很流行的，考虑了向量x的最大元素并且概括了这些绝对元素。我们应该对有特别的兴趣归因于它倾向于满足这个解—事实是这个将随着这本书的进展而被讨论和确定。
1.4 细看最小化
的选择是凸面的但是不严格，这个很容易通过观察如果和在同一象限（例如，它们有相同的符号模式）中来证实这个事实，那么它们的凸组合在式（1.8）中给出了一个等式。因此，问题
(1.11)
也许不止有一个解。然而，即使这个问题有无限多的可能解，我们可以声称：（1）这些解集中于一个有界限的凸性的集合；（2）在这些解中，存在至少一个至多n个非零解（这个数量是有限制的）。
这个解的凸性集合（在第一个性质中）是直接的，作为一个所有的最优解都有相同的处罚（在这个例子中的长度）的一个事实的直接的结果而停止；两个这样的解的任意凸组合必须给出一个更低的或者相等的处罚，归因于凸性函数，并且因为选出的这两个解是最优的，一个更低的处罚是不可能得到的。因此，两个最优解的任何凸组合仍然是一个最优解。
这个解集是有界限的是所有的给出相同的处罚的最优解的事实的一个直接结果。给出任意两个最优解和，它们之间的距离满足
意味着所有的解都是相近的。
为了显示出第二个性质，让我们假设一个对于()找到的最优解，有个非零解。清晰的，的k列的线性组合是线性相关的，因此存在一个非平凡的向量h将这些列向量和0（例如，h的支持性包含的支持性）相结合，Ah = 0。
我们考虑向量，对于很小的值保证在新向量中没有元素可以再一次改变它。任何值满足都是合适的。首先，这个向量能保证满足线性系统，就象这样，它是对于()的可行解。此外，是假设的最优解，我们还必须假设
我们争辩上面的不等式其实是一个等式。上面的关系可用于的正反两个值，在这函数是连续可微的（所有的向量有相同的符号模式）。因此，就像声称的那样，唯一的可能真实的方式就是如果上面的不等式满足作为一个等式。这个意味着在这些情况下h的加法/减法没有改变解的长度。作为一个例子，如果只有正的元素，那么h的元素将会有正反两方面，而且它们的和为零。更一般的情况，我们应该要求。接下来的步骤就是调整，用这种方式中的一恶搞元素就是无效的，然而却保持了解的长度。我们选择指数i给出最小的比率，并且选择。再后来的向量中，第i个元素是无效的，然而所有的其他的保持了它们的符号和优势，所以有
通过这种方式，我们得到这个优化问题的至多k-1个非零解，（因为它可能有多个列同时等于零），这个过程可以重复，直到k=n.在这种情况下，如果矩阵A是线性相关的，就有可能有的列全为零，这也是有可能的。
从上面我们了解到形式倾向于稀疏解。我们证明的性质已经众所周知，而且被大家认为是线性系统的基本性质，一个倾向于稀疏解的性质。然而,如同我们将看到后来,即使我们对稀疏解很感兴趣，对我们的需要来说，得到n个非零解太多了，并且我们将追求更深层次的稀疏解。
1.5()转换的线性规则
假如在()中，未知量x由代替，在这里都是非负向量，以致u得出在x中的所有的正的元素，其他的是无效的，并且v对于在x中的非负的元素和u的作用是相同的。通过这个替换和表示连锁的向量，很容易看到和因此，在等式（1.11）中提出的()的优化问题能被重新写为
(1.12)
通过这种方式，我们面临一个新的问题，就是经典的线性规划结构，而不是形式的最小化问题。对于()和LP这两个问题来说是等价的，我们必须表明关于x的正反两方面的分解是满足条件的。式（1.12）的解不能是这样：（例如，支持u和v的重叠）
这个很容易通过观察来证实如果在式（1.12）中的最优解中在u和v的第 k列都有非零解（由于过去的约束是整数），然后这两个系数同时乘以负的矩阵A。没有普遍性的损失，如果我们假设，然后通过和来更换这两列，即使通过降低了限制条件，与初始解的最优性相矛盾，但是我们对它的确定性和线性约束性都很满意。因此，支持u、v不重叠，LP确实是等价于()的。
1.6 促进稀疏的解决方案
当我们从的规则化走向的时候，促进了稀疏解的解决方案。用这个原理，我们可以考虑时的形式。必须注意到当时不再是正式形式了，就像是三角不等式不再 满足条件的了。不过,我们应当使用术语规范为这些功能,同时牢记这预订。
这些形式导出了稀疏解吗？为了得到这些形式的表现的摸索，我们来考虑以下问题：假设x是已知的并且它的长度在中。当时让我们找出在中最短的这样的向量。把它作为一个最优问题，表示为
(1.13)
我们应该假设x有一个非零解（我们应该进一步假设这些值都是正的，因为它们的符号并不影响对以下问题的分析）作为向量的主要元素，其他的都是零。我们定义拉格朗日函数为
(1.14)
这个函数是可分隔的，来处理其他的在x中的每一个独立的元素。这个最优解由满足所有的k的给出的，意味着所有的非零元素都被认为是一样的。约束导出了以及由给出的解的形式。因为q lt; p，这意味着当a = 1时最短的形式就得到了，在x中只有一个非零元素。
上述的结果表明当q lt; p对于任何一对和形式，一个单位长度的形式的向量变成在中最短的向量，当它是最可能的稀疏解。上面给出的分析的一个几何解释就是一下的内容：在中的形式的球表面代表了的在（1.13）中所提出的问题的可行的集合。我们在同样的空间中将吹成气球，并且寻找它的第一个有球面的交集。我们得到的结果意味着这个交集就沿着坐标轴，在这个轴线范围内除了一个所有的元素都是零。这个在图1.1中展示。
Fig. 1.1 Demonstrating the fact that a unit-length-norm vector (dashed) becomes shortest in(pgt;q)(solid) when it is the sparsest possible.On the left this is demonstrated for p = 2 and q=1, and the right shows it for p=1 and q=0.5. The dash-dotted curves in both graphs show the reverse claim – maximizing the length leads to the most non-sparse outcome.
说明形式将使这个结果变成稀疏解的另一种说明如下所示：考虑我们已经考虑的问题
(1.15)
形成这个约束定义的等式的线性集合定义了一个解的可行的集合，这些解形成了一个仿射子空间（一个由固定的矢量改变的子空间）。这个改变可由这个系统的任何一个可能的解，来实现。一个A中的零空间中的和其他任何向量组成的线性组合形成了一个可行解。几何学上，这个集合被作为嵌入到空
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[151638]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
