《压缩感知_很好的综述_2016》.pdfVIP

压缩感知∗ 许志强† 中国科学院数学与系统科学研究院 计算数学与科学工程计算研究所 科学与工程计算国家重点实验室 北京 年 月 日 摘要 压缩感知是近来国际上热门的研究方向. 其在信号处理中具有很好的应用前景. 此外, 它与逼近论、最优化、随机矩阵及离散几何等领域密切相关, 由此产生了一些漂 亮的数学结果. 本文综述压缩感知一些基本结果并介绍必威体育精装版进展. 主要包括RIP 矩阵 编码与ℓ 解码的性能, RIP 矩阵的构造, Gelfand 宽度, 个例最优性及OMP 解码等. 引言 现实世界中, 人们经常需要对信号进行观测, 例如医学图像成像、CT 断层扫描等, 以 期通过观测信息对原始的信号进行重建. 由于计算机的离散化存储, 我们可将需重建的信 号x 抽象为一N 维向量, 可将对信号x 的观测抽象为用一n × N 的矩阵Φ 与信号x 进行 乘积. 例如在CT 扫描中, 矩阵Φ 通常选择为离散Fourier 矩阵. 那么, 我们所观测的信息 为 y = Φx. (1) 人们自然而问: 为重建信号x 至少需要多少次观测 由线性代数知识可知, 为使方程组 (1) 的解存在且唯一, 我们须选择n ≥ N . 也就是说, 我们需要至少进行n = N 次观测. 然 而, 现实世界中的自然信号通常具有一定规律性. 对这种规律性, 一种常用的刻画方式是自 然信号在一组基底表示下是稀疏的. 这里的“稀疏”是指它们用一组基底展开后, 大多数 系数为0, 或者绝对值较小. 例如, 自然图像用小波基底展开后, 一般而言, 其展开系数大多 国家自然科学基金 及创新群体 资助 1 稀疏信号的恢复 2 数绝对值较小. 这也就是图像能够进行压缩的原理. 然而, 这同时为人们减少观测次数n 从理论上提供了可能性. 因而, 压缩感知的主要任务为: 对尽量小的n 设计n × N 观测矩 阵Φ 以及通过Φx 快速恢复x 的算法. 所以, 压缩感知的研究主要分为两方面：矩阵Φ 的设计; 与反求信号x 的算法. 本文主要介绍压缩感知的一些基本结果. 在每节里, 我们采用注记的方式介绍当前的 一些研究进展及研究问题, 同时提供与之相关的参考文献, 以使感兴趣的读者可进一步探 索. 本文组织结构如下: 第2 节中我们介绍了稀疏信号精确恢复的编码、解码方法. 特别 是, 我们将介绍矩阵的零空间性质, 及RIP 矩阵编码与ℓ1 解码的性能. 我们在第3 节中介 绍RIP 矩阵的构造方法, 包括随机矩阵、结构随机矩阵及确定性矩阵. 在第4 节中, 为理 解最优编码、解码对的性能, 我们介绍了Gelfand 宽度与编码、解码对性能的关联. 我们 在第5 节中介绍了编码、解码对在不同范数意义下的个例最优性. 最后一节简要介绍实现 解码的算法. 稀疏信号的恢复 为方便介绍压缩感知理论, 我们将信号的稀疏性简单理解为信号中非0 元素数目较少. 我们所指的信号即为一向量x ∈ N . 我们用Σs 表示s-稀疏向量集合, 即 Σ := {x ∈ N : ∥x ∥ ≤ s}, s 0 这里 ∥x ∥ 表示x 中的非0 元素数目