英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
第一章
序幕
经典线性代数的一项突出成就是对线性方程组求解问题的彻底研究。结果——明确的，永恒的，深刻的——给主题一个完全固定的外观。由于线性方程组是许多工程开发和求解的核心引擎，因此这些知识在实际应用中得到了成功的应用。令人惊讶的是，在这一广为人知的领域中，有一个基本问题与线性系统的稀疏解有关，这一问题最近才得到深入的探讨；我们将看到，这个问题有令人惊讶的答案，它激发了许多实际的发展。在这一章中，我们将集中精力仔细地定义这个问题，并在以后的章节中为回答这个问题奠定基础。
1.1欠定线性系统
考虑一个nlt;m的矩阵A isin; IRntimes;m，定义方程组Ax=b的欠定线性系统，这个系统比方程组有更多的未知量，因此，如果b不在矩阵A的列范围内，则它没有解，或者有无穷多解。为了避免没有解的异常，我们在下文中假定A是一个满秩矩阵，这意味着它的列跨越整个空间Rn。
在工程中，我们经常遇到这样的问题，即线性方程组的不确定性。作为图像处理的一个例子，需要考虑图像放大问题，其中未知图像经过模糊和缩小操作，最终给出的结果是质量较低，图像较小的b。矩阵A代表退化操作， 我们的目标是从给定的测量值b重建原始图像x。显然，有无限多可能的图像x可以解释b，其中有些看起来比其他的要好。那么我们如何找到合适的x？
1.2正则化
无论是在上面的例子中，还是在其他许多假设相同公式的问题中，我们都希望有一个单一的解决方案，而这些问题中有无限多个是一个主要障碍。为了将此选择限制为一个定义良好的解决方案，需要附加条件。一种常见的方法是正则化，在正则化中引入一个函数J（x），该函数评估潜在解x的可取性，首选较小的值。定义一般优化问题（PJ）：
(PJ ) : minx J(x) subject to b = Ax, (1.1)
现在由J（x）来决定我们可能得到的解决方案。回到图像放大示例，通常使用一个函数J（x），该函数更喜欢平滑或更好的是分段平滑的结果。
最著名的J（x）选择是平方欧氏范数kxk22。由这种选择产生的问题（P2）实际上有一个唯一的解xcirc;，即所谓的最小范数解。利用拉格朗日乘子，我们定义了拉格朗日
（1.2）
lambda;是约束集的拉格朗日乘子。取L（x）对x的导数，我们得到了
part;L(x)
part;x = 2x AT lambda;. （1.3）
|
因此，得到的解为1 |
（1.4）
将此解插入约束Ax=b将导致
（1.5）
将其赋给方程（1.4）可得到众所周知的闭式伪逆解
（1.6）
注意，由于我们假设A是满秩的，矩阵AAT是正有限的，因此是可逆的。我们还注意到，对于形式J（x）=kBxk22（这样BTB是可逆的）的更一般的选择，解的闭式表达式
1.3凸性的诱惑
也存在， （1.7）
遵循同样的步骤。
“t2”在工程的各个领域都有广泛的应用，这主要是由于它的简单性，表现为上述封闭形式和独特的解。在信号和图像处理中，这种正则化经常用于各种反问题、信号表示和其他方面。然而，这决不是一项声明，即“2是它所服务的各种问题的真正最佳选择”。在许多情况下，“2”的数学简单性是一个误导性的事实，它使工程师无法为J（·）做出更好的选择。实际上，在图像处理中，经过三十年的努力，成功地激活了（`2norm-based）维纳滤波器，我们最终意识到，解决方案存在于一个不同的，基于统计的J（·）选择中，这是我们在本书中经常遇到的。
1.3凸性的诱惑
2导致唯一解的事实是一个更广泛现象的表现，因为选择任何严格凸函数J（·）都保证了这种唯一性。让我们回顾一下凸性的定义，首先是集合，然后是函数。
定义1.1。如果forall;x1，x2isin;Omega;和forall;tisin;[0,1]，则集Omega;是凸的，凸组合x=tx1 （1-t）x2也在Omega;中。
使用上面的定义，很容易验证setOmega;={x | Ax=b}是凸的。因此，方程（1.1）中优化问题的可行解集是凸的。为了使优化问题整体上是凸的，我们必须在罚J（x）上加上凸性要求。此类财产的核心定义如下：
定义1.2。如果forall;x1，x2isin;Omega;和forall;tisin;[0,1]，凸组合点x=tx1 （1-t）x2满足
（1.8）
理解上述定义的另一种方法是：J（x）（由{（x，y）| yge;J（x）}定义的区域）的碑文是IRm 1中的凸集。
如果J（·）是连续可微的两倍，其导数可用于凸性的替代定义：
定义1.3。函数J（x）：Omega;→IR是凸的，如果forall;x1，x2isin;Omega;，如果且仅当
（1.9）
或者，当且仅当nabla;[2]J（x1）是正定的。
利用Hessian正定性的定义，使得平方2-范数凸性的证明变得微不足道。实际上，平方2范数是严格凸的，因为这个Hessian对所有x都是严格正定的。回到方程（1.2）中的问题，由于约束集是凸的，并且惩罚是严格的，所以保证了唯一解。
到目前为止，我们已经讨论了选择J(x) = kxk2。但是，还有许多函数J（·）的选择是凸的或严格凸的。尽管J（·）的这些选项很少导致一个封闭形式的解，但它们是严格凸的这一事实意味着一个唯一的解。2也许更重要的是，可以确保精心选择的优化算法来求解（1.2），可以保证收敛到此类优化问题的全局极小值。
这些性质使得凸问题在工程中，特别是在信号和图像处理中具有广泛的应用前景。同样，这并不意味着非凸问题没有价值——它只是说，在处理非凸优化任务时，人们应该意识到可能会遇到的问题，原因是因为它们的不完善。
凸函数的特殊情况是pge;1的所有p-范数（使用Hessian来验证）。这些被定义为
（1.10）
尤其是tinfin;-范数（显然，没有p的3阶次幂）和t1-范数是非常有趣和流行的；tinfin; 考虑向量x的最大项，并且t1求绝对项的和。我们将对t1有特殊的兴趣，因为它倾向于回避解决方案——这一事实将在本书中讨论并确立。
1.4仔细研究t1的最小化
选择J（x）=kxk1是凸的，但不是严格意义上的凸，这一事实很容易通过注意，如果x1和x2在同一象限（即，它们具有相同的符号模式）得到验证，那么它们的凸组合给出等式（1.8）。因此，问题
（1.11）
可能有多个解决方案。尽管如此，即使这个问题有无限多的可能的解决方案，我们也可以声称（i）收集了这些解决方案
1.4仔细研究t1的最小化
在一个有界且凸的集合中，并且（ii）在这些解中，至少存在一个至多n个非零（作为约束数）的解。
解集（在第一个性质中）的凸性是立即产生的，这是由于所有最优解都有相同的惩罚（在这种情况下为t1-length长度）这一事实的直接结果；由于J（x）=kxk1的凸性，这两个解的任何凸组合必须给出更低或相等的惩罚，由于两个选择的解是最优的，所以不可能得到较低的惩罚。因此，两个最优解的任何凸组合也是一个最优解。
解集是有界的，这是所有最优解给出相同高度的惩罚的直接结果，vmin=kxoptk1lt;infin;。给定任意两个最优解x1opt和x2opt，它们之间的距离满足
意味着所有的解决方案都在附近。
为了说明第二个性质，我们假设已经找到（P1）的最优解xopt，kgt;n非零。显然，由xopt线性组合的k列是线性相关的，因此存在一个将这些列组合为零的非平凡向量h（即h的支持包含在xopt的支持内），Ah＝0。
我们考虑向量x=xopt h，因为它的极小值保证了新向量中的任何条目都不会改变它的符号。满足| |le;mini | xopti |/| hi |的任何值都是合适的。首先，很明显，这个向量保证满足线性约束Ax=0，因此，它是（P1）的可行解。此外，由于假设xopt是最优的，我们必须假设
我们认为，上述不平等事实上是一种平等。上述关系适用于t1函数连续且可微的区域中 E的正负值（因为所有向量xopt h具有相同的符号模式）。因此，正如所声称的那样，唯一可能实现这一点的方法是，将上述不平等作为一种平等加以满足。这意味着，在这些情况下加/减h不会改变解的t1长度。例如，如果xopt仅有正条目，那么h的条目应该同时为正和负的，并且总和为零。一般来说，我们应该要求hTsign（xopt）=0。
我们的下一步是调整xopt中的一个条目为空，同时保持解的t1的长度。我们选择给出最小比率| xopti |/| hi |的索引i，然后选择–-xopti/hi。在得到的向量xopt h中，第i个条目为空，而所有其他条目都保留它们的符号，我们还有kxopt hk1=kxoptk1。这样我们得到了一个新的最优解，其中k-1最多不为零（因为可能有多个条目同时为空）。这个过程可以重复到k=n。在这个过程中，只有当A中的列是线性相关的时，才有可能使条目为空，这种情况很少发生。
从上面我们了解到，t1-范数倾向于选择稀疏解。我们所证明的性质是众所周知的，并且被认为是线性规划的基本性质——基本（稀疏）解的一种趋势。然而，正如我们稍后将要看到的，虽然我们对稀疏性非常感兴趣，但将n个非零值视为过于密集而无法满足我们的需求，并且会寻求更深的稀疏性。
1.5（P1）到线性规划的转换
假设在（P1）中，未知的x被替换为x=uv，其中u，visin;IRn都是非负向量，因此u取x中的所有正项，其他项为空，而v对x中的负项也做同样的操作。通过这种替换，通过表示串联向量z=[u T，vT]Tisin;IR2n，很容易看出[4]kxk1=1T（u v）=1Tz，Ax=A（u-v）=[A，-A]z。因此，方程（1.11）中提出的（P1）优化问题可以重新写成
（1.12）
这样，我们就不必最小化t1-范数问题，而要面对一个具有经典线性规划（LP）结构的新问题。为了使两个问题（P1和LP）等价，我们必须证明我们关于x分解为正项和负项的假设是满足的，并且（1.12）的解不能是uTv，0（即u和v的支持重叠）。
可以很容易地通过观察得出以下结论：如果在（1.12）的给定最优解中，u和v中的第k个项都是非零的（并且由于最后一个约束是正的），那么这两个系数用相反的符号乘a中的同一列，就很容易证明这一点。在不丧失一般性的情况下，如果我们假设ukgt;vk，那么通过将这两个条目替换为u0k=uk-vk和v0k=0，我们既满足正性约束又满足线性约束，同时也减少uk-vkgt;0的惩罚，这与初始解的最优性相矛盾。因此，u，v的支承不重叠，LP实际上等于（Pi）
1.6推广稀疏解决方案
随着我们从“t2正则化”转向“t1”时，我们提倡稀疏解。利用这个基本原理，我们可以考虑plt;1的“p-”规范。必须小心，因为tp不再是plt;1的形式规范，因为三角不等式不再存在
1.6推广稀疏解决方案
尽管如此，在记住这些保留的前提下，我们也将使用规范这个术语来描述这些功能。
这些规范会导致更稀疏的解决方案吗？为了了解这些规范的行为，我们考虑了以下问题：假设x已知具有tp的单位长度。让我们在q中找到qlt;p的最短向量。把这作为一个优化问题，内容如下：
（1.13）
我们将假设x有一个非零（我们进一步假设这些值都是正的，因为它们的符号不影响后面的分析）作为向量中的前导项，其余均为零。我们把拉格朗日函数定义为
（1.14）
此函数是可分离的，它独立于其他项处理x中的每个项。
最优解由零个条目给出，假定它们是相同的。对于所有k，constraintxkp-q=Const，这意味着所有非xk p p=1导致xk=a-1/并且该解的q-范数由kxkqq=a1-q/p给出。由于qlt;p，这意味着对于a=1
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409432]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
