logo资料库

压缩感知很好的综述.pdf

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：0.25M 资料格式：pdf 举报 版权申诉
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
资料共18页，剩余部分请下载后查看
    压缩感知 ∗ † 许志强 中国科学院数学与系统科学研究院, 计算数学与科学工程计算研究所, 科学与工程计算国家重点实验室, 100190, 北京 2012 年 1 月 12 日 摘要 压缩感知是近来国际上热门的研究方向. 其在信号处理中具有很好的应用前景. 此外, 它与逼近论、最优化、随机矩阵及离散几何等领域密切相关, 由此产生了一些漂 亮的数学结果. 本文综述压缩感知一些基本结果并介绍最新进展. 主要包括 RIP 矩阵 编码与 ℓ1 解码的性能, RIP 矩阵的构造, Gelfand 宽度, 个例最优性及 OMP 解码等. 1 引言 现实世界中, 人们经常需要对信号进行观测, 例如医学图像成像、CT 断层扫描等, 以 期通过观测信息对原始的信号进行重建. 由于计算机的离散化存储, 我们可将需重建的信 号 x 抽象为一 N 维向量, 可将对信号 x 的观测抽象为用一 n × N 的矩阵 Φ 与信号 x 进行 乘积. 例如在 CT 扫描中, 矩阵 Φ 通常选择为离散 Fourier 矩阵. 那么, 我们所观测的信息 为 y = Φx. (1) 人们自然而问: 为重建信号 x, 至少需要多少次观测? 由线性代数知识可知, 为使方程组 (1) 的解存在且唯一, 我们须选择 n ≥ N . 也就是说, 我们需要至少进行 n = N 次观测. 然 而, 现实世界中的自然信号通常具有一定规律性. 对这种规律性, 一种常用的刻画方式是自 然信号在一组基底表示下是稀疏的. 这里的“稀疏”是指它们用一组基底展开后, 大多数 系数为 0, 或者绝对值较小. 例如, 自然图像用小波基底展开后, 一般而言, 其展开系数大多 y 国家自然科学基金 (11171336) 及创新群体 (11021101) 资助. Email: xuzq@lsec.cc.ac.cn 1
    2 稀疏信号的恢复 2 数绝对值较小. 这也就是图像能够进行压缩的原理. 然而, 这同时为人们减少观测次数 n 从理论上提供了可能性. 因而, 压缩感知的主要任务为: 对尽量小的 n, 设计 n × N 观测矩 阵 Φ, 以及通过 Φx 快速恢复 x 的算法. 所以, 压缩感知的研究主要分为两方面：矩阵 Φ 的设计; 与反求信号 x 的算法. 本文主要介绍压缩感知的一些基本结果. 在每节里, 我们采用注记的方式介绍当前的 一些研究进展及研究问题, 同时提供与之相关的参考文献, 以使感兴趣的读者可进一步探 索. 本文组织结构如下: 第 2 节中我们介绍了稀疏信号精确恢复的编码、解码方法. 特别 是, 我们将介绍矩阵的零空间性质, 及 RIP 矩阵编码与 ℓ1 解码的性能. 我们在第 3 节中介 绍 RIP 矩阵的构造方法, 包括随机矩阵、结构随机矩阵及确定性矩阵. 在第 4 节中, 为理 解最优编码、解码对的性能, 我们介绍了 Gelfand 宽度与编码、解码对性能的关联. 我们 在第 5 节中介绍了编码、解码对在不同范数意义下的个例最优性. 最后一节简要介绍实现 解码的算法. 2 稀疏信号的恢复 为方便介绍压缩感知理论, 我们将信号的稀疏性简单理解为信号中非 0 元素数目较少. 我们所指的信号即为一向量 x ∈ RN . 我们用 Σs 表示 s-稀疏向量集合, 即 Σs := {x ∈ RN : ∥x∥0 ≤ s}, 这里 ∥x∥0 表示 x 中的非 0 元素数目. 所谓对信号 x0 ∈ RN 编码, 即指用一 n × N 的矩阵 Φ 与 x0 ∈ RN 进行乘积, 那么我们得到 y = Φx0. 此处, y ∈ Rn 即为我们所观测到的关于 x0 的信息. 所谓解码, 就是试图通过 y 反求 x0, 也 就是寻找一从 Rn 到 RN 的映射, 我们将该映射记为 ∆. 我们用 ∆(y) 表示反求结果. 一般 而言, 若 n < N , 则有无数个 x ∈ RN 满足 y = Φx. 因而, 只有借助信号稀疏性的特征, 我 们才有可能反求原始的信号 x0. 那么, 给定一编码、解码对 (Φ, ∆), 我们关心其性能, 即: ∥x0 − ∆(Φx0)∥X , 此处 X 为一给定范数. 本文中, 我们通常选择 X 为 ℓp 范数, 并用下标 p 表示 ℓp 范数. 当 x0 中非 0 元素数目较小的时候, 一种较为自然的解码 ∆0(y) 是如下规划问题的解: ∥x∥0 P0 : min x∈RN s.t. Φx = y.
    2 稀疏信号的恢复 3 这里, ∥x∥0 表示 x 中非 0 元素的数目. 我们用符号 ∆0(y) 表示 P0 的解. 也就是说, ∆0(y) 为在所有满足线性方程组 Φx = y 的向量中, 选择非 0 元素数目最少的. 如果我们对矩阵 Φ 加些许限制, 由 P0 定义的解码, 可精确恢复 s-稀疏向量: 定理 2.1 假定 Φ ∈ Rn×N 是一个任 2s 列均线性无关的矩阵. 我们选择解码为 ∆0, 那 么, 对任意的 x0 ∈ Σs, ∆0(Φx0) = x0. 根据定理 2.1, 如果我们选取观测次数 n = 2s, 那么就存在一编码、解码对 (Φ, ∆) 使得对 任意的 x0 ∈ Σs, 均有 ∆(Φx0) = x0. 这意味着: 如果我们希望恢复一个嵌入在 N 维空间的 s-稀疏向量, 那么 2s 次观测次数就足够了. 但是, 问题 P0 的求解是十分不平凡的. 事实上, P0 是一个 NP 完全问题 [14, 31]. 那么, 我们能否找到一个更为有效的解码算法? 一个令人惊讶的事实是, 如果矩阵 Φ 满足一定条 件, 那么回答则是肯定的, 但我们要在观测次数上付出些许代价. 我们现在将解码 ∆1(y) 定 义为如下问题的解: ∥x∥1 P1 : min x∈RN s.t. Φx = y. 如所知, P1 可转化为如下的线性规划问题： t1 + t2 + ··· + tN P2 : min t∈RN s.t. Φx = y −tj ≤ xj ≤ tj, j = 1, . . . , N tj ≥ 0, j = 1, . . . , N. 从一个简单的论证可看出, P1 的解与 P2 的解相同. 因此, 可找到有效的算法对 P1 求解. 但 是, 一个自然的问题是: P1 的解与 P0 的解等价吗? 或者是, 对什么样的观测矩阵 Φ, P1 的解与 P0 的解总一致? 为回答这一问题, 我们首先介绍矩阵的零空间性质. 零空间性质思想的主要出发点是： 解码通常是从集合 {x ∈ RN : Φx = y}. 中按一定规则挑选我们需要的元素. 由线性代数知识可知, 解集 {x ∈ RN : Φx = y} 可由 原始的信号 x0, 与矩阵的 Φ 的零空间 Ker Φ := {x ∈ RN : Φx = 0}
    2 稀疏信号的恢复 4 所确定. 因此, 人们考虑通过刻画矩阵 Φ 的零空间, 从而给出 P1 解与 P0 解一致的充 要条件. 我们首先介绍零空间性质的定义. 为描述方便, 我们介绍如下符号: 对于指标集 T ⊂ {1, . . . , N} 及向量 v ∈ RN , 我们将 v 中指标在 T 中的元素取出, 形成一个新的向量, 标记为 vT ∈ R#T . 我们用 T c 表示 T 的补集. 类似的, 我们可定义矩阵 ΦT . 定义 2.1 我们称矩阵 Φ 满足 s-阶零空间性质, 如果对任意的 v ∈ Ker Φ, 均有 ∥vT∥1 < ∥vT c∥1, 对任意的 T ⊂ {1, . . . , N}, #T = s. 直观上, 我们将零空间性质理解为 Ker Φ 的非 0 元素较为均匀的分布, 不会明显的集中于 某 s 个元素上. 采用零空间性质, 我们有 定理 2.2 我们选择解码为 ∆1. 那么, 对任意的 x ∈ Σs, 如果和仅仅如果 Φ 满足 s-阶零空间性质. ∆1(Φx) = x 注 2.1 用类似于零空间性质的方式, 描述 ∆1 解码可恢复 s-稀疏信号, 在人们研究 L1 最佳逼近时就已经出现 (参考 [33]). 与定理 2.2 一致的形式首先出现在 [23]. 此外, 文 [18, 19] 也隐含了类似的结果. 虽然可以用零空间性质给出 P1 的解与 P0 的解一致的充要条件. 但是, 零空间性质并 不容易操作, 无论在理论还是计算方面. 也就是说, 给一个矩阵 Φ, 难以从理论上证明其是 否满足零空间性质, 也不容易在计算机上快速验证. 因而, 人们考虑了另外一种刻画方式, 即是所谓的矩阵 RIP 性质 (Restricted Isometry Property). 我们首先介绍 RIP 性质的定义 [9]. 我们说矩阵 Φ 满足 s-阶 RIP 性质, 如果存在常数 δs ∈ [0, 1) 使得 (1 − δs)∥x∥2 ≤ ∥Φx∥2 ≤ (1 + δs)∥x∥2 对任意的 x ∈ Σs 成立. 实际上, (2) 等价于 Grammian 矩阵 Φ ⊤ T ΦT 所有特征值位于区间 [1 − δs, 1 + δs], 这里 #T ≤ s. 我们称 δs 为 RIP 常数. (2) 我们首先看一下如何从直观上理解 RIP 矩阵. 倘若 δs = 0 , 那么矩阵 Φ 为一标准正交 矩阵. 因而也是一方阵. 然而在压缩感知中, 我们希望矩阵 Φ 是“扁” 的, 也就是 n < N , 同 时保留类似于正交矩阵的特征. 因而, RIP 矩阵的定义 (2), 事实上刻画了矩阵 Φ 中任取 s 列所形成的 n × s 矩阵接近于正交矩阵的程度. RIP 常数 δs 越接近于 0, 其任取 s 列所形成 的子矩阵也就越接近于正交. 从某种意义上来说, 性质也就越好. 下面定理给出了解码 ∆1 能够精确恢复 s-稀疏信号的一个充分条件.
    2 稀疏信号的恢复 定理 2.3 ([6, 7]) 假定编码矩阵 Φ 满足 2s 阶 RIP 性质, 且 RIP 常数 δ2s ≤ √ 我们选择解码 ∆1. 那么, 对任意的 x ∈ Σs, 均有 5 2 − 1. ∆1(Φx) = x. 上述定理表明, 我们可用 RIP 矩阵编码、∆1 解码精确恢复 s-稀疏信号. 然而, 现实世 界中的信号并非严格稀疏的, 通常仅仅是近似稀疏. 对于此类信号, 如果我们仍然用 RIP 矩阵 Φ 进行编码, 选则解码为 ∆1, 那么我们能较好的恢复非稀疏信号吗? 令人惊讶的是, 我们仍然能较好的完成任务. 为介绍这方面的结果, 我们首先介绍最佳 s-项逼近误差的概 念. 给定范数 ∥ · ∥X , 那么信号 x ∈ RN 的在范数 ∥ · ∥X 意义下最佳 s-项逼近误差为 对于 K ⊂ RN , 我们令 σs(x)X := min z∈Σs ∥x − z∥X . σs(K)X := max x∈K σs(x)X . 下面定理指出, 对于一般信号, 我们采用 RIP 矩阵编码与用 ∆1 作解码, 那么恢复效果可用 ℓ1 范数意义下的最佳逼近误差刻画. 定理 2.4 假定编码矩阵 Φ 满足 2s 阶 RIP 性质, 且 RIP 常数 δ2s ≤ √ 2 − 1 . 我们选择 解码为 ∆1. 那么对任意的 x ∈ RN , 我们有 ∥∆1(Φx) − x∥2 ≤ C0 σs(x)1√ s , 此处 C0 为一常数. 常数 中, E. Candes 将RIP 常数改进为 δ2s ≤ √ 注 2.2 定理 2.3 与定理 2.4 首先在[7] 中被证明. 但给出的 RIP 常数较为粗糙. 在 [6] 2 − 1. 仍有一些论文考虑改进定理 2.3 中的 RIP √ 2 − 1 [4, 21]. 特别是，Mo 和 Li 将该常数改进为 δ2s < 0.4931 [30]. 此外, Davies 和 Gribonval 建构一个例子表明, 如果 δ2s ≥ 1√ , 那么 ∆1 解码不能恢复一些 s-稀疏信号. 注意到这些研究均是针对 δ2s, 也就是要求矩阵满足 2s 阶 RIP 条件. 在 [5] 中, Cai, Wang 和 Xu 考虑了矩阵满足 s-阶 RIP 条件的情况, 给出了 P1 能恢复 s-稀疏信号的充分条件为 δs < 0.307. 此外, 我们特别指出, 借助离散几何中的多面体理论, 在文 [16] 中, Donoho 给 出了 ∆1 解码能精确恢复 s-稀疏信号的充要条件. 2 注 2.3 对于 0 < p < 1, 人们也考虑了如下定义的 ∆p 解码: ∥x∥p min x∈RN s.t. Φx = y.
    3 RIP 矩阵 ∑ 这里 ∥x∥p := ( ∆p 解码所需观测次数较少, 但解码复杂度会有所增加[39, 13]. N j=1 |xj|p)1/p. 事实上, 当 0 < p < 1, ∥ · ∥p 为一拟范数. 相比于 ∆1 解码, 6 注 2.4 在本文中, 我们假定信号的稀疏性指非 0 元素较少. 但是, 很多应用问题里面, 信号是在一“字典”或者紧框架表示下是稀疏的. 对于此类情况, 文 [11] 进行了研究. 并 将定理 2.4 进行了推广. 但是, 这个方向仍值得进一步深入探索. 我们现在回到本文开始所提出的问题： 如果选择解码为 ∆1, 为精确恢复所有 s-稀疏信号, 观察次数 n 最少应为多少? 文 [22] 给出了如下定理: 定理 2.5 假定 Φ ∈ Rn×N 及解码为 ∆1. 那么, 如果 ) ∆1(Φx) = x, 对任意 ( 则 x ∈ Σ2s, n ≥ c1s log N c2s , t 0.455 且 c2 = 4. ( 这里 c1 = 1 log 9 根据上述定理, 如果解码选择为 ∆1, 那么我们至少需要进行 n = O(s log 能精确恢复 s-稀疏信号. 这个下界能够达到吗? 也就是说, 对于 n = O(s log ), 我们能 否构造观测矩阵 Φ ∈ Rn×N , 使得对任意 x ∈ Σs, 均有 ∆1(Φx) = x? 根据定理 2.3, 我们可 将该问题归结为能否构造满足 s-阶 RIP 条件的矩阵 Φ ∈ Rn×N 使得 n = O(s log )? 我 们将在下节回答该问题. ) 次观测, 才 N s ) ( ) ( ) N s N s 3 RIP 矩阵 根据定理 2.3 和定理 2.4, 为保证 ℓ1 解码能恢复稀疏或者近似稀疏信号, 我们需要构造 RIP 矩阵. 我们希望对于给定的 n, N ∈ Z, 构造一 n × N 的矩阵 Φ, 以使其对尽量大的 s 满 足 s-阶 RIP 条件. 那么, 如何构造此类矩阵? 当前的主要构造方法有：随机矩阵、结构随 机矩阵与确定性矩阵.
    3 RIP 矩阵 3.1 随机矩阵 7 我们考虑两类随机矩阵：Gaussian 随机矩阵与 Bernoulli 随机矩阵. 所谓 Gaussian 随 机矩阵, 即指矩阵中的元素 ϕi,j 是独立的随机变量且服从如下分布: ϕi,j ∼ N (0, 1 n ) 即服从期望为 0, 方差为 1 n 的 Gaussian 分布. 所谓 Bernoulli 矩阵, 即指矩阵 Φ 中的元素以 或 − 1√ 相同的概率取 1√ n . n 定理 3.1 假定 n × N 的矩阵 Φ 是一个 Gaussian 或者 Bernoulli 随机矩阵. 那么, 当 s ≤ C1n/ log(N/s) 矩阵 Φ 是一个 s-阶 RIP 矩阵的概率不小于 1 − exp(−C2n), 此处常数 C1, C2 仅仅依赖于 RIP 常数 δ. 注 3.1 一个类似于定理 3.1 的结果最早由 Kashin 得到 [24]. 文 [10, 41] 中也给出了 定理 3.1 的证明. 一个比较简单的证明方法是 [1] 中所介绍的. 此外, 文 [1] 也给出了 RIP 性质与 Johnson-Lindenstrauss 引理的关联. 注 3.2 定理 3.1 表明 Gaussian 随机矩阵或 Bernoulli 随机矩阵满足 s = O(n/ log(N/s)) 阶的 RIP 性质. 根据逼近论中的宽度理论, 对于给定的 n, N ∈ N, 这里的 s 已经达到了最 佳阶. 3.2 确定性矩阵 虽然随机矩阵能产生尺寸接近最优的 RIP 矩阵. 在工程实际中, 人们更希望构造一个 确定性 RIP 矩阵. 因为确定性矩阵更利于工程设计, 此外, 从构造解码算法角度来看, 确 定性矩阵利于降低内存、设计快速的恢复算法等. 然而, 现在仍然缺少令人满意的确定性 RIP 矩阵构造方法. 当前的构造方法主要是基于矩阵的列相干性. 假定矩阵 Φ = (a1, . . . , aD) ∈ Cn×N , 这里 n ≤ N . 我们假定矩阵 Φ 中的列元素标准 化, 即 ∥ai∥2 = 1. 矩阵 Φ 的列相干性定义为 M(Φ) := max i̸=j |⟨ai, aj⟩|.
    3 RIP 矩阵 下式给出了 M(Φ) 的一个下界, 也称为Welch 界 [43] N − n (n − 1)N M(Φ) ≥ √ 8 (3) . 当等号成立的时候, 我们称矩阵 Φ为最优 Grassmannian 框架. 文 [20] 中指出, 只有当 N ≤ n2, 等号才有可能成立 (参考 [40]). 下面定理显示了矩阵的列相干性与 RIP 性质之间的关联 [15, 2]. 定理 3.2 假定 a1, . . . , aN 是矩阵 Φ 的列元素且其列相干性为 µ. 那么, 矩阵 Φ 满足 RIP 常数为 δs = (s − 1)µ 的 s-阶 RIP 性质. ( 人们能够构造出满足条件 ) log N√ n log n µ = O 的矩阵 (参考 [25, 15, 45]). 我们在此介绍作者在 [45] 中提出的一种构造方法, 其主要利用 了数论中的 Weil 指数和定理 [42]: 定理 3.3 ([42]) 假定 p 是一个素数. 假定 f (x) = m1x + ··· + mdxd, 且存在一个 j, 给定正整数 q 和 d, 我们下面构造一 n × N 矩阵 Φ, 这里 n ≥ 2q + 1 为素数, 且 N = (2q + 1)d. 那么, 矩阵 Φ 的第 j 行定义为 exp(2πi⟨xj, k⟩) √ n k∈[−q,q]d ∈ C(2q+1)d , (4) xj = [j, j2, . . . , jd]/n mod 1. 下面的定理刻画了由 (4) 所定义的矩阵 Φ 的列相干性 [45]. 定理 3.4 给定正整数 q 和 d, 令 n ≥ 2q + 1 为素数, 且 N = (2q + 1)d. 假设 n × N 矩 阵 Φ 由 (4) 定义. 那么, M(Φ) ≤ d − 1√ n . 1 ≤ j ≤ d, 使得 p - mj. 那么 p∑ 2πif (x) p e x=1 [ Φj,· = 这里 √ p. ≤ (d − 1) ]
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料