英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
附录A 译文
追求算法一实践
现在是时候考虑可靠和有效的解决方法了（Po），因为一种直截了当的方法似乎是无望的。我们现在讨论的方法，似乎没有希望实现，但在具体条件下是可以得出结果的。看问题(Po），
（Po）：求,使得 b=Ax，
人们观察到，未知x是由两个有效的部分组成的，以找到解的支持，而非零值超过这个支持。因此，攻击(Po)数值解的一种方法是关注支持，理解一旦发现，x 的非零值很容易被简单的最小二乘检测到。作为离散性质的支持，寻求它的算法也是离散的。 这一系列的推理导致了贪婪算法的家族，将在下面介绍。
人们观察到，未知x是由两个有效的部分组成的，以找到解的支持，而非零值超过这个支持。因此，攻击(Po)数值解的一种方法是关注支持，理解一旦发现，x 的非零值很容易被简单的最小二乘检测到。作为离散性质的支持，寻求它的算法也是离散的。 这一系列的推理导致了贪婪算法的家族，将在下面介绍。
另一种观点(Po)可以忽略支持，并将未知视为向量 xisin;IR在连续体上。平滑惩罚函数，可以采用连续优化的求解方法(Po)-本章后面介绍的松弛方法采用了这种观点，通过各种形式平滑圆锥曲线，并将修正后的问题作为平滑优化处理。
3.1 贪婪算法
3.1.1 核心理念
假设矩阵 A 有spark(A)gt;2，优化问题(Po)值val(Po)=1（在最优解处）,因此 b 是矩阵 A 某些列的标量倍数，已知该解是唯一的。我们可以通过应用 m 测试来识别这个列。 第 y 个测试可以完成通过最小化 Ɛ(j) =ajZj - b，导致。插入错误表达式，错误就变成
Ɛ(j)=
（3.1）
chy-Schwartz不等式应满足等式，表示 b 和 是平行的。 这一程序需要 O(Mn)命令，这可能被认为是合理的。
根据同样的原理，假设 A spark(A)gt;2，并且已知优化问题具有值 val(Po)=。则 b 是 A 最多行列的线性组合。概括前面的解决方案，人们可能会认为枚举 A 中所有(G)列的=子集，并测试每个。 枚举取。在许多人看来，这在许多步骤中似乎慢得令人望而却步。
贪婪的策略放弃了详尽的搜索，而倾向于一系列局部最优的单期更新。 从 =0 开始，通过保持一组最初为空的活动列，并在每个阶段扩展由一个附加列设置的活动列，构造一个k近似。 在每个阶段选择的列最大程度地减少了原始pound;2 误差，从简单的活动列逼近 b 时。 在构造包括新列在内的近似值后，对残差施误差进行评估；如果它现在低于指定的阈值，则算法三乘。
3.1.2 正交匹配程序
图 3.1 给出了该策略的正式描述及其相关表示法。 这一过程在信号处理的文献中被称为正交匹配-诉讼(OMP)，但在其他领域的其他名称中非常著名（而且使用得更早），见下文。
请注意，扫描阶段给出了以下形式的误差值，这与我们在方程（3.1）中看到的非常相似，
Ɛ(j)= (3.2）
任务：近似(Po)的解： ,服从Ax=b。
参数：我们得到了矩阵 A、向量 b 二误差阈值 s。
初始化：初始化k=0,并设置
初始值
初试残差
初始解决方案支持
主要迭代：将 k 增加 1 并执行以下步骤：
扫描：计算错误 Ɛ(j)= 使用最优选择对所有 j 进行；
更新支持：找到最小化器，为 Ɛ(j)：，Ɛ()lt;Ɛ()，并更新。
更新临时解决方案：计算 ，的最小值服从Support{x}=。
更新剩余：计算 。
停止规则：如果，停止。 否则，应用另一个迭代。输出：所提出的解是 k 次迭代后得到的。
图 1 3.1 正交匹配程序-逼近()解的贪婪算法
=
=
因此，对最小误差的追求实际上等同于对残差 之间最大（绝对值）内积的追求，以及矩阵 A 的归一化向量。
在更新临时解决方案阶段，我们将 项关于x最小化，因此它的支持是 。 我们将表示为大小为 的矩阵，其中包含属于此支持的 A 中的列。 因此，要解决的问题是 的最小化，其中 是向量 x 的非零部分。 解是通过对这种二次形式的导数进行零点化，
(3.3)
在这里，我们使用了 k 迭代中残差的公式，。上述关系表明，A 中的列是支持 S 的一部分,与残差必然正交 。 这反过来意味着在下一次迭代（以及之后）中，这些列将不会再次被选择用于支持。 这种正交化是正交匹配程序算法命名一原因。
可以建议上述算法的一个更复杂和更好的行为变体，其中扫描阶段的每个测试都是作为全最小二乘(L S)进行的，同时考虑所有累积列和候选列，并同时求解所有系数。 在 OMP 中， 次步骤在“-第四步”执行。 这种方法称为 LS-OMP。利用该公式可以使 LS 步骤高效
(3.4)
其中。 表示从A中收集k-1所选列的子矩阵为，我们应该解决的LS问题是
(3.5)
解是通过对上述表达式的导数归零得到的
(3.6)
导致
(3.7)
因此，根据方程（3.4）中给出的公式，如果我们存储了矩阵，然后上述公式变得容易，并导致更新此矩阵的 k 列。一旦找到解决方案，应评估残差，并选择导致最小误差的列。 观察，如果与的列正交，则上述要倒置的矩阵变为块对角线，结果为和。如这意味着前一个解的系数保持不变，并且引入了一个新的非零系数z系数。
残差的评价有数值捷径，但我们不会在这里探讨这一问题。 请注意，上述针对 LS-OMP 中最小二乘任务的递归方法也与加快 OMP 有关，这意味着更新临时解决方案阶段可以变得更有效。
如果传递的近似非零，LS-OMP和OMP方法通常需要时间度次失败；这可能比穷举搜索要好得多，这需要次失败。 因此，一次性短期策略可以比彻底搜索更有效-如果它有效的话！ 该策略可能会严重失败，比如Vladimir Temlyakov构造了一个明确的例子，其中一个简单的“-项表示是可能的，但这种方法产生了一个 n 项（即密集）表示。 一般来说，可以说，在单项时策略中，近似误差总是减少到到可能的，给定起始近似值和单次约束。这一特性使该算法在近似理论中获得了“贪婪算法”的名称。
3.1.3 其他贪婪方法
上述算法上的许多变体是可用的，在精度和/或复杂性上都有改进。 这一类贪婪算法是众所周知和广泛使用的，事实上，这些算法已经在各个领域重新发明。在统计建模的设置中，贪婪的逐步最小二乘被称为正向逐步回归，至少自 20 世纪 60 年代以来一直被广泛应用。当在信号处理设置中使用时，这将被命名为匹配跟踪(MP)或正交匹配程序(OMP)。近似理论家将这些算法称为贪婪算法(GA)，并考虑了它们的几个变体：纯(PGA)、正交(OGA)、松弛(RGA)和弱贪婪算法(WGA)。
MP 算法与 OMP 算法相似，但有一个重要的差异，使它更简单，因此不太准确。 在主迭代中，在扫描和更新支持阶段之后，而不是求解一个最小二乘来重新评估所有系数 ITX，的系数原始条目保持不变， 新系数指的是新成员选择为 。 该算法如图 3.2 所示。
Weak-MP是MP算法的进一步简化，用于支持下一个元素的次优选择。 图3.2中MP算法描述的嵌入，要添加到支持中的下一个元素的最佳选择。从图 3.2 中的 MP 算法描述出发，通过选择任何因子t范围（0， 1]远离最优选择的索引来放松更新支持。该算法如图 3.3 所示。
让我们解释和激励这种方法：我们已经看到计算的内部产品之间的等价性，（最多一个归一化因子），以
及相应的误差Ɛ(j)，其中我们寻求最小值。 而不是寻找最大的内积值，我们满足于第一个发现超过 r 弱阈值。柯西-施瓦茨的不等式
（3.8）
这使得最大可实现的内积上有一个上限。 因此，我们可以计算在扫描阶段开始时，当我们搜索给出最小误差Ɛ(j)的时，我们选择在（0，1）范围内为预先选择的 t 给出的第一个。 上述条件可交替写成
（3.9）
（3.10）
这样，选择的索引清楚地指向一个列，该列在最大因子t处，远离可能的最大值。请注意，完全扫描可能是 满足上述条件的弧索引完成的，弧只需选择作为搜索的副产品发现的最大值。这样，搜索速度可能会快得多，但有一项谅解，即剩余部分的衰减率有所下降。
3.1.4 标准化
所有上述贪婪算法(OMP、MP 和弱 MP)都被描述为一个通用矩阵A，它可能有不属于单元和范数的列。我们可
以通过来规范列，使用主对角线上包含的对角线矩阵W，然后在上述算法中使用A。 结果
会不同吗？ 答案在下面的定理中说明。
定理3.1. 贪婪算法(OMP、MP 和弱MP)产生相同的解决方案支持当使用原始矩阵A或其归一化版本时。
证明：我们用OMP的第 k 步，并观察到下一个索引的选择是通过找到导致误差最小的来进行的，Ɛ(j)=给出。表示，我们很清楚，因此我们得到
Ɛ(j)
（3.11）
因此，使用归一化列导致相同的结果来选择索引。
下面的最小二乘步骤找到最小的解|，以找到的支持S为前提。由A的子矩阵表示，其中包含从支撑中得到的列，因此上述问题的解决方案很容易由
（3.12）
由此产生的剩余
（3.13）
相反，我们使用子矩阵，其中是从W中提取的部分，指的是支持S。使用该归一化矩阵的 OMP获得的残差是
(3.14)
我们得到了两个选项的残差是相同的，原始矩阵或归一化矩阵A。因此，当残差驱动下一阶段选择支持时， OMP对归一化漠不关心，正如所声称的那样。
对于选择索引，MP使用相同的过程，正如我们已经显示的，这在规范化下不会改变。通过公式，MP中的剩余更新更简单
（3.15）
将相同步骤应用于归一化矩阵给出
（3.16）假设并使用连接，我们得到
（3.17）
我们再次得到残差也保持不变，保证 MP步骤也对正常化漠不关心。最后一个要考虑的算法，弱MP，搜索满足的
（3.18）
当使用原始矩阵时。与归一化矩阵相同的步骤导致非常相同的规则，因此，由于关系，索引的选择是相同的。 此外，更新是与MP使用的非常相同的更新，因此残差也没有改变，从而导致弱MP也对矩阵A的归一化漠不关心，这就得出了这一证明。 □
使用归一化矩阵更简单，因为在所有这些算法中都使用简单的内积来选择下一个支持索引。因此，我们将假设这些矩阵之前有一个归一化。
请注意，如果原始问题是用非归一化矩阵给出的，则归一化确实对所获得的结果有影响。 因此，
如果在任何这些算法中使用归一化矩阵，则必须执行形式的撇去归一化步骤。 这是因为算法提供了满足的解决方案，自从我们得到了
（3.19）
3.15 贪婪方法中残差的衰减率
在 MP 算法中，我们已经看到(见3.2)由残差用递归公式更新。
（3.20）
如果选择，是最大化的。 因此，残余物的能量行为举止像
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409435]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
