稀疏随机矩阵的观测次数下界.PDFVIP

第２８卷　第 ８期 信 号 处 理 Ｖｏｌ．２８　Ｎｏ．８ ２０１２年８月 ＳＩＧＮＡＬＰＲＯＣＥＳＳＩＮＧ Ａｕｇ．２０１２ 稀疏随机矩阵的观测次数下界 孙晶明　王　殊　董　燕 （华中科技大学电子与信息工程系，湖北 武汉４３００７４） 摘　要：压缩感知理论中的稀疏重构问题，要将一个高维信号从它的低维投影中恢复出来，通常选用稠密随机矩 阵作为观测矩阵来解决这一问题。而某些稀疏随机矩阵作为观测矩阵也可以达到这一目的。稀疏随机矩阵的特 点是，在编码和重构过程中都具有较低的计算复杂度，更新方便，且对存储容量的要求较低。该文基于压缩感知 理论，分别对列重固定、行重固定以及一般的稀疏随机矩阵进行了研究，当这些稀疏随机矩阵满足有限等距性质 时，推导了观测次数应满足的下界条件，并对三种矩阵的性能进行了分析。以二值稀疏随机矩阵为特例，进行了 仿真实验。实验结果显示，结论给出的观测次数下界是比较紧的，并验证了列重固定、行重固定的稀疏随机矩阵 作为观测矩阵的可行性和实用性。 关键词：压缩感知；观测矩阵；稀疏随机矩阵；有限等距性质；观测次数 中图分类号：ＴＮ９１１．７　　文献标识码：Ａ　　文章编号：１００３－０５３０（２０１２）０８－１１５６－０８ ＬｏｗｅｒＢｏｕｎｄｓｏｎｔｈｅＮｕｍｂｅｒｏｆＭｅａｓｕｒｅｍｅｎｔｓ ｏｆＳｐａｒｓｅＲａｎｄｏｍＭａｔｒｉｃｅｓ ＳＵＮＪｉｎｇｍｉｎｇ　ＷＡＮＧＳｈｕ　ＤＯＮＧＹａｎ （ＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＨｕａｚｈｏｎｇＵｎｉｖｅｒｓｉｔｙ ｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：　Ｓｐａｒｓｅｒｅｃｏｖｅｒｙｐｒｏｂｌｅｍｉｎｔｈｅｔｈｅｏｒｙｏｆｃｏｍｐｒｅｓｓｅｄｓｅｎｓｉｎｇｉｓｔｏｒｅｃｏｖｅｒａｈｉｇｈｄｉｍｅｎｓｉｏｎａｌｓｉｇｎａｌｆｒｏｍｉｔｓ ｌｏｗｄｉｍｅｎｓｉｏｎａｌｐｒｏｊｅｃｔｉｏｎ，ａｎｄａｄｅｎｓｅｒａｎｄｏｍｍａｔｒｉｘｉｓｕｓｕａｌｌｙｕｓｅｄａｓｔｈｅｍｅａｓｕｒｅｍｅｎｔｍａｔｒｉｘｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ． Ｗｈｉｌｅｓｏｍｅｓｐａｒｓｅｒａｎｄｏｍｍａｔｒｉｃｅｓａｓｔｈｅｍｅａｓｕｒｅｍｅｎｔｍａｔｒｉｃｅｓｃａｎａｌｓｏａｃｈｉｅｖｅｔｈｉｓｇｏａｌ．Ｓｐａｒｓｅｒａｎｄｏｍｍａｔｒｉｃｅｓｈａｖｅ ｓｅｖｅｒａｌａｔｔｒａｃｔｉｖｅｐｒｏｐｅｒｔｉｅｓ，ｌｉｋｅｌｏｗｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙｉｎｂｏｔｈｅｎｃｏｄｉｎｇａｎｄｒｅｃｏｖｅｒｙ，ｅａｓｙｉｎｃｒｅｍｅｎｔａｌｕｐｄａｔｅｓ， ａｎｄｌｏｗｓｔｏｒａｇｅｒｅｑｕｉｒｅｍｅｎｔ．Ｂａｓｅｄｏｎｔｈｅｔｈｅｏｒｙｏｆｃｏｍｐｒｅｓｓｅｄｓｅｎｓｉｎｇ，ｔｈｉｓｐａｐｅｒｉｎｖｅｓｔｉｇａｔｅｓｓｐａｒｓｅｒａｎｄｏｍｍａｔｒｉｃｅｓ ｗｉｔｈｆｉｘｅｄｃｏｌｕｍｎｓｐａｒｓｉｔｙｏｒｆｉｘｅｄｒｏｗｓｐａｒｓｉｔｙａｎｄｇｅｎｅｒａｌｓｐａｒｓｅｒａｎｄｏｍｍａｔｒｉｃｅｓｒｅｓｐｅｃｔｉｖｅｌｙ，ａｎｄｗｈｅｎｔｈｅｓｅｓｐａｒｓｅｒａｎ ｄｏｍｍａｔｒｉｃｅｓｓａｔｉｓｆｙｔｈｅｒｅｓｔｒｉｃｔｅｄｉｓｏｍｅｔｒｙｐｒｏｐｅｒｔｙ，ｔｈｅｌｏｗｅｒｂｏｕｎｄｃｏｎｄｉｔｉｏｎｓｔｈａｔｔｈｅｎｕｍｂｅｒｏｆｍｅａｓｕｒｅｍｅｎｔｓｓｈｏｕｌｄ ｓａｔｉｓｆｙａｒｅｄｅｄｕｃｅｄ，ａｎｄｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｒｅｅｍａｔｒｉｃｅｓｉｓａｎａｌｙｓｅｄ．Ｂｉｎａｒｙｓｐａｒｓｅｒａｎｄｏｍｍａｔｒｉｃｅｓａｒｅｔａｋｅｎａｓａｓｐｅｃｉａｌ ｅｘａｍｐｌｅｔｏｄｏｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓ．Ｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ，ｔｈｅｌ