1 Bit Compressed Sensing Reconstruction Algorithm Based on Blind Operation
6
0
0
全文
(2) 第２ 期 闫 斌，等：一种基于盲运算的１ 比特压缩感知重建算法 ２６５ 大 部 分 的 量 化 模型是在测量值上加入有限的加性 根 （２），简 化 模 型 为 据 式 （１）和 （３） 噪 声 ，这 对 于 高 效率量化来说是足够的 ，但是对于 ｘ＾ ＝ ａｒｇｍｉｎ ｘ ， ｓ． ｔ． ｙ ＝ Ａｘ， 低 比 特 率 的 粗 糙 测 量 值 就 显 得 不 足 ，所 以 选 取 一 个 式 （３）中 ：·表示计算其中非零元素的个数 ，也 合 适 的 量 化模型对于１ 比特压缩感知非常重要 ． 数 称 之 为ｌ 范 ． 特 压 缩 感 知 把 测 量 值量化成１ 比特 ，具有以下 这 １比 是 一 个ＮＰ 难 问 题 ，在高维空间是非常难实 几 个 优 点 ：第 一 ，测量值只有－ １ 和１，对硬件设施 现 通 过转化成ｌ 范数等价的凸优化等价模 的 ．故 来 说 很 容 易 实 现 ；第二 ，量化器通过一个简单的比 型 来 求 解 ： ＾ 较 器 来 实 现 ，既高效 ，成本也低 ；第三 ，１ 比特量化 ｘ ＝ ａｒｇｍｉｎ ｘ ， ｓ． ｔ． ｙ ＝ Ａｘ． （４） ［ ， ］ 对非线性失真不敏感 ，具有较好的鲁棒性 于 定义１（一 ．关 致 不 确 定 性 原 理 ） 对 于 测 量 矩 １比 特压缩感知的理论模型 ，最早是由ＰＴ Ｔ． 阵Ａ 的 选 取 ，Ｔａｏ、Ｄｏｎｏｈｏ、Ｃａｎｄｅｓ 等给出了构建压 出的 ，文献［６ ］ 缩 Ｂｏｕｆｏｕｎｏｓ 和 Ｒｉｃｈａｒｄ Ｇ． Ｂａｒａｎｉｕｋ 提 感知测量矩阵需满足的ＵＵＰ，即对于任意的Ｋ 把ＦＰＣ（ｆｉｘｅｄ ｐｏｉｎｔ ｃｏｎｔｉｎｕａｔｉｏｎ）算 法 引 入 到１ 比 特 稀 疏 向 量ｘ，ε 为 一 个 非 常 小 的 负 数 ，如 果 满 足 压 缩 感 知 中 ，其 改 进 在 于 每 次 迭 代 过 程 中 都 把 梯 度 （１ － ε）Ｍ ｘ ≤ Ａｘ ≤（１ ＋ ε）Ｍ ｘ ，（５） Ｎ Ｎ 值 投 影 到 圆 上 ，再把得到的解进行归一化处理 ，这 称Ａ 满 足集合大小为Ｋ、参数为ε 的一致不 比 传 统 的ＣＳ 算法要理想很多 献［７ ］在此基础 则 ．文 理在一定程度上保证了可压 ． ＵＵＰ 定 定 性 原理 上 进 行 了 拓展 ，提出了ＭＳＰ （ｍａｔｃｈｅｄ ｓｉｇｎ ｐｕｒｓｕｉｔ） 确 信 号 恢 复 过 程 的 鲁 棒 性 和 稳 定 性 ，但 它 不 是 充 分 算 法 法 采 用回溯原理 ，扩大了支撑集的范 缩 ． ＭＳＰ 算 要 条 件 ． 能 高１２ ｄＢ 和 必 围 ，重 建 效 果 比 一 致 重 建 、ＣｏＳａＭＰ 性 是１ 比 特 压 缩 感 知 的 一 个 重 要 里程碑 于 １． ２ 压缩感知算法 ２０ ｄＢ ， ．由 前 从 式 （４）中 求解出ｘ 的算法比较多 ，其中 法 是 在 稀 疏度已知的前提下进行的信号恢 目 ＭＳＰ 算 贪 婪 算 法 因 其 结 果 简 单 、 运 算 较 小 等 优 点 而 被 广 泛 复 ，而 现 实 中 信 号的稀疏度很多都是未知的 ，这导 ［ ］ 应用 法 和ＯＭＰ ． ＭＰ （ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔｓ ）算 致ＭＳＰ 算 法 在 实 际 中 应 用 变 得 很 难 ． ［ ］ 法是 贪 婪 算 法 的 本 文 在ＭＳＰ 算 法 的 基 础 上 ，借 鉴 文 献 ［８］中的 （ｏｒｔｈｏｇｏｎａｌ ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔ）算 向前／ 向后迭代思路 ，提出了ＦＢＭＳＰ （ｆｏｒｗａｒｄ 早 法 是 在ＭＰ 的 基 础 上 增 加 了 对 每 期 代 表 ，ＯＭＰ 算 ｂａｃｋｗａｒｄ ｍａｔｃｈｉｎｇ ｓｉｇｎ ｐｕｒｓｕｉｔ ）算 法 ，摒弃了ＭＳＰ 一 步 得 到 的 原 子 进 行 正 交 化 的 过 程 ，在 保 证 了 精 度 ［ 算 法 中 以 稀 疏 度 为 先 验 知 识 的 迭 代 ，实 现 了 稀 疏 度 的同时 ，ＯＭＰ 算法收敛速度变快了 ，ＲＯＭＰ ］ 未 知 条 件 下 的 重 构 外 由 于 迭 代 过 程 中 每 次 引 入 （ｒｅｇｕｌａｒｉｚｅｄ ｏｒｔｈｏｇｏｎａｌ ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔ）也 ．另 是ＭＰ 的 的 都 是 最 好 的 原子 ，减少了算法的复杂度 ，提高了 一 来 从 原 子 的 角 度 出 发 又 衍 生 了ＳｔＯＭＰ 种 变 型 ．后 重 构 精 度 ． （ｓｔａｇｅｗｉｓｅ ｏｒｔｈｏｇｏｎａｌ ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔ ）算法［ ］，增 加 了 一 个 软 阈 值 参 数 来 确 保 迭 代 中 保 留 的 项 ，使 得 论体系 １ ＣＳ 理 法得到了广泛的应用 后又引入回 ＳｔＯＭＰ 算 ． 随 ［ ］ ［ ］ 缩感知理论 １． １ 压 ，产生了ＳＰ （ｓｕｂｓｐａｃｅ ｐｕｒｓｕｉｔ ）和 溯 的思想 ［ ］ 定输入实信号ｘ∈Ｒ ，如果它是Ｋ 稀疏的 ， ＣｏＳａＭＰ （ｃｏｍｐｒｅｓｓｉｖｅ ｓａｍｐｌｉｎｇ ｍａｔｃｈｉｎｇ ｐｕｉｓｕｉｔ） 假 ，那么它可以通 等 即 其 中 有Ｋ（Ｋ Ｎ）个元素是非零 算 法 ，这 类 算 法 的 主 要 特 点 是 在 已 选 的 原 子 基 础 过Ｍ ＝ Ｏ（Ｋｌｇ（Ｎ ／ Ｋ））个 线性测量向量ｙ 来获得精 上 多 了 一 步 回 删 的 过 程 ，把 一 些 内 积 值 较 小 的 坏 原 确 重 构 ，可 以 用 如 下 公 式 来 表 示 ： 子 剔 除 掉 ，在 一 定 程 度 上 提 高 了 运 行 效 率 和 重 构 精 （１） 度 ｙ ＝ Ａｘ， ｙ ∈Ｒ ， ，同 时 文 献［１６ ］详述了ＣｏＳａＭＰ 算法的合理性 ． 式 （１）中 ：Ａ∈Ｒ 是 测 量 矩 阵 ． 有 学 者 最 近 提出了ＦＢＰ （ｆｏｒｗａｒｄ ｂａｃｋｗａｒｄ ｐｕｒｓｕｉｔ） 由 于Ｍ × Ｎ 不 是 方 阵 ，不 能 进 行 传 统 意 义上的 算 法［］，其创新在于改进了ＳＰ 和ＣｏＳａＭＰ 支撑集 求 逆 过 程 ，所以式（１ ）的求解是一个病态过程 ，但 的 候 选 范 围 ，效 果 得 到 了 较 大 提 升 ． 是 由 于 信 号 的 稀 疏 性 ，使得式（１ ）的求解变得有可 １． ３ １ 比特压缩感知 ．为 能 了能够从输入信号中恢复Ｋ 个稀疏值 ，必须 １ 比 特 压 缩 感 知 是 对压缩感知的一个衍生 ，其 保 证Ａ 的 不 相 关 性 ，即 对 于 任 意 的ｘ ≠ｘ ， 主 要 特 点 是 通 过量化器来进行比较 ，得到量化值 ． （２） 计 Ａｘ － Ａｘ ＝ Ａ（ｘ － ｘ ）≠０． 算 测量矩阵Ａ∈Ｒ 的每一行与原始信号ｘ ∈ ０. ０. ０. １. １. ２ ９. ２. ２. ２. Ｍ×Ｎ. １０. １１. １２. １３. １２. １４. Ｎ. １５. Ｍ. Ｍ. ７. １. ２. Ｍ×Ｎ. １. ２. １. ２.
(3) 西 南 交 通 大 学 学 报 第５０ 卷 内 积 ，得 到的每一个测量值通过以下公式进 ＦＢＭＳＰ 算法不需要稀疏度Ｋ 为先验信息 ，采用回 Ｒ 的 行 量 化 ： 数 来 控 制 支 撑 集 迭 代 过 程 中 溯 思 想 ，引 入α 和β 参 ｙ ＝ ｓｉｇｎ（Ａｘ）， （６） 的 支 撑 集 大 小 始 化 过 程 中 设 定 固 定 支 撑 集 个 数 ．初 ，符 号 函 数ｓｉｇｎ（ｙ ）＝ ｙ ／ ｙ 适 用于每 α，取α 个 在 式 （６）中 支 撑 集 和 上一步迭代得到的最优支撑集 个 测 量 值 ，每 个 测量值占用１ 个比特 ，所以测量值 的 并 集 作 为 当 前 支 撑 集 ，然 后 在 归 一 化 条 件 下 计 算 仅 代 表 测 量 次数 ，也代表测量比特数 由于 测 Ｍ不 ．又 ， 量 符 号 值 、测 量矩阵和当前最优解ｘ 三者的积 每 次 取 的 是测量值的符号（＋ １，－ １ ），而不是精确 选 出 最 优 的β 个 值 ，最 后 完 成 删 减 、归 一 化 和 更 新 ． 的 测 量 值 ，这 使 得测量精度下降 了提高测量精 在 ．为 最 后 一 步 过 程 中 ，最 优 解 的 选 取 对 信 号 重 构 度 ，可 以 增 加 测 量 次 数 ，甚 至 多 于 信 号 的长度Ｎ，此 有 着 重 大 的 影 响 ，由于稀疏度Ｋ 未知 ，β 值如果过 时 的Ｍ ／ Ｎ 可以认为是信号的“比特／ 系数”． 测量 大 会 引 入 较 大 的 误 差 ，所 以 初 始 化 一 个 较 小 的β 作 值 取 值 如 下 ： 为 最 优 解 的 个 数 ，以 单 步 步 长 为１ 来 逐 步 增 加 最为 号 重 构 过 程 中 ，存 在 算 法 迭 代 终 止 条 件 ，根 稳 妥 ．信 （Ａｘ ）{ ≥＜ ００，， ｙｙ ＝＝ ＋－ １１， （ ７） 据 目 前 贪 婪 迭 代 算 法 ，用 得 最 多 的 误 差 判 别 迭 代 停 ， ＾ ＾ 某 个 即 止 标 准 是 利 用 前 后 两 次 迭 代 的 差ｘ － ｘ 与 ＾ ｙ ｓｉｇｎ（Ａｘ）≥０． （８） 阈 值 的 关 系 果 大 于 阈 值 ，则 增 加β 的 值 ，在β 增 ．如 由 式 （８）获得的ｙ 即为测量向量每一次获得 加 的 过 程 中 ，支 撑集逐渐扩大 ，当误差小于某个阈 的 测 量 值 ，由 于 测 量 值 只 包 含 了 符 号 信 息 而 丢 失 了 值 止 增加 ，此时的稀疏度Ｋ 就是需要的稀 时 ，β 停 幅值信息 ，故加入能量约束让其限制在一个 疏 度 ． ： 圆ｌ 上 体 算 法 流 程 如 下 ： ＦＢＭＳＰ 具 输 入 ：测 量 符 号ｙ∈｛± １ ｝，测量矩阵Ａ，向前 ＝ １． （９） ｘ ＝ ( ∑ｘ ) 制α ＝ ８，向 后 控 制β ＝ １，阈 值ε ＝ ０． ００６． 按 照 式 （９ ）进行能量限制 ，减少了搜索空间 ， 控 初 始 化 ：迭 代计数ｌ ＝ ０，最大迭代次数ｌ ＝ 在 信 号 重 建 过 程 中 具 有 重 要 作 用 ． 初 始 化Ｋ 稀 疏 的 信 号 估 计ｘ＾ ． １５０ ， （１）增 加 迭 代 次 数 前／ 向后符号匹配追踪 ２ 向 ｌ ＝ ｌ ＋ １． 法 是 典 型 的１ 比 特 压 缩 感 知 重 构 算 法 ， ＭＳＰ 算 （２）计 算 估 计 的 测 量 值 大多数贪婪算法一样 ， 其 测 量 值 由式（６ ）得到 ．和 ｄｉａｇ（ｙ）Ａｘ＾ ． 第ｌ 次 迭 代 后 ，ＭＳＰ 算 法 产 生 一个由测量信号及其 ｙ（珓３＝）识 符 号 标 志 支 撑 集 形 成 的 信 号 估 计ｘ＾ ． 每 次 迭 代 都 更 新 上 一 次 ｒ ＝ （ｙ珓）别 ， 的 估 计 值 ，直 到 算 法停止 法借鉴了回溯顺 这 ． ＭＳＰ 算 ． 表 取 负 的 功 能 函 数 （· ）代 序 编 码 理 论［ ］，在每次迭代的过程中都最小化以 里 （４）计 算 修 正 的 信 号 代 理 下 式 子 ： ｓ ＝ Ａ ｄｉａｇ（ｙ）ｒ ， ｄｉａｇ（ｙ）Ａｘ ， （１０） 其 中 ：信 号 代理是一个系数 ，是算法第（６ ）步求导 其 中 ：ｄｉａｇ（ｙ）表示把测量值ｙ 的每个元素依次放 过 后 的 系 数 ，通 过 信 号 代理可以确定算法第（５ ）步 在 主 对 角 矩 阵的主对角线上 ；（· ） 代表取负元素 的 撑 集 ． 的 功 能 ，即 保 留 负 元 素 ，正 元 素 置 零 ，该 功 能 等 价 于 支 定 正 确 的 支 撑 集 惩 罚 函 数 ，当 信 号 精 确 重 构 的 时候 ，ｙ 和Ａｘ 的符号 （５）确 ）∪ｓｕｐｐ（ｘ＾ ）， Ｔ ＝ ｓｕｐｐ（ｓ 相 同 ，此 时 的 惩 罚 力 度 为０． 中 ：ｓｕｐｐ（· ）代 表 向 量 的 支 撑 集 ；ｘ 是 向 量ｘ 中 该 算 法 对 信 号进行重构需要信号的稀疏度Ｋ 式 ． 最 大 元 素 为 先 验 信 息 ，但 在 实 际 应 用 中 ，这 一 信 息 很 难 获 取 ， 的α 个 （６）在 支 撑 集 上 进 行 一 致 重 建 ． 这 使 得 算 法 的 实 际 应 用 受 到 限 制 基 于ＭＳＰ 算法的不足和缺点 ，本文提出了向 ｂ ＝ ａｒｇｍｉｎ （ｄｉａｇ（ｙ）Ａｘ） ， ｓ． ｔ． ｘ ＝ １ 且 ｘ ＝ ０． 前／ 向 后 符号匹配追踪（ｆｏｒｗａｒｄ ｂａｃｋｗａｒｄ ｍａｔｃｈｉｎｇ ．和 ＭＳＰ 算 法 法不同的是 ， 该步是在归一化条件下求二范数平方的最小 ｓｉｇｎ ｐｕｒｓｕｉｔ，ＦＢＭＳＰ）算 ２６６ Ｎ. ｉ. ｉ. ｉ. ｉ. ｉ. ｉ. ｌ. ｉ. ｌ －１. ｉ. ｉ. ２. Ｎ. １／２. ２ ｉ. ２. ｉ. ｍａｘ. ０. ｌ. ｌ －１. ｌ. －. ｌ. ｌ. －. １３. Ｔ. －. ２ ２. ｌ. ｌ. －. ｌ. ｌ. ｌ －１. α. α. －. Ｔ. ｘ. ２. Ｔｃ. ２ ２.
(4) 第２ 期 闫 斌，等：一种基于盲运算的１ 比特压缩感知重建算法 ２６７ 量 间隔为３０，最大测量次数为４ ０９６，实验结果 值 最 优 化 过 程 是 在 支 撑 集Ｔ 下 进 行 的 ，ｘ ＝ ０ 测 ．该 示 图２ 所 ． 表 示 支 撑 集Ｔ 的 补 集所对应的ｘ 全为０． 第（６ ）步 如 利 用 的 是 梯 度 下 降 法 来 求 解 ，每 次 迭 代 的 步 长 都 进 行 了 归 一化处理 ，一直迭代到满足迭代停止条件 为 止 ． （７）删 减 、归 一 化 、更 新 估 计 值 ｂ ， ｘ＾ ＝ ｂ 式 中 ：ｂ 是指在第ｌ 次迭代中取向量ｂ 中的前 最大元素 ，剩余的元素都删减掉 ，然后按照 β个 第 （７）步 的 公式进行归一化 ，得到ｘ＾ ，用ｘ＾ 替换 成 更 新 ． ｘ＾ 完 图１ Ｍ ＝ ５１２ 信 号 重 构 Ｆｉｇ． １ Ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｉｎ （８）稀 疏 度 估 计 ｔｈｅ ｃａｓｅ ｏｆ Ｍ ＝ ５１２ ＾ ＾ 如 果ｘ － ｘ ≥ε，则β ＝ β ＋ １． （９）限 制 条 件 如 果Ａ ｄｉａｇ （ｙ）ｘ＾ ＞ ε 或者Ａ ｄｉａｇ （ｙ ）ｘ＾ ＝ ０， 则 转 至 步 骤 （１０）． 转 至 步 骤 （１），否 在 这 里 为 了 防 止 程 序 陷 入 死 循 环 ，额 外 增 加 一 个 迭 代 停 止 条 件 ，即 如 果ｌ ＞ ｌ ，转 至 步 骤 （１０）． ＾ （１０）输 出ｘ ． 法 中的步骤（１ ）～ （７ ）实现的是信 ＦＢＭＳＰ 算 号 的 重 构 ，步骤（８ ）实现的是稀疏度的估计 ，在步 骤 （８）中 ，ε 值 的 大 小 决 定 了 向 下 迭 代 的 截 止范围 ， 图２ ＦＢＭＳＰ 算 法 对 不 同 稀 疏 度 的 预 测 Ｆｉｇ． ２ ＦＢＭＳＰ ａｌｇｏｒｉｔｈｍ ｕｓｅｄ ｉｎ 从 第４ 部 分 的 实 验 结 果 可 以 看 出 ，当 向 后 迭 代 到某 ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｓｐａｒｓｉｔｉｅｓ 种 程 度 的 时 候 ，信 号 残 差 已 经 非 常 小 了 ． 从 图２ 可 以 看 出在稀疏度Ｋ 取不同值的情况 验结果及分析 ３ 实 下 ，ＦＢＭＳＰ 算 法 随 着 测 量次数的增加 ，都能寻找到 下 实 验 均 在ＣＰＵ Ｉｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）２ Ｄｕｏ、 相 以 对 正确的稀疏度Ｋ，从而实现稀疏度的正确 主 频２． ００ Ｇｂｉｔ ／ ｓ、内 存２． ００ ＧＢ 的３２ 位机上运行 估 计 ． 的Ｍａｔｌａｂ２０１２ 中 ． 进 行 的 （３）α 和β 值 的 选 取 （１）信 号 重 建 仿 真 本 文中 ，α 和β 值的选取是ＦＢＭＳＰ 算法的核 为 了 说 明ＦＢＭＳＰ 算法的重构能力 ，实验中输 心 所 在 ，恰 当 地 选 取α 和β 值 能 够 较 大 地 提 升 算 法 入 信 号 取 稀 疏 度Ｋ ＝ ２０，长度Ｎ ＝ ２５６ 的归一化随 的 性 能 于 稀 疏 度未知情况下 ，β 必须取１，否则 ．由 机 信 号 ，测量矩阵Ａ 采用Ｍ × Ｎ 的高斯随机矩阵 ． 不 能 正 确 地 预 测 稀 疏 度 ．实 验 中 取α ＝ ２：２：４０，β ＝ 图１ 是在Ｍ ＝ ５１２ 情况下原始信号和重构信号的 １，其 他 条 件 不 变 的 情 况 下 ，取１００ 次 实 验 的 平均值 对 比 ． ． 作 为 结 果 ，实 验 结 果 如 图３ 所 示 从 实 验 结 果 可 以 看 出 ，在 采 样 次 数 是 信 号 长 度 由 图３ 可 以 看 出 ，随 着α 的 增 加 ，重构ＭＳＥ 总 、仅 取 测量值符号的前提下 ，也能较好地重构 体 ２倍 呈现逐渐变差的趋势 ，这是因为α 过大容易在 出原始信号 ，ＭＳＥ （ｍｅａｎ ｓｑｕａｒｅ ｅｒｒｏｒ ）值（见 初 始 迭 代 引 入 过 多 的 误 差 ，α 取 值 在２ ～ １０ 区 间效 式 （１１））为２０． ３５ ｄＢ． 果 都是较好的 外如果α 过小容易在算法初始 ．另 （２）稀 疏 度 实 验 估 计 迭 代 过 程中选取错误的支撑集 ，从而造成局部突 为 了 检 验ＦＢＭＳＰ 对信号稀疏度估计的能力 ， 变 ，所 以 本 文 中 的α 取 值 为 中 间 一 点 的 值α ＝ ８． 实 验 中 ，取稀疏度Ｋ ＝ ２０，３０，４０，测量信号长度 （４）重 建 性 能 比 较 测 量 矩 阵Ａ 采 用Ｍ × Ｎ 的高斯随机矩阵 ， Ｎ ＝ ２５６ ， 为 了比较ＦＢＭＳＰ 算法的性能 ，图４ 是在测量 Ｔｃ. . . . . ｌ. β. ｌ. β. . . . ｌ. ｌ. . ２. β. . . ｌ. . . . . . ｌ. ｌ －１. ｌ. ｌ －１. ２. . Ｔ. Ｔ. ｌ. ｍａｘ. . . ｌ. . . . . ｌ. . . . . . .
(5) 西 南 交 通 大 学 学 报 第５０ 卷 表１ 不同噪声情况下重构误差 次 数Ｍ ＝ １：３０：４ ０９６，其他条件不变的情况下 ， Ｔａｂ． １ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｅｒｒｏｒ ｉｎ ｄｉｆｆｅｒｅｎｔ ｎｏｉｓｅ ｃｏｎｄｉｔｉｏｎｓ 重构误差对比 ，在这里采 ＣｏＳａＭＰ、 ＭＳＰ、 ＦＢＭＳＰ 的 构 误 差 用ＭＳＥ 的 公 式 为 算 法 ｅ ＝ ０． ００１ 重 ｅ ＝ ０． ０１０ ｅ ＝ ０． １００ ｘ＾ － ｘ ＣｏＳａＭＰ ０． １２８ ８ ０． １２１ ８ ０． １２２ ５ （１１） Ｖ （ ） ＝ １０ｌｇ ( )． ｘ ＭＳＰ ０． ０４３ ７ ０． ０５３ ５ ０． ０４３ ４ 实 验 结 果 如 图４ 所 示 ． ＦＢＭＳＰ ０． ０２９ ４ ０． ０３４ ８ ０． ０３１ ０ ２６８. ２ ２. ＭＳＥ ｄＢ. ２ ２. . . . . . . （６）运 行 时 间 、时 间 复 杂 度 和ＭＳＥ 分 析 实 验 中 ，为 了保证信号的高精度重构 ，同时减 少 运 行 时 间 ，取 测 量 次 数Ｍ ＝ ２ ０００，假设信号稀疏 他 条 件 保 持 不变 表２ 可以看出 ， ．从 度 为Ｋ ＝ ２０，其 法 和ＭＳＰ 的 算 法 运 行 时 间 略 微 相 当 ，而 ＣｏＳａＭＰ 算 法的运行时间比ＣｏＳａＭＰ 降低了 ＦＢＭＳＰ 算 ３７． １％ ， 比ＭＳＰ降 低了４６． ４％ ． 主要原因在于在寻 找 最 优 支 撑 集 的时候 ，支撑集是逐渐扩大 ，而相比 支 撑 集 是 每 次 都 是 固 定 的 ，大 约 ＭＳＰ 和 ＣｏＳａＭＰ 的 支撑集 ，ＣｏＳａＭＰ、ＭＳＰ 和ＦＢＭＳＰ ３ 个算法分 ３Ｋ 个 别 对 应 的 语 句执行次数为ｋ 、ｋ 和ｋ （ｋ ＋ １ ）／ ２，这 就 是 为 什 么ＦＢＭＳＰ 运行时间更少 外从表２ 还 ．另 可以看出 ，ＦＢＭＳＰ 算法比ＭＳＰ 算法提高了 比ＣｏＳａＭＰ 算法提高了９． ２７９ ｄＢ，主要 ２． ２１７ ｄＢ ， 法和ＭＳＰ 算法每次迭代过程 原 因 在 于ＣｏＳａＭＰ 算 ，在刚开始迭代时 ，更容 中 的支撑集大约为３Ｋ 个 易 引 入 一 些 错 误 的 支 撑 集 ，这 些 错 误 的 支 撑 集 降 低 了 重 构 信 号 的精度 ，而ＦＢＭＳＰ 是以一个很小的稀 疏 度 开 始 迭 代 ，每次只增加一个稀疏度 ，从而保证 了 每 次 增 加 的 支撑集都是最优的 ，降低了错误率 ， ． 提 高 了 重 建 效 果
(6). . . . . . . . . . α. 图３ 不 同α 值 情 况 下ＦＢＭＳＰ 算 法 重 构ＭＳＥ Ｆｉｇ． ３ Ｒｅｃｏｎｓｔｒｕｃｔｅｄ ＭＳＥ ｕｓｉｎｇ ＦＢＭＳＰ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｖａｌｕｅｓ ｏｆ α. ２. .
(7)
(8)
(9) . . . . . . . . . 图 种 算 法 重 构 对 比. ４ ３ ＭＳＥ Ｆｉｇ． ４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｃｏｎｓｔｒｕｃｔｅｄ ＭＳＥ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ. 由 图４ 可以看出 ，在３ 种算法中 ，ＦＢＭＳＰ 算法 ，ＣｏＳａＭＰ 算法最差 ．在 效 果 最 理 想 ，ＭＳＰ 算法次之 高 比特情况下 ，ＦＢＭＳＰ 算法重构效果比ＭＳＰ 高 比 ３ ｄＢ ， ＣｏＳａＭＰ 高 １２ ｄＢ． （５）抗 噪 能 力 测 试 为 了 测 试ＦＢＭＳＰ 算法的抗噪能力 ，取稀疏度 他配置不变 ，压缩测量 Ｋ ＝ ２０ ，Ｍ ＝ ２ ０００ ，α ＝ ８ ，其 模 型 为ｙ ＝ Ａｘ ＋ ｅ，其中ｅ 为高斯噪声模型 ，在这里 ｅ取 均 值 为０，方差分别为０． ００１、０． ０１ 和０． １． 取 实 验 结果的平均值为误差结果 ，实验结果如 １０ 次 表１ 所 示 ． 由 表１ 可得 ，在相同噪声情况下 ，ＦＢＭＳＰ 重构 误 差 最 小 ，其 次ＭＳＰ，ＣｏＳａＭＰ 最 差 外ＦＢＭＳＰ 和 ．另 ＭＳＰ 都 表 现 出 良 好的抗噪能力 ，ＣｏＳａＭＰ 则抗噪能 ． 力 要 弱 一 些. ２. 表２ ３ 种算法的运行时间、ＭＳＥ 和时间复杂度对比 Ｔａｂ． ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎｎｉｎｇ ｔｉｍｅ， ＭＳＥ ａｎｄ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ. 算 法. ４ . 时 间／ ｓ. ＭＳＥ ／ ｄＢ. ＣｏＳａＭＰ. ２． １１６ ６. － １８． ６１１. ＭＳＰ. ２． ４８２ ０. － ２５． ６７３. ＦＢＭＳＰ. １． ３３１ ４. － ２７． ８９０. 结 论. 时 间 复 杂 度 Ｏ（ｋ ） Ｏ（ｋ ） Ｏ（ｋ ） ２ ２ ２. 本 文 在 深 入研究压缩感知理论基础和各种算 法 的基础上 ，针对１ 比特压缩感知的ＭＳＰ 算法的 缺 点 ，综 合 了ＣｏＳａＭＰ、ＦＰＣ 和ＦＢＰ 等算法 ，提出了 一 种 能 在 稀 疏 度未知的情况下进行盲运算信号重 构 的ＦＢＭＳＰ 算 法 ，该算法初始化一个向前的α 支 撑 集 和 一 个 小 的 向 后 的β 支 撑 集 ，在 满 足 条 件 的 每 次 迭 代 中 都 进 行β 自 加１，直到找到合适的稀疏度 .
(10) 第２ 期 闫 斌，等：一种基于盲运算的１ 比特压缩感知重建算法 ２６９ ｆｒｏｍ ｒａｎｄｏｍ ｐｒｏｊｅｃｔｉｏｎｓ ａｎｄ ｕｎｉｖｅｒｓａｌ ｅｎｃｏｄｉｎｇ 实 现 信 号 的 重 构 于 该 算 法 在 初 始 迭 代 时 极 小 地 ．由 ｓｔｒａｔｅｇｉｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ 引 入 误 差 ，使 得 重建的效果得到了提高 ，并且运行 Ｔｈｅｏｒｙ，２００６ ，５２ （１２ ）：５４０６５４２５． 时 间 也 减 少 了 ． ［１０］ ＭＡＬＬＡＴ Ｓ Ｇ，ＺＨＡＮＧ Ｚ． Ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔｓ ｗｉｔｈ ｔｉｍｅｆｒｅｑｕｅｎｃｙ ｄｉｃｔｉｏｎａｒｉｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ 参考文献：. Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ，１９９３ ，４１ （１２ ）：３３９７３４１５． ［］ ＩＥＥＥ ［１１］ ＴＲＯＰＰ Ｊ Ａ， ＧＩＬＢＥＲＴ Ａ Ｃ． Ｓｉｇｎａｌ ｒｅｃｏｖｅｒｙ ｆｒｏｍ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００６ ，５２ （４ ）： ｒａｎｄｏｍ ｍｅａｓｕｒｅｍｅｎｔｓ ｖｉａ ｏｒｔｈｏｇｏｎａｌ ｍａｔｃｈｉｎｇ １２８９１３０６． ｐｕｒｓｕｉｔ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， ［２］ ＣＡＮＤ?Ｓ Ｅ Ｊ． Ｃｏｍｐｒｅｓｓｉｖｅ ｓａｍｐｌｉｎｇ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ２００７ ，５３ （１２ ）：４６５５４６６６． ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｇｒｅｓｓ ｏｆ Ｍａｔｈｅｍａｔｉｃｉａｎｓ． ［１２］ ＮＥＥＤＥＬＬ Ｄ，ＶＥＲＳＨＹＮＩＮ Ｄ． Ｕｎｉｆｏｒｍ ｕｎｃｅｒｔａｉｎｔｙ Ｍａｄｒｉｄ：［ｓ． ｎ． ］，２００６ ：１４３３１４５２． ｐｒｉｎｃｉｐｌｅ ａｎｄ ｓｉｇｎａｌ ｒｅｃｏｖｅｒｙ ｖｉａ ｒｅｇｕｌａｒｉｚｅｄ ｏｒｔｈｏｇｏｎａｌ ［３］ ＱＡＩＳＡＲ Ｓ， ＢＩＬＡＬ Ｒ Ｍ， ＩＱＢＡＬ Ｗ， ｅｔ ａｌ． ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔ［Ｊ］． Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｃｏｍｐｒｅｓｓｉｖｅ ｓｅｎｓｉｎｇ： ｆｒｏｍ ｔｈｅｏｒｙ ｔｏ ａｐｐｌｉｃａｔｉｏｎｓ， ａ Ｍａｔｈｅｍａｔｉｃｓ，２００９ ，９ （３ ）：３１７３３４． ｓｕｒｖｅｙ［Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋ，２０１３ ，１５ ： ［１３］ ＤＯＮＯＨＯ Ｄ Ｌ，ＴＳＡＩＧ Ｙ，ＤＲＯＲＩ Ｉ，ｅｔ ａｌ． Ｓｐａｒｓｅ. ［１］ ＤＯＮＯＨＯ. Ｄ. ４４３４５６．. Ｌ．. Ｃｏｍｐｒｅｓｓｅｄ. ｓｅｎｓｉｎｇ Ｊ ．. ｓｏｌｕｔｉｏｎ ｏｆ ｕｎｄｅｒｄｅｔｅｒｍｉｎｅｄ ｌｉｎｅａｒ ｅｑｕａｔｉｏｎｓ ｂｙ ， ＦＥＲＮＡＮＤＥＺＧＲＡＮＤＡ Ｃ． Ｓｕｐｅｒ ｓｔａｇｅｗｉｓｅ ｏｒｔｈｏｇｏｎａｌ ｍａｔｃｈｉｎｇ ｐｕｒｓｕｉｔ［Ｒ］． Ｓｔａｎｆｏｒｄ： ｒｅｓｏｌｕｔｉｏｎ ｆｒｏｍ ｎｏｉｓｙ ｄａｔａ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｆｏｕｒｉｅｒ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｓｔａｔｉｓｔｉｃｓ， Ｓｔａｎｆｏｒｄ Ｕｎｉｖｅｒｓｉｔｙ， ＵＳＡ， Ａｎａｌｙｓｉｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１３ ，１９ （６ ）：１２２９１２５４． ２００６． ［５］ ＣＡＮＤ?Ｓ Ｅ Ｊ，ＦＥＲＮＡＮＤＥＺＧＲＡＮＤＡ Ｃ． Ｔｏｗａｒｄｓ ａ ［１４］ ＤＡＩ Ｗ， ＭＩＬＥＮＫＯＶＩＣ Ｏ． Ｓｕｂｓｐａｃｅ ｐｕｒｓｕｉｔ ｆｏｒ ｍａｔｈｅｍａｔｉｃａｌ ｔｈｅｏｒｙ ｏｆ ｓｕｐｅｒｒｅｓｏｌｕｔｉｏｎ［Ｊ］． ｃｏｍｐｒｅｓｓｉｖｅ ｓｅｎｓｉｎｇ ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｎ Ｐｕｒｅ ａｎｄ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ， Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００９ ，５５ （５ ）： ２０１４ ，６７ （６ ）：９０６９５６． ２２３０２２４９． ［６］ ＢＯＵＦＯＵＮＯＳ Ｐ Ｔ，ＢＡＲＡＮＩＵＫ Ｒ Ｇ． １ｂｉｔ ｃｏｍｐｒｅｓｓｉｖｅ ［１５］ ＮＥＥＤＥＬＬ Ｄ，ＴＲＯＰＰ Ｊ Ａ． ＣｏＳａＭＰ：ｉｔｅｒａｔｉｖｅ ｓｉｇｎａｌ ｓｅｎｓｉｎｇ［Ｃ］∥ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４２ｎｄ Ａｎｎｕａｌ ｒｅｃｏｖｅｒｙ ｆｏｒｍ ｉｎｃｏｍｐｌｅｔｅ ａｎｄ ｉｎａｃｃｕｒａｔｅ ｓａｍｐｌｅｓ［Ｊ］． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ ａｎｄ Ｓｙｓｔｅｍｓ． Ａｐｐｌｉｅｄ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｈａｒｍｏｎｉｃ Ａｎａｌｙｓｉｓ，２００８ ， Ｗａｓｈｉｎｇｔｏｎ Ｄ Ｃ：ＩＥＥＥ，２００８ ：１６２１． （３）：３０１３２１． ［７］ ＢＯＵＦＯＵＮＯＳ Ｐ． Ｇｒｅｅｄｙ ｓｐａｒｓｅ ｓｉｇｎａｌ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ［１６］ ２６方 ． 贪 红 ，杨 海 蓉 婪 算 法 与 压 缩 感 知 理 论 ［Ｊ］． 自动 ｆｒｏｍ ｓｉｇｎ ｍｅａｓｕｒｅｍｅｎｔｓ［Ｃ］∥ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４３ｒｄ 化 学 报 ，２０１１，３７（１２）：１４１３１４２１． Ａｓｉｌｏｍａｒ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｉｇｎａｌｓ， Ｓｙｓｔｅｍｓ ａｎｄ ＦＡＮＧ Ｈｏｎｇ，ＹＡＮＧ Ｈａｉｒｏｎｇ． Ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍｓ ａｎｄ Ｃｏｍｐｕｔｅｒｓ． Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ，２００９ ：１３０５１３０９． ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ［Ｊ］． Ａｃａｔ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ［８］ ＫＡＲＡＨＡＮＯＧＬＵ Ｎ Ｂ， ＥＲＤＯＧＡＮ Ｈ． Ｃｏｍｐｒｅｓｓｅｄ ２０１１ ，３７ （１２ ）：１４１３１４２１． ｓｅｎｓｉｎｇ ｓｉｇｎａｌ ｒｅｃｏｖｅｒｙ ｖｉａ ｆｏｒｗａｒｄｂａｃｋｗａｒｄ ｐｕｒｓｕｉｔ［Ｊ］． Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ，２０１３ ，２３ （５ ）： １５３９１５４８． （中文编辑：唐 晴 英文编辑：周 尧） ［９］ ＣＡＮＤ?Ｓ Ｅ Ｊ，ＴＡＯ Ｔ． Ｎｅａｒ ｏｐｔｉｍａｌ ｓｉｇｎａｌ ｒｅｃｏｖｅｒｙ. ［４］ ＣＡＮＤ?Ｓ. Ｅ Ｊ.
(11)
関連したドキュメント
The denoising results for pixels near singularities are obtained by nonlocal means in spatial domain to preserve singularities while the denoising results for pixels in smooth
Proof of Theorem 2: The Push-and-Pull algorithm consists of the Initialization phase to generate an initial tableau that contains some basic variables, followed by the Push and
Proof of Theorem 2: The Push-and-Pull algorithm consists of the Initialization phase to generate an initial tableau that contains some basic variables, followed by the Push and
Comparing the Gauss-Jordan-based algorithm and the algorithm presented in [5], which is based on the LU factorization of the Laplacian matrix, we note that despite the fact that
The (GA) performed just the random search ((GA)’s initial population giving the best solution), but even in this case it generated satisfactory results (the gap between the
4 The maintenance cost which is not considered by traditional model concluding the unscheduled maintenance cost and the wear cost during the operation can be modeled as a function
These authors make the following objection to the classical Cahn-Hilliard theory: it does not seem to arise from an exact macroscopic description of microscopic models of
These authors make the following objection to the classical Cahn-Hilliard theory: it does not seem to arise from an exact macroscopic description of microscopic models of
