英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
第二章 唯一性与不确定性
我们回到基本问题(P0)，这是我们讨论的核心。(P0):满足b = Ax的x最小0-范数（稀疏度）。虽然我们在下文中会将这个问题作为我们的主要目标，但我们强调，我们很清楚这个问题在任何实际工具方面的两个主要缺点：
- 等式要求b = Ax太过于严格，因为任何向量b 能由A的几个列向量表示的可能性很小。更好的要求就是允许存在较小的偏差。
- 稀疏性度量对于x中非常小的条目过于敏感，更好的度量应该对这些小条目采取更加宽松的办法。
这两点考虑的问题都会包含在后面的分析中，但是为了顺利，我们必须从正如(P0)所提出的问题的程式化方面开始。
对于未定线性方程组Ax = b（一个满秩矩阵Aisin;IRntimes;m，其中nlt;m），我们提出了如下问题：
问题1：什么时候能确定最稀疏解的唯一性？
问题2：是否可以测试一个特殊解以验证其（全局）最优性吗？
这一章解决了这些问题以及它们的一些扩展问题。我们没有直接回答上述问题，而是首先考虑了特殊矩阵A，对特殊矩阵的分析似乎更加容易。然后我们再将答案推广到一般矩阵A。这样做的同时，我们也遵循了起初处理这些问题的研究人员所采取的方法步骤。
2.1. 处理两个问题
我们首先在具体条件下讨论上面定义的(P0)问题：A是两个正交矩阵Psi;和Phi;的拼接。作为一个典型的例子，我们可以考虑单位矩阵和傅里叶矩阵的合并：A= [I, F]。在这种条件下，方程组b = Ax是未定的这一事实，具体意味着有多种方式将一个给定的信号b表示为尖峰（即来自单位矩阵的列）和正弦（即来自傅里叶矩阵的列）的叠加。这种方程组的稀疏性解决方案是将所述信号表示为几个正弦信号和尖峰信号的叠加。这种稀疏性结局方案的独特性在首次得到关注时似乎令人惊讶。
2.1.1 不确定性原理
在处理线性方程组[Psi;, Phi;] x = b的稀疏性方案之前，受经典不确定性的启发，我们应当考虑一个（看似）不同的问题。正如读者无疑知道的那样，经典的不确定性原理指出，两个共轭变量(例如，位置和动量，或通过傅立叶变换耦合的任何其他对)不能都以任意精度已知。转到它的数学公式，它声明任何函数f(x)和它的傅立叶变换F(omega;)必须服从不等式
， (2.1)
其中我们假设这些函数是归一化的，
这种说法表明一个信号不可能在时间和频率上紧密集中的，并且时间上扩展和频率扩展的乘积有一个下限。
在我们的术语中，一个类似的主张是信号不能同时在时间和频率上稀疏地表示。我们现在来研究这个确切的观点，因为它将有助于理解下面的一些讨论。假设我们有一个非零向量bisin;IRn (比如说一个信号)和两个正交基Psi;和Phi;。则b可以表示为Psi;列的线性组合，也可以表示为Phi;：b = Psi;alpha; = Phi;beta; (2.2)的列的线性组合。
显然，alpha;和beta;是唯一定义的。在一个特别重要的情况下，Psi;仅仅是单位矩阵，而Phi;是傅立叶变换的矩阵。则alpha;是b的时域表示，而beta;是频域表示。
对于任意一对基Psi;和Phi;，会出现一个有趣的现象：alpha;可以是稀疏的，或者beta;可以是稀疏的，但不能同时稀疏！然而，这种说法显然是取决于Psi;和Phi;之间的距离，因为如果两者相同，我们可以很容易地将b构造为Psi;中的一列，并在alpha;和beta;中获得可能的最小基数(为1)。因此，我们现在用两个基的相关系数来定义它们之间的接近程度。
定义2.1. 对于构成矩阵A的任意对正交基Psi;，Phi;，我们将相关系数micro;(A)定义为这两个基的列之间的最大内积，
邻近度(Psi;，Phi;)= micro;(A) = (2.3)
这种双正交矩阵的相关系数满足1/micro;(A)1，对其中某些正交基对，例如恒等式与傅立叶、恒等式与Hadamard等，其下界是可达到的。要理解这确实是可能相干性的下限，只需注意Psi;Phi;是一个正交矩阵，其每列的项的平方和等于1。因此，所有条目都不能小于1/，因为这样我们就会得到所有平方条目的和小于1。使用上面的定义2.3，我们能得到以下不等式结果：
不确定原则1: (2.4)
证明：此后，在不失一般性的前提下，我们将假设= 1。由于b = Psi;alpha; = Phi;beta;，且bb = 1，我们有
1 = bb (2.5)
= alpha;Psi;Phi;beta;
=
在这里，我们利用了两个基之间一致性的定义。此不等式导致
(2.6)
这可以被解释为“1-范数”情况的另一个不确定性原则，表明两个表述不能同时“1-短”。实际上，使用几何平均值和代数平均值之间的关系()，我们有
(2.7)
然而，这会分散我们的注意力，我们又回到了以0的不确定性原则。
让我们考虑下面的问题：在所有满足=1并且具有非零值(即)的可能表示alpha;中，给出最长1-长度的表示是什么？这定义了一个形式的满足和 (2.7) 的优化问题。
假设这个问题得到一个解。类似地，B非0的beta;的并行定义给出了结果。这意味着使用等式(2.6)，我们可以得到一个形式为
(2.9)
的不等式，因为每个1-长度都用其上界替换。这样的不等式是我们的目标，因此我们需要解决等式(2.8)中提出的问题。
在不失一般性的情况下，我们可以假设alpha;中的A非零是它的第一个条目，其余的是零。我们进一步假设所有这些条目都是严格大于0的(因为在这个问题中我们只使用绝对值)。利用拉格朗日乘子，0-约束消失，我们得到
(2.10)
该拉格朗日函数的导数为
(2.11)
即最优值由给出，且均相同。这意味着最佳值(由于2-约束)是，因此是向量alpha;的最大1-范数的值。使用此结果和beta;的并行结果，插入式(2.9)可得到
(2.12)
再次使用几何-代数平均关系我们可以得到所述的
(2.13)
另一种更简单的证明(由Allan Pinkus提出)如下：由于Psi;和Phi;
是酉矩阵，我们有。让我们用I来表示alpha;。由b = Psi;alpha; =我们有
(2.14)
其中我们使用了柯西-施瓦茨不等式以及相关系数的定义。将所有在jisin;J上的beta;表达式求和，我们得到
(2.15)
这推出了我们在等式(2.13)中提出的不等式，从而证明了定理。
这一结果表明，如果两个碱基的相关系数很小，那么alpha;和beta;不可能都是非常稀疏的。例如，如上所述，Psi;是恒等式，Phi;是傅立叶矩阵，则micro;([Psi;,Phi;])1/。由此得出，信号在时域和频域都不可能少于2个非零点。在这种情况下，我们还知道这是一种必然关系，因为具有均匀间距 (假设它是整数)的尖桩栅栏信号通过傅立叶变换(由于泊松公式)被转换成相同的信号，从而累积2个非零点。图2.1显示了此信号。
海森堡经典的不确定原理在离散背景下就是，如果我们将alpha;和beta;看作概率分布(取条目的绝对值并进行归一化)，则它们方差的乘积满足ge;常数。相反，(2.4)给出了非零点之和的下界，而不考虑它们的位置。
1
0.8
0.6
0.4
0.2
0
0 10 20 30 40 50 60
图2.1 当n=64时的栅栏信号。它有8个等高的均匀分布的非零。该信号的离散傅立叶变换(DFT)看起来完全相同。
2.1.2 冗余解的不确定性
我们现在将其与唯一性问题联系起来。根据不确定性原理(2.4)，考虑求解Ax=[Psi;,Phi;]x=b的问题。假设下面的线性系统有两个解，，，其中一个是非常稀疏的。我们将看到另一个不可能也是非常稀疏的。差值必然在A的零空间内。将e分别分割成e的前n个条目和后n个条目的子向量和。我们有
Psi;=-Phi;＝y ne; 0 (2.16)
向量y是非零的，因为e是非零的，并且Psi;和Phi;都是非奇异的。现在调用(2.4)：
(2.17)
由于e = minus;，我们有(不确定性原理2)：
(2.18)
这里，我们对0-范数使用三角不等式，，通过计算两个向量的非零点，并考虑没有支撑重叠(这导致相等)和重叠(这给出了这个不等式)。综上所述，我们证明了以下结果：
定理2.2. 线性系统[Psi;, Phi;] x = b的任何两个不同的解，不可能都是非常稀疏的，由于下面不确定性原理2：
(不确定性原理2)：
当我们在这里讨论欠定系统的解时，我们将这一结果称为冗余解的不确定性。
2
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409434]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
