稀疏与冗余表示第二章.docx

第2章 唯一性和不确定性我们返回到基本问题（P0），它是我们讨论的核心，当我们参照以下这个问题作为我们的主要目标，我们强调我们很清楚导致任何实用的工具的两个主要缺陷：1.等式要求b = AX过于严格，因为存在被A的少数列表示的任何向量b的微小改变,一个更好的要求是一个允许小的偏差的要求。2.稀疏测度对X中很小的项过于敏感，一个更好的测度将采取对这样的小项更宽容的做法。这两个方面的考虑将包括在以后的分析中，但对于这个成功，我们必须从确实是由（P0）提出的问题的程式化版本开始。对于欠定线性方程组，Ax = b的（一个满秩矩阵，N n, 必然是严格正的，我们希望得到尽可能最小的可能值以便获得和酉矩阵表现出来性质尽可能的接近。我们已经看到，对于结构化得双正交矩阵的互相关满足。考虑n*m的随机正交矩阵，在多诺霍和霍的文章中表明它们往往是不连续的，这意味着当时和通常是成正比。它表明对于大小为n*m的满秩矩阵的互相关的下界由下式给出一系列矩阵不等式被命名为格拉斯曼框架。这些矩阵的一系列列叫做等角线。事实上，一系列的矩阵有，可能的最高值。这样的矩阵的数值构建已被Tropp等使用迭代投影到（有时并非如此）凸集得到解决。我们将在这章的最后回到这个话题。我们也在量子信息理论中提到了Calderbank的文章，使用具有最小互相关的正交基的集合构建纠错码，获得的正交基的组合的互相关的类似确界。与此活动的流程更相关的是Sochen，Gurevitz和Hadani最近的贡献，信号集的结构使得它们的变化具有低的互相关。互相关是比较容易计算的，正因为如此，它使我们能够达到spark的下界，spark常常是难以计算的。引理2.1 对于任何矩阵，下面的关系成立：证明：首先，通过归一化A的列具有单位范数修改矩阵A，获得。这种操作既保留了spark和互相关。结果格拉姆（Gram）矩阵（给定一个实矩阵A，矩阵ATA是A的列向量的格拉姆矩阵，而矩阵AAT是A的行向量的格拉姆矩阵。）满足以下的性质：考虑大小为p*p的矩阵G的任意主对角线元素，通过选择的p列的一个子集和计算其子-格拉姆（sub-Gram）构建。从Gershgorin圆盘定理（对于一般的（可能是复杂的）大小为n*n的矩阵H，Gershgorin的圆盘是由中心和半径的n个磁盘形成的。该定理表明H的所有特征值必须躺在这些磁盘的组合内。可知，如果主对角线元素对角占优，也就是说，如果对于每个i - 则G的这个子矩阵是正定的，一族向量线性无关当且仅当格拉姆行列式（格拉姆矩阵的行列式）不等于零。因此的p列 是线性无关的。条件表明每一个P* P子矩阵的正定性较小。因此，是最小的可能导致线性相关的列的数目，因此。我们对先前的唯一性定理有下列的模拟，而这一次基于互相关。定理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一样大的界。事实上，对于特殊的矩阵，我们也得到了这样的规则。有趣的是，一般情况下的下界变为，而特殊的双正交的情况下给了一个强大的（即更高）的下限。一般情况下的确界比（2.18）弱近2倍，因为（2.18）采用特殊结构。2.2.3通过Bable方程考虑其唯一性在引理2.1的证明，我们考虑归一化矩阵的格莱姆矩阵所提取的大小为p*p的子矩阵。所有这些子矩阵的意味着每P个列是线性无关的。然而，为了简化分析，我们将G的非对角线项的限定为一个简单的值，因此，在这个矩阵中可能很少的项丢失的鲁棒性。由于我们需要检查每列的p-1个非对角线项的总和是否小于1（对Gershgorin性质保真），我们就可以定义下列贝尔方程，下面Tropp（特罗普）：2.2.3通过Bable方程考虑其唯一性定义2.4对于给定的归一化列矩阵，我们考虑的p列的一个子集，并且计算这个子集中的所有列与子集外的一列的内积的绝对值的和，同时最大化子集和子集外的第j列我们得到Babel方程：显然，对于p = 1，我们得到。对于p = 2上式表明我们要搜索一切可能的三个向量，考虑到其中两个向量属于，第三个作为外部向量与另两个向量计算内积。这个定义表明着这个函数是单调非递减的，它的增长越慢，它使得分析结果更好 ，相比于使用较粗略的互相关估测。计算对于大p成为指数这个函数，因此望而却步，但其实这是不正确的。通过计算， 按降序排列的每一行，我们得到矩阵。每一行中的第一项为1时，成为主对角项，因此应被忽略。计算每一列的前p项和（从第二项开始计算），我们得到了上述定义最差子集的每个j，我们从中应该选择最大的一个，因而我们注意到，对于每一个P，我们有， 对于格拉斯曼矩阵（Grassmannian）等号成立，其中所有Gram矩阵的非对角线项是相同的大小。我们怎样才能用Bable方程更好地估计唯一性？ 显然，如果，我们推断，所有的p + 1列是线性无关的。因此，Spark的一个下限的可能是紧接着是不确定性和唯一性特性2.2.4spark的上界 spark一般不可能估计，因为它比解决（P0）更难。这是因为它的评估需要搜索具有不同基的A的所有可能的一组列，寻求线性相关的列子集。这是具有m复杂指数的组合搜索。虽然解释用互相关替代spark的必要性是困难的，唯一性结果的鲁棒性的付出的花费可能被认为太昂贵而不被允许。这激发了用于近似的替代spark的方法，这一次使用上限。这样的一个界限表明我们不能保证基于已获得的值的唯一性，但它对唯一性的范围进行了粗略评估。2.2.4spark的上界 为了获得上界，我们重新定义的spark为范数的m个优化问题 i=1,2,3,m每个问题假设在A的零空间的最稀疏向量使用第i项。通过求解类似序列的问题，spark即为中的最稀疏结果由于一系列问题太复杂，我们定义了另外一系列问题替代，用替代范数，正如我们在第1章中所看到的，这些问题有一个线性规划结构，他们是凸的，并且在合理的时域可解。此外，很显然，对于每个i，我们有，因为根据定义是这个问题可能最稀疏的解，因此，我们有界限 数值试验表明，这个界限往往是相当严格的，并接近真的spark。2.3构建格拉斯曼矩阵一个大小为n*m的格拉斯曼（实）矩阵n大小是一个列归一化矩阵，其Gram矩阵满足正如上文提到的，这是可能的最小互相关。这样的矩阵不一定存在，并且特别地，当且仅当时，它们是可能的。在这个意义上，格拉斯曼矩阵是特别的，在这个矩阵每个列和每对列之间的角度是相同的，并且它也是最小的可能。因此， 这种矩阵的构建与这些空间的向量/子空间有很紧密的联系。当m=n时，酉矩阵很容易构建，构建一个格拉斯曼矩阵是非常困难的。这项任务的数值算法由Tropp等人提出。我们也把这里作为这样的设计程序的一个例证。我们要补充的是，虽然图像处理对这种结构的兴趣不大，他们在编码，无线通信等方面有重要应用。该算法的核心思想是在投影在这个矩阵应该满足的域上进行迭代。以任意矩阵A开始，这些投影应参照以下要求：1.A的列是归一化的：这可以通过归一化每一列得到。2.性质（2.30）：我们应该计算，检测上述的一些非对角项，并且降低它们。类似地，由于过小的值也不允许在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; 计算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 =sqrt（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总结 现在，我们已经给出在本章开始时提出的问题的答案。我们已经看到，任何足够稀疏的解保证是在所有的可能的解中的唯一性