《欠定线性方程.doc》由会员分享，可在线阅读，更多相关《欠定线性方程.doc（5页珍藏版）》请在金锄头文库上搜索。
1、欠定线性方程组的稀疏解Sparse Solution of Underdetermined Linear Equations摘要找出欠定线性方程组的稀疏解， y = x NP-hard in general. 此处典型或随机的 是稀疏解的近似值，通过使用线性代数的标准操作的定值得出。我们的建议是，和逐步正交匹配追踪 (StOMP)，陆续将信号转化为忽略不计的残差。从初始残差r0 = y开始，在s-th阶段形成匹配滤波器 Trs1，指出所有振幅超过特定临界值的坐标，用已选坐标解决最小平方的问题，并减去最小二乘法拟合，得出一个新的残差。在经过固定的几个阶段后（例如到10后）停止。与正交匹配追踪算法
2、(OMP)不同，和逐步正交匹配追踪(StOMP)每个阶段，都有多个系数可以进入的其模型，但在正交匹配追踪算法(OMP)的每个阶段，只有一个系数能够进入；此外，和逐步正交匹配追踪(StOMP)有固定的阶段数（例如，10个阶段），而正交匹配追踪算法(OMP)可以有n个不同的阶段。就稀疏解而言，StOMP的运行速度要快的多，例如期中的1最小值以及OMP和其他大规模的问题。利用相图来比较算法性能分析。恢复K-稀疏向量(y,)中的x0就是随机的nN 且y = x0用图中的一点 (n/N, k/n)来表示；值得一提的是，此处的范围为 k n N。对于n，相比范围是1时得到的最小值，StOMP（近似的）正确
3、恢复了 y = x 中稀疏/不确定的平面的稀疏解。事实上，比起1最小化和OMP，StOMP能更好地解决极限欠定问题。我们严格推导出匹配滤波系数中每个步骤，每个阶段的条件高斯分布，并严谨地为StOMP性能变量建立了大型系统极限。准确计算出大量样本相位；这些都为StOMP稀疏矢量的近似恢复提供了渐进准确极限所需的样本数量。通过指出StOMP 在压缩传感，纠错码编码以及超完备表征中能快速有效地找出稀疏解，从而给出数值例。关键字：压缩传感，纠错码编码，稀疏超完备表征。相变，大系统极限。随机矩阵理论，高斯近似，1最小化。阈值函数，逐步回归，错误发现率，错误警报率。MIMO信道，互访干扰，串行干扰抵消，迭
4、代译码。鸣谢：This work was supported by grants from NIH, ONR-MURI, a DARPA BAA,and NSF DMS 00-77261, DMS 01-40698 (FRG) and DMS 05-05303.1: Department of Statistics, Stanford University, Stanford CA, 943052: Institute for Computational Mathematics in Engineering, Stanford University, Stanford CA, 943053:
5、DAPNIA/SEDI-SAP, Service dAstrophysique, Centre Europeen dAstronomie/Saclay, F-91191Gifsur-Yvette Cedex France.1简介利用信号处理中稀疏特性的可行性已经引起广泛的兴趣。多年以来，已有多项应用表明信号具有稀疏表示，充分利用其稀疏性,我们将从中受益无穷；请见11, 28, 26, 25, 7. 2005年的ICASSP 大会特别定题为充分利用稀疏特性，以及近期的国际研讨会也在广泛研究此课题。不久前，稀疏解决方案问题(SSP)引起了广泛的关注。我们给出一个随机意义上的nN的矩阵，例如带有ii
6、d高斯条目的矩阵。同时又给出一个n-矢量y，且已知y = x0中x0是一个未知的稀疏矢量。要想恢复x0 然而值得注意的是n N，方程组若为欠定的则此问题就不适用于线性代数。然而x0的稀疏性有很特殊的性质使得其可以有唯一解。应用范围与此模型有关的有：应用一：压缩传感。X0 代表一个信号或图像的系数且在已知基础上恰好能够稀疏地代表信号与图像。能编译出一个计量运算符，也就是说，一个运算符满足基对象的线性组合。此处nN表示得到的数据比未知还少。尽管存在不确定性，X0 的稀疏性能够将经常被看作是极少样本的对象进行准确重构。17,8,48.应用二：纠错。通过将信息放入编码块中来进行其传递，其中编码块的一小
7、部分条目有可能会被打断。根据接受到的数据来建立一套系统，即y=x0；此处指的是必须要更正或指明的错误的值，y一般代表校验和，一般指校验和运算符。一般认为错误数要比临界值要小，且x0是稀疏的。此处稀疏能使过疏误差被无误的更正。9,48,28.应用三：稀疏过完整表示。x0代表信号y的合成系数，一般认为能被过完整扩展项稀疏代表；这些项是包含在列中的。稀疏性能仅通过若干个项来恢复唯一表示，尽管表示通常都是非唯一的。43,11,21,20,50,51. 在这些应用中，有些算法能够找的合适的稀疏解；有些情况下一些已知的理论结果能确保找到的借是最稀疏的可能解。例如，假设1最小化的算法找到了y = x最小1范
8、数的解。这也叫做基追踪（BP）11，这种方法偏向一些尤为惊人的理论特性，例如在看似一般情况下准确重建的严格证明21,35,32,7,16,8,17,18。令人头疼的是，许多研究结果都需要非常庞杂的计算过程。此次研究是从一开始将压缩传感的理论应用到NMR光谱学中时，我们发现1最小化的直接应用（多元的）每频谱都需要数天的固溶时间开始的。虽然说光谱时间要比计算机时间相对珍贵，但这对我们来说还是巨大的计算成本。事实上，大量研究已经证明一般用途的1最小化对于大型应用来说速度太慢。一些研究已经提出了试探法，正交匹配追踪(OMP)（在其他领域也被叫作贪婪近似法或逐步回归） 43, 52, 53, 55, 5
9、4, 虽然这种方法适用于经验性研究，却无法为1最小化提供有力的理论保障。（其它启发式求解请见50, 51, 29.）在此论文中我们提到了和逐步正交匹配追踪 (StOMP)，欠定组的近似稀疏解的属性中，是随机的，或者x0中的非零元素是随即定位的，或者两种情况同时存在。在处理大型问题的稀疏解时，和逐步正交匹配追踪 (StOMP)相比之前的BP和OMP方法要快得多。此外，和逐步正交匹配追踪 (StOMP)的理论分析表示了StOMP在寻找稀疏解时与BP方法一样可行。分析中我们将相位对比的概念用作性能指标。我们还考虑到相位表，一个带有测量x0(中的行数或x0中的非零个数)相对稀疏度的坐标2D图，还有系统
10、的不确定性y = x(中的列数或中的行数)。.StOMP中的较大-n性能在表中显示出两个相位（成功/失败），同时也完成了BP的过程。这里的“成功相位”（在相位图中StOMP成功找到稀疏解的区域）与1最小化的成功阶段大小相似。某种意义上讲StOMP在解决极限欠定问题的稀疏解时，要比1最小化或OMP都更有效；它的相位边界在极限稀疏下要比其它同类方法还要高。而且StOMP只需要几秒钟就能解决1最小化几天解决的问题。所以StOMP就很适用与大型应用。我们也确实能给出几个确切的既成实例来证明这种方法的好处。我们的分析验证了这么一句话无噪声欠定问题的表现跟有噪声唯一确定问题一样。这也就是说，处理测量数据的
11、零碎数据（随机）就像是在处理高斯噪声的完整数据。在每个StOMP阶段，通常一套匹配滤波器系数是 串扰（非正交性）造成的噪声和实际信号交织在一起的；设定一个合适的临界值，减去已知信号，就可以降低下个迭代阶段的串扰。这不只是刚才那么一句话那样简单；我们又搭建了一个理论框架用来进行严谨的渐进分析。1-3一下的定理让我们可以追踪成功抓取信号的准确度，串扰的降低在每个阶段都在相变之下严格建立了（渐进的）“成功相位”，在相变之上也出现了“失败相位”。所以理论证实了有限-n的结果。论文组织结构大体如下。第二部分为稀疏解问题的背景；第三部分介绍了StOMP算法并记载了其良好的性能；第四部分介绍了基于相位图和相
12、变的测量方法。第五部分为此算法的计算复杂性分析。第六部分介绍了测估相位的分析性大系统极限，因其与StOMP特性向对应。第七部分为关于高斯噪声的观点，也印证了我们的阀值规则。第八部分描述的是StOMP在变化的情况下（增加噪声，非零系数的分部，矩阵集合）的性能，并记载了StOMP在所有不同情况下的良好性能。第九部分为应用1-3中的计算实例，记录了模拟案例中的成功案例。第十部分描述了可用软件包，第十一部分讨论了我们得出的结果与多用户探测理论，以及之前稀疏解问题取得的成果的关系。2 稀疏解预备知识首先回想一下在简介中提到的稀疏解问题（SSP）。在SSP中，未知矢量x0 RN尤为有趣；他是一个假定的稀疏矩阵，也就是说非零数k远比N要小。已知长度测定y = x0中为N矩阵中已知的n，用来恢复x0。当然，如果为非奇矩形矩阵，通过n=N我们很容易将x从y中恢复出来；但我们感兴趣的是当n tss此处s为正常噪声水平，ts是一个阀值参数。我们将挑选出来的坐标及之前提到的估测值的子集合并，因此得到一个新的估测值：(xs)Is= (TIsIs)1TIsY.0.1.1.2.3.5.8.13
