稀疏与冗余表示第二章

《稀疏与冗余表示第二章》由会员分享，可在线阅读，更多相关《稀疏与冗余表示第二章（14页珍藏版）》请在金锄头文库上搜索。

1、第 2 章 唯一性和不确定性我们返回到基本问题（P0） ，它是我们讨论的核心，当我们参照以下这个问题作为我们的主要目标，我们强调我们很清楚导致任何实用的工具的两个主要缺陷：1.等式要求 b = AX 过于严格，因为存在被 A 的少数列表示的任何向量 b 的微小改变,一个更好的要求是一个允许小的偏差的要求。2.稀疏测度对 X 中很小的项过于敏感，一个更好的测度将采取对这样的小项更宽容的做法。这两个方面的考虑将包括在以后的分析中，但对于这个成功，我们必须从确实是由（P0）提出的问题的程式化版本开始。对于欠定线性方程组，Ax = b 的（一个满秩矩阵 ，N n, 必然是严格正的，我们希望得到尽可能最

2、小的可能值以便获得和酉矩阵表现出来性质尽可能的接近。我们已经看到，对于结构化得双正交矩阵 的互相关满足。考虑 n*m 的随机正交矩阵，在多诺霍和霍的文章中表明它们往往是不连续的，这意味着当 时 和 通常是成正比。它表明对于大小为 n*m 的满秩矩阵的互相关的下界由下式给出一系列矩阵不等式被命名为格拉斯曼框架。这些矩阵的一系列列叫做等角线。事实上，一系列的矩阵有 ，可能的最高值。这样的矩阵的数值构建已被 Tropp 等使用迭代投影到（有时并非如此）凸集得到解决。 。我们将在这章的最后回到这个话题。我们也在量子信息理论中提到了 Calderbank 的文章，使用具有最小互相关的正交基的集合构建纠错

3、码，获得的正交基的组合的互相关的类似确界。与此活动的流程更相关的是 Sochen，Gurevitz 和 Hadani 最近的贡献，信号集的结构使得它们的变化具有低的互相关。互相关是比较容易计算的，正因为如此，它使我们能够达到 spark 的下界，spark 常常是难以计算的。引理 2.1 对于任何矩阵 ，下面的关系成立：证明：首先，通过归一化 A 的列具有单位 范数修改矩阵 A，获得 。这种操作既保留了 spark 和互相关。结果格拉姆（ Gram）矩阵 （给定一个实矩阵 A，矩阵 ATA 是 A 的列向量的格拉姆矩阵，而矩阵 AAT 是 A 的行向量的格拉姆矩阵。）满足以下的性质：考虑大小为

4、 p*p 的矩阵 G 的任意主对角线元素，通过选择的 p 列的一个子集和计算其子- 格拉姆（sub-Gram）构建。从 Gershgorin 圆盘定理（对于一般的（可能是复杂的）大小为 n*n 的矩阵 H，Gershgorin 的圆盘是由中心 和半径 的 n 个磁盘形成的。该定理表明 H 的所有特征值必须躺在这些磁盘的组合内。可知，如果主对角线元素对角占优，也就是说，如果对于每个 i - 则 G 的这个子矩阵是正定的，一族向量线性无关当且仅当格拉姆行列式（格拉姆矩阵的行列式）不等于零。因此 的 p 列 是线性无关的。条件 表明每一个 P* P 子矩阵的正定性较小。因此， 是最小的可能导致线性相

5、关的列的数目，因此 。我们对先前的唯一性定理有下列的模拟，而这一次基于互相关。定理 2.5 （唯一性 - 互相关）：如果线性方程组 Ax = b 有一个解 x 满足，该解必然是最稀疏的解。比较定理 2.4 和 2.5。它们的形式类似，但有不同的假设。一般来说，定理2.4，它使用了 spark，是尖锐的，并且比定理 2.5 更强，定理 2.5 使用了互相关，因此只有 spark 的下界更小。互相关永远不能小于 。因此，定理 2.5 的基数界势必是永远大于 。不过，spark 很容易和 n 一样大，定理 2.4 接着给出一个和 n/2 一样大的界。事实上，对于特殊的矩阵 ，我们也得到了这样的规则。

6、有趣的是，一般情况下的下界变为 ，而特殊的双正交的情况下给了一个强大的（即更高）的下限。一般情况下的确界比（2.18）弱近 2 倍，因为（2.18 ）采用特殊结构 。2.2.3 通过 Bable 方程考虑其唯一性在引理 2.1 的证明，我们考虑归一化矩阵 的格莱姆矩阵所提取的大小为 p*p的子矩阵。所有这些子矩阵的意味着每 P 个列是线性无关的。然而，为了简化分析，我们将 G 的非对角线项的限定为一个简单的值 ，因此，在这个矩阵中可能很少的项丢失的鲁棒性。由于我们需要检查每列的 p-1 个非对角线项的总和是否小于 1（对Gershgorin 性质保真） ，我们就可以定义下列贝尔方程，下面 Tr

7、opp（特罗普）：2.2.3 通过 Bable 方程考虑其唯一性定义 2.4 对于给定的归一化列矩阵 ，我们考虑 的 p 列的一个子集 ，并且计算这个子集中的所有列与子集外的一列的内积的绝对值的和，同时最大化子集 和子集外的第 j 列我们得到 Babel 方程：显然，对于 p = 1，我们得到 。对于 p = 2 上式表明我们要搜索一切可能的三个向量，考虑到其中两个向量属于 ，第三个作为外部向量与另两个向量计算内积。这个定义表明着这个函数是单调非递减的，它的增长越慢，它使得分析结果更好 ，相比于使用较粗略的互相关估测。计算对于大 p 成为指数这个函数，因此望而却步，但其实这是不正确的。通过计算

8、 ， 按降序排列的每一行，我们得到矩阵 。每一行中的第一项为 1 时，成为主对角项，因此应被忽略。计算每一列的前 p 项和（从第二项开始计算） ，我们得到了上述定义最差 子集的每个 j，我们从中应该选择最大的一个，因而我们注意到，对于每一个 P，我们有 ， 对于格拉斯曼矩阵（Grassmannian）等号成立，其中所有 Gram 矩阵的非对角线项是相同的大小。我们怎样才能用 Bable 方程更好地估计唯一性？ 显然，如果 ，我们推断，所有的 p + 1 列是线性无关的。因此，Spark 的一个下限的可能是紧接着是不确定性和唯一性特性2.2.4spark 的上界 spark 一般不可能估计，因为

9、它比解决（P0）更难。这是因为它的评估需要搜索具有不同基的 A 的所有可能的一组列，寻求线性相关的列子集。这是具有 m 复杂指数的组合搜索。虽然解释用互相关替代 spark 的必要性是困难的，唯一性结果的鲁棒性的付出的花费可能被认为太昂贵而不被允许。这激发了用于近似的替代 spark 的方法，这一次使用上限。这样的一个界限表明我们不能保证基于已获得的值的唯一性，但它对唯一性的范围进行了粗略评估。2.2.4spark 的上界 为了获得上界，我们重新定义的 spark 为范数的 m 个优化问题 i=1,2,3,m每个问题假设在 A 的零空间的最稀疏向量使用第 i 项。通过求解类似序列的问题，spa

10、rk 即为 中的最稀疏结果由于一系列问题 太复杂，我们定义了另外一系列问题替代，用 替代范数，正如我们在第 1 章中所看到的，这些问题有一个线性规划结构，他们是凸的，并且在合理的时域可解。此外，很显然，对于每个 i，我们有 ，因为根据定义 是这个问题可能最稀疏的解，因此，我们有界限数值试验表明，这个界限往往是相当严格的，并接近真的 spark。2.3 构建格拉斯曼矩阵一个大小为 n*m 的格拉斯曼（实）矩阵 n 大小是一个列归一化矩阵，其 Gram 矩阵 满足正如上文提到的，这是可能的最小互相关。这样的矩阵不一定存在，并且特别地，当且仅当 时，它们是可能的。在这个意义上，格拉斯曼矩阵是特别的，

11、在这个矩阵每个列和每对列之间的角度是相同的，并且它也是最小的可能。因此， 这种矩阵的构建与这些空间的向量/子空间有很紧密的联系。当 m=n 时，酉矩阵很容易构建，构建一个格拉斯曼矩阵是非常困难的。这项任务的数值算法由 Tropp 等人提出。我们也把这里作为这样的设计程序的一个例证。我们要补充的是，虽然图像处理对这种结构的兴趣不大，他们在编码，无线通信等方面有重要应用。该算法的核心思想是在投影在这个矩阵应该满足的域上进行迭代。以任意矩阵 A 开始，这些投影应参照以下要求：1.A 的列是 归一化的：这可以通过归一化每一列得到。2.性质（2.30）：我们应该计算 ，检测上述的一些非对角项，并且降低它

12、们。类似地，由于过小的值也不允许在 Gram 矩阵中，可能还要增大非对角线项的值。3.G 的秩不应超过 n：由于上述修改，导致 G 成为满秩矩阵，一个奇异值操作和截断超出前 n 项的奇异值使得 Gram 矩阵达到合适的秩。这个过程可以并且应该被重复多次。没有保证收敛，或趋于一个格拉斯曼矩阵，但测试表明，人们可以用这一数值方法得到接近这样的矩阵。一个MATLAB 代码如下这些准则是在图 2.2 中给出。D = randn（N，L）; 初始化产生标准正态分布的随机数或矩阵的函数D = D *diag（ 1 /spart（diag（D* D） ） ）; 列归一化用于构造一个对角矩阵G = D* D;

13、 计算 Grammu =sqrt(（L-N ）/ N /（L-1） ）;for k = 1：1：Iter( 项)，收缩大的内积gg=sort（abs（G（:)） ）;pos=find（abs（G（:) ） ） gg（round （dd1 *（L * L-L） ） ） abs（G（:)） ） gg（round （dd1 *（L * LL） ） ）和 abs（G（:)） ）1;disp（K，mu，mean（abs（G（pos） ） ） ，max （abs （G （pos ） ） ） ）; disp 函数直接将内容输出在 Matlab 命令窗口中：end;U，S， V = svd（G）;D =sqr

14、t（S（ 1：N ，1：N） ）* U（：，1：N） “;图 2.2 构建格拉斯曼矩阵的 Matlab 代码。图 2.3 表示出了这个程序的结果为。对于大小为 50*100 的矩阵，该最小可能的互相关为 。图 2.3 显示了最初的 Gram 矩阵和在 1000 次迭代后的结果，使用 。图 2.4 显示在这两个 Gram 矩阵的非对角项的排序，正如我们所见，迭代过程成功非常成功地获得了和格拉斯曼矩阵非常接近的一个矩阵。事实上，在此过程中，最大非对角项是 0.119。图 2.5 给出了通过算法的迭代改进的互相关 1。2.4 总结 现在，我们已经给出在本章开始时提出的问题的答案。我们已经看到，任何足够稀疏的解保证是在所有的可能的解中的唯一性。因此，任何足够稀疏的解必然是 全局最优的。这些结果表明，寻找一个稀疏解可以导致有趣的特性的好的提出的问题。我们现在来讨论获得的解的实用的方法。图 2.3 初始格拉姆矩阵（左上）和最后 1 个（右上）训练了大小为 50*100 的格拉斯曼矩阵.该图的底部显示出了最终的格拉姆矩阵的绝对值，表明了非对角线元素趋向于具有相同的值，根据要求。图 2.4 原始和最后的 Gram 矩阵非对角线项的排序图 2.5 迭代过程中一个函数涉及的互相关