[稀疏与冗余表示第二章.docxVIP

第2章唯一性和不确定性我们返回到基本问题（P0），它是我们讨论的核心，当我们参照以下这个问题作为我们的主要目标，我们强调我们很清楚导致任何实用的工具的两个主要缺陷：1.等式要求b = AX过于严格，因为存在被A的少数列表示的任何向量b的微小改变,一个更好的要求是一个允许小的偏差的要求。2.稀疏测度对X中很小的项过于敏感，一个更好的测度将采取对这样的小项更宽容的做法。这两个方面的考虑将包括在以后的分析中，但对于这个成功，我们必须从确实是由（P0）提出的问题的程式化??版本开始。对于欠定线性方程组，Ax = b的（一个满秩矩阵，N M），我们提出以下几个问题：Q1：被提出的最稀疏的解什么时候是唯一的？Q2：是否可以验证一个候选解的全局最优解？这节解决了这些问题和它们的一些扩展。而不是直接回答上述问题，我们首先考虑的特殊矩阵A使这些分析看起来更容易，然后将我们的答案扩展到一般矩阵A.在这样做后，我们也沿着最初解决了问题的研究者的路径继续探究。2.1处理双-正交情形我们首先讨论在一个具体的设定中的上面已定义的（P0）问题：在这个情形中，A是两个正交矩阵和的联合矩阵。作为一个经典的例子，我们可以考虑单位阵和傅立叶矩阵的联合A = [I; F]。在这样的设定中，事实上，系统b = AX是欠定方程组，具体而言，表示一个给定的信号b有许多方法，b可以看作一系列峰值（即来自单位矩阵的列）和正弦曲线（即傅立叶矩阵的列）的叠加。这种系统的一个稀疏解是作为几个正弦和几个峰值的叠加的所述信号的一种表示。当第一次发现这样的稀疏解的唯一性似乎令人惊讶。2.1.1不确定性原理受经典的不确定性原理的启发，在解决线性系统的稀疏解前，我们将考虑一个（看起来）很难的问题，。作为读者无疑知道，经典的不确定性原理表明两个成对的变量（如位置和动量，或其他任何由傅立叶变换生成的一对向量）不可同时被确定。对其数学公式进行变换，它指出任何函数f（x）及其傅立叶变换必须遵循以下不等式在这里我们假定这些方程是归一化的，这种推断说明一个信号不能在时域和空域被聚集，并在时域和频域的传播结果中有一个下界。在我们的术语中一个类似的推断是一个信号不能在时域和频域同时稀疏表示。我们现在发展这个确切的观点，因为它对理解下面的一些讨论是有帮助的。假设我们有一个非零向量（表示一个信号）和两个正交基和。那么b可以表示作的列的线性组合或作为的列的线性组合：显然，和被唯一定义。在一个特别重要的情况下，是单位矩阵，是傅立叶变换的矩阵。那么是b的时域表示而是b的频域表示。对于任意一对基，;一个有趣的现象发生了：要么是稀疏的，要么是稀疏的，但不能同时稀疏！然而，这种说法显然取决于和之间的距离，因为如果这两个是相同的，我们可以很容易地构造b是的其中一列，并获得在和可能的最小基数（即1）。因此，我们现在开始定义两个基的互相关。定义2.1对于构成矩阵A的任意一对正交基和;我们定义互相关为这两个基列之间的最大内积这样的双-正交矩阵的互相关满足。其中下界对于某些双正交基是可以实现的，如单位阵和傅立叶变换矩阵，单位阵和阿达马矩阵，等等。一看就知道，这确实是可能的互相关下界，一个简单的注释是是一个正交矩阵，在每一列中的它的项的平方和等于1。所有的项不能小于，所有平方项的和小于1。使用上面的定义2.3，我们有以下不等式的结果：定理2.1 对于任意一对互相关为的正交基，对于任意一个非零向量它在两个基下的表示分别为和，以下不等式成立：证明：不失一般性，我们将假设。由于，，我们有在这里，我们已经利用两个基之间的互相关的定义。由此不等式推导得这可以解释为范数的情况下又一不确定性原理，这表明两种表示不能同时短。事实上，使用几何和代数平均数的关系，我们有然而，这偏离了我们的目标，我们返回到基于的不确定性原理。让我们考虑以下的问题：在满足和有A个非零项（即）的所有可能的表示，哪个是长度最长的一个？这定义了形式的最优化问题：假设该问题的一个解。类似地，对B个非零项的向量给出一个类似的解为。这意味着使用公式（2.6），我们有如下形式的不等式由于每个长度被替换为其上限。这个不等式是我们的目标，需要等式（2.8）提出的问题的解。不失一般性，我们可以假设中的A个非零项式是它的前A项，其余为零。我们进一步假设，所有这些项都是严格正的（因为在这个问题中仅使用绝对值）。用拉格朗日乘子，约束消失了，我们得到这个拉格朗日式的导数是这意味着最优解是由下式给出，每一项都是相同的。这意味着该最优解（由于约束）是，从而是向量最大的范数的最大值？使用此解和类似的的解，，代入（2.9）得再次使用几何平均数我们得到关系另一种更简单的证明（由艾伦·平库斯证明）如下：由于和是酉矩阵，我们有。让我们用I表示的支撑集。（在数学中，一个定义在集合X上的实值函数f的支撑集，或简称支集，