基于压缩感知的凸优化算法研究.pdf

基于压缩感知的凸优化算法研究基于压缩感知的凸优化算法研究 research on convex optimization algorithm based on compressed sensing 作作 者者 姓姓 名名 吴文婷 学学 位位 类类 型型 学 历 硕 士 学学 科 专科 专 业业 计算机应用技术 研研 究究 方方 向向 嵌入式系统 导导 师师 及及 职职 称称 史久根 副研究员 2013 年年 4 月月 合合 肥肥 工工 业业 大大 学学 本论文经答辩委员会全体委员审查 确认符合合肥工业 大学硕士学位论文质量要求 答辩委员会签名 工作单位 职称 答辩委员会签名 工作单位 职称 主 席 王焕宝 安徽建筑工业学院 教授 委 员 汪荣贵 合肥工业大学 教授 唐 昊 合肥工业大学 教授 薛美盛 中国科学技术大学 副教授 张本宏 合肥工业大学 副教授 导 师 史久根 合肥工业大学 副研究员 独独 创创 性性 声声 明明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知 除了文中特别加以标志和致谢的地方外 论文中不包含其他人已经发表或撰 写过的研究成果 也不包含为获得 合肥工业大学 或其他教育机构的学位或证书而使 用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意 学位论文作者签字 吴文婷 签字日期 2013 年 4 月 21 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解 合肥工业大学 有关保留 使用学位论文的规定 有权 保留并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查阅或借阅 本人 授权 合肥工业大学 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 吴文婷 导师签名 史久根 签字日期 2013 年 4 月 21 日 签字日期 2013 年 4 月 21 日 学位论文作者毕业后去向 工作单位 电话 通讯地址 邮编 i 基于压缩感知的凸优化算法研究基于压缩感知的凸优化算法研究 摘摘 要要 随着信息技术的迅猛发展 海量数据日益增长 传统的信号处理模式已经 越来越不能够适应这种局面 信号处理能力也受到了极大的挑战 压缩感知理 论应运而生 压缩感知理论能够从繁冗的信号中提取简洁的信息 从而减少信 号处理的数据量 压缩感知理论包含了信号的稀疏分解 观测矩阵的设计与选 择以及信号的恢复 利用较少的观测值精准地恢复信号是压缩感知恢复过程的 关键 本文在压缩感知理论框架下研究凸优化恢复算法 首先 本论文详细介绍了压缩感知的理论基础 描述了压缩感知框架下的 压缩过程和恢复过程 详细介绍了稀疏分解和观测矩阵的有限等距特性 而且 分析了恢复过程中凸松弛法与贪婪算法各自的特点和区别 其次 论文分析比较了最小 0 l法 最小 1 l法以及最小 2 l法的区别 深入研究 了凸优化算法中的稀疏梯度投影算法和内点法 阐述各算法的基本内容 从理 论上分析总结各算法的优缺点 通过仿真实验比较算法的性能 发现算法恢复 性能受到信号规模 信号稀疏度以及噪声大小的影响 最后 针对上述算法不能稳定收敛的问题 本文提出了结合拟牛顿的梯度 投影算法和适用于多数凸优化算法的停止准则 该算法充分利用了拟牛顿的校 正机制和线性收敛特性 近似的目标矩阵有效降低了恢复算法的计算复杂度 而校正机制则弥补了方向误差 在可行梯度上寻找最优解 并且采用的停止准 则能够很好的平衡算法精度和运行时间 仿真实验结果表明 基于拟牛顿的梯 度投影算法能够以极小的误差恢复原始信号 并且获得更加稳定且更快的算法 收敛速度 提高算法恢复性能和鲁棒性 关键词关键词 压缩感知 恢复算法 凸优化 拟牛顿 ii research on convex optimization algorithm based on compressed sensing abstract with the rapid development of information technology the amounts of processing data increase quickly the traditional signal processing mode has not been able to adapt to this situation the signal processing ability experience great challenges compressed sensing theory is proposed this theory can reduce the amount of signal processing data effectively by extract the concision information from the redundant raw signals there are several research fields in the compressed sensing area such as signal sparse representation selection and design of observation matrix and signal reconstruction the key point of the compressed sensing is to make signal reconstruction accurately with small amount of observed values in this dissertation we make a research on several convex optimization algorithms with compressed sensing theory to process the signal reconstruction in the first place we make a detailed introduction on the basic theory about compressed sensing the compression process and reconstruction process is described particularly it is essential for the basic theory description to describe the sparse decomposition process and the characteristic of observation matrix in addition we analyze the specialty and difference between the convex relaxation method and greedy algorithm in the next place we make an analysis on the difference between the 1 l minimization in signal reconstruction and the 0 l and 2 l minimization in traditional way in order to make farther research we introduce the basic theory of the sparse gradient projection algorithm and interior point method then we make a conclusion about the characteristics of these methods theoretically in the next the simulation experiments are made to test the performance of these methods the experimental results show that their convergence rates relay on the algorithm scale the sparsity level of signal and the noise level the last but not the least in allusion to the phenomenon which the strategy stated above cannot converge stably we proposed the gradient projection with quasi newton method for sparse reconstruction and the better stopping criterion for convex optimization algorithms it makes full use of the correction mechanism and superlinear convergence of quasi newton method the approximation of the objective function decreases the computational complexity the correction iii mechanism makes up the error on search direction so as to find the optimal solution in the possible gradient directions the stopping criterion can makes a good balance between the accuracy of algorithm and the cpu time the experimental results show that gradient projection with quasi newton method cannot only deal with the compressed sensing signal reconstruction with low reconstruction error but also can significantly decrease cpu time and improve the stability and the convergence of the algorithm keywords compressed sensing signal reconstruction convex optimization quasi newton iv 致致 谢谢 时光荏苒 岁月如梭 硕士研究生的学习生涯即将结束 本论文能够顺利 完成 与我得到来自老师和同学的无私的关心和帮助密不可分 值此论文完成 之时 特此向所有给予我关心 帮助和支持的人表示感谢 特别要感谢的是我 的导师史久根教授 论文评审老师薛美盛教授以及汪荣贵教授 我衷心的感谢导师史久根老师对本人研究生三年来的关心和教导 自从进 入研究生学习阶段 导师便为我提供了良好的实验室环境以及诸多科研机会 研一刚入校便让我加入到科研项目组中 这为我今后的学习打下了扎实的基础 锻炼了我的学习能力和科研创新能力 让我受益匪浅 本论文是在史老师的悉 心指导下完成的 整篇论文的研究阶段都离不开老师的教导 史老师严谨的治 学态度 孜孜不倦又平易近人的指导方式以及扎实的学术知识 都深深影响着 我 在研究过程中史老师给出的许多意见都使我非常受用 在此我再一次向史 老师表示我真诚的感谢 此外 我还需要感谢分布式控制研究所的谢新胜老师 同级同学刘胜以及 已经毕业的 09 级的师兄师姐 在我的研究生学习生涯中 他们给予我很多的关 心和帮助 填补了我许多科研知识方面的空白 在我的研究遇到困难的时候都 给予了我非常受用的指导意见 感谢薛美盛老师和汪荣贵老师对我的文章提出了宝贵的审核意见 论文的 完成离不开两位老师的指导和帮助 同时我还特别感谢我的家人 朋友以及与我朝夕相处的实验室同学和室友 家人朋友对我无私的爱和深切的期望是我努力学习的动力和强大的精神支柱 实验室同学为我营造了严谨又愉快的科研氛围 提高了学习效率 也正是有了 他们的支持和帮助 才使得能够顺利完成科研任务 最后 我要深深的感谢合 肥工业大学对我的培养和教育 感谢这个大环境给予我成长和发挥的空间 我 会继续努力 再接再厉 感谢母校 感谢所有关心 帮助和支持过我的人 作者 吴文婷 日期 2013 年 4 月 21 日 v 目目 录录 第一章第一章 绪论绪论 1 1 1 课题背景以及研究意义 1 1 2 国内外研究现状和发展趋势 2 1 2 1 压缩感知理论的国内外理论性研究现状 2 1 2 2 压缩感知理论的国内外应用性研究现状 5 1 3 本文的主要研究内容和结构安排 6 第二章第二章 压缩感知的理论框架压缩感知的理论框架 8 2 1 引言 8 2 2 压缩感知的基本原理 8 2 3 压缩过程 10 2 3 1 信号的稀疏表示 10 2 3 2 观测矩阵的选择 13 2 4 恢复过程 15 2 4 1 贪婪算法 16 2 4 2 凸松弛法 17 2 4 3 性能对比 18 2 5 本章小结 20 第三章第三章 凸松弛法在压缩感知二维图像信号上的应用凸松弛法在压缩感知二维图像信号上的应用 22 3 1 引言 22 3 2 凸优化 22 3 3 稀疏梯度投影算法 23 3 3 1 gpsr 算法的理论基础 24 3 3 2 gpsr basic 算法 24 3 3 3 gpsr 算法的收敛性分析 26 3 4 内点法 27 3 5 算法性能比较 29 3 6 本章小结 33 第四章第四章 基于拟牛顿的梯度投影算法基于拟牛顿的梯度投影算法 35 4 1 引言 35 4 2 基本思想和算法 35 4 2 1 拟牛顿法 35 4 2 2 基于拟牛顿的梯度投影算法 36 4 3 停止准则 38 4 4 仿真实验 39 vi 4 5 本章小结 42 第五章第五章 总结与展望总结与展望 43 5 1 研究内容总结 43 5 2 研究的不足之处 43 5 3 未来的工作 44 参考文献参考文献 45 攻读硕士学位期间发表的论文和参与的研究工作攻读硕士学位期间发表的论文和参与的研究工作 49 特别声明特别声明 50 vii 插图清单插图清单 图 1 1 单像素 cs 相机 5 图 2 1 传统采样压缩过程 8 图 2 2 压缩感知理论下的采样过程 9 图 2 3 二维信号的离散小波变换 12 图 2 4 观测过程 14 图 2 5 l1范数最小化的稀疏平面表示 17 图 2 6 bp 算法和 omp 算法恢复效果对比 19 图 2 7 bp 算法和 omp 算法重构时间直方图 20 图 3 1 l0 ball l1 ball l2 ball 与约束空间的交点 23 图 3 2 mondrian 图像恢复效果 30 图 3 3 boatcolor 图像恢复效果 31 图 3 4 不同信噪比下恢复时间对比 32 图 4 1 牛顿法求解流程图 35 图 4 2 barbara 图像恢复效果对比 39 图 4 3 dollar 图像恢复效果对比 40 图 4 4 非零个数与运行时间对比 41 viii 表格清单表格清单 表 2 1 bp 算法和 omp 算法重构时间对比 19 表 2 2 贪婪算法和凸松弛法总结对比 20 表 3 1 mondrian 图像恢复时间和非零个数结果 33 表 3 2 boatcolor 图像恢复时间和非零个数结果 33 表 4 1 恢复时间与误差率分析 40 表 4 2 不同停止准则的时间和匹配度对比 42 1 第一章第一章 绪论绪论 1 1 课题背景以及研究意义课题背景以及研究意义 在当代 信息技术科学对社会进步有着越来越大的影响力 从科学教育到 人们的日常生活 从国防安全到医疗科技 信息科技的每一点创新进步都给我 们的社会带来巨大的影响 随着人们生活水平逐步提高 传媒信息的逐渐公开 透明化以及智能手机的不断普及 人们对信息的需求量迅猛增长 从而促生了 物联网 云计算等一系列高新科技产品 这些新生产物给我们的生活带来了极 大的方便 但是与此同时 极其繁冗的海量数据 从采集到存储 再到应用 如何能够高效的利用这些海量数据 是当前科技面临的一个巨大的挑战 现实 世界是模拟化的 而信息处理工具是数字化的 因此将采集到的模拟信号转换 成为数字信号 再通过加工才能得到我们所需的信息 传统的信号数据采集过 程要求我们遵照临界频率或者是奈奎斯特 nyquist 采样定理 即采样频率只 有在不小于信号带宽 2 倍的前提下 才能不失真地从离散信号恢复得到原始信 号 在过去的几十年里 这一理论运用在绝大多数的信号和图像的采样 存储 传输和处理中 并且具有较强优势 例如宽带通信和医学成像 但是随着信号 量的日益增多 nyquist 采样理论的缺点逐渐显露 首先 nyquist 采样所要求 的硬件成本昂贵 而且逐渐增加的信号带宽需要越来越高的采样频率和处理速 度 其次 为降低存储和传输成本 在存储传输过程中需要将采样信号进行压 缩 压缩过程势必会有大量有效信息丢失 从而导致恢复效果的失真 并且压 缩算法的计算复杂度也是一个不容忽视的问题 信息爆炸所产生的这一系列现 实问题导致 nyquist 采样理论越来越不能很好适应当前的信息处理 因此一种 全新的思维理念应运而生 2006 年 美国科学院院士 d l donoho 和 ridgelet curvelet 的创始人 e cand s 以及著名的华裔科学家陶哲轩提出了基于逼近论和信号稀疏表示的压 缩感知理论 1 compressed sensing cs 压缩感知理论的创新思维在于它将 信号的采样过程与压缩过程同步进行 即针对具有稀疏性或者可压缩性的信号 进行有限次观测 得到包含有原始信号全部信息的观测值 然后通过求解一系 列优化问题 从观测值中恢复原始信号 这种新的采样压缩模式 有效的降低 了信号的采样频率和数据传输成本 因此该理论一经提出 迅速得到信息领域 的广泛关注 诸如斯坦福大学和一批世界著名学府纷纷成立专门的课题研究组 并在理论与应用方面都获得了相应的成果 压缩感知理论也因为低采样频率和 低硬件成本 使其在信号处理 图像处理 医疗成像 模式识别 无线电通信 以及雷达成像上都有广泛的应用 是 2007 年美国十大科技进展 随着生活水平的日益提高 智能手机 数码相机的普及使得人们对高清图 像 高清视频的存储和处理有了更高的要求 同时 在医疗方面 为了提高医 2 生对病症判断的准确性 例如 ct 和核磁共振等检查对病理成像的精准度也越 来越高 因此 压缩感知理论在图像处理的应用上有着较大的发展空间 低成 本低速率高精度的特点使得国内外研究学者在基于压缩感知的图像应用上投入 了大量精力并取得了一定的研究成果 本文是在与中科院空间科学与应用研究中心的合作课题背景下研究基于压 缩感知理论的图像恢复算法 分析压缩感知理论在图像信号重构中需要解决的 问题 对比凸松弛法与其他方法的优缺点 同时具体分析凸优化法中内点法和 稀疏梯度投影法的恢复性能 并提出一种基于拟牛顿法的图像恢复算法 这种 算法充分利用了拟牛顿法的近似特征和线性收敛性 并在此基础上总结提出了 适用于多种凸松弛法的新的算法停止准则 通过仿真实验验证了该算法的高效 性 具有一定的理论研究意义和实用价值 1 2 国内外研究现状和发展趋势国内外研究现状和发展趋势 压缩感知理论自 2006 年正式提出以来 受到学术界广泛关注 国内外的诸 多学者纷纷将这一新的理论思想应用到自己的研究领域 提出了许多有价值的 理论和实际应用方案 本节将从理论和应用两方面分析目前国内外的研究成果 1 2 1 压缩感知理论的国内外理论性研究现状 2006 年 2 月 cand s donoho 和 tao 在文献 2 中提出了根据不完备频率恢 复原始信号的一系列相关问题 针对一个n维离散信号 随机选择m个频率值 在频率具体位置和振幅大小均未知的情况下 证明了求解一个凸优化问题 能 够以至少 m 1 n o 的概率恢复得到原始信号 这一证明为压缩感知理论奠定了 理论基础 随后 在 2006 年 12 月 cand s 和 tao 在文献 3 中阐述了在随机观 测条件下 观测点的个数与原始信号点的个数之间的关系 在 2006 年 4 月的 ieee 信息理论会议上 cand s donoho 以及 tao 发表了文献 4 正式提出了 压缩感知理论 cand s 等人认为在压缩感知理论框架下 信号n在某正交基下 或者某紧致结构下 变换后得到的系数属于 01 p lp 球内 并且信号的重构 允许维数n的最关键系数保持 2 l的误差 尽管这种观测是非自适应的 但是观 测值包含了能够恢复原始信号的全部有效信息 在压缩感知理论提出之后 如 何将信号稀疏化表示 如何提高信号的非线性函数逼近能力是压缩感知理论研 究面临的首要问题 目前解决该问题的主要方法有两种 一种是找到合适的正 交基 将原始信号变为最稀疏的信号表示 另一种则是在冗余字典下将信号进 行稀疏分解 2008 年 5 月 rauhut schnass 等人在文献 5 中通过理论和实验证明通过求 解一个小数量的随机测量值即可得到基础冗余字典进而得到稀疏信号 同年 albert wolfgang 和 ronald 在发表的文献 6 中提出了基于压缩感知的 k 项近 3 似 文章通过实例构建了基于压缩感知的 k 项最优近似法 随着研究的不断推 进 emmanuel 等人又在 2011 年提出了基于压缩感知的连贯的冗余字典 在文 献 7 中他提出有关恢复信号的欠采样信号在非正交基或者非连贯字典的真正 的冗余字典下 通过求解分析 1 l范数的优化问题可以得到准确的恢复信号 同 时在恢复过程中引入了具备有限等距性质 restricted isometry property rip 的观测矩阵 并且该完备连贯的观测矩阵对任何不连贯字典都没有限制 在关注信号稀疏表示的同时 观测矩阵的设计和选择也是关于压缩感知理 论的另一个研究热点 cand s 在文献 4 中就观测矩阵在压缩感知理论中的应 用 给出了观测矩阵应当具备的特征 观测矩阵列向量组成的子矩阵的最小奇 异值应当大于某个常数 即观测矩阵的列向量相互之间应当满足线性独立特性 观测矩阵的列向量必须具备类似噪声的随机独立特性 通过由观测矩阵组成的 压缩感知恢复模型 可以获得稀疏度的解是 1 l范数最小的向量 不过 虽然这 些具备 rip 特性的观测矩阵得到的观测值可以保证以很高的概率重构原始信 号 但并不能确保无失真地恢复出原始信号 因此 emmanuel 和 cand s 在 2011 年 11 月提出一种新的概念 8 即在压缩感知框架内 只要原始信号服从随机概 率分布 且满足简单不连贯的同向性 即可从含有少量噪声的稀疏信号中如实 恢复原始信号 该理念对信号是否满足随机采样以及观测矩阵是否满足 rip 特 性没有要求 因此这种新的理念是一种基于压缩感知理论的新的发展方向 在信号重构方面 由于压缩感知的恢复算法主要是求解稀疏解的线性规划 linear programming lp 问题 因此一些针对稀疏信号的稀疏近似算法同 样适用于压缩感知的恢复 b logan 9 在 1965 就将最小 1 l范数与稀疏信号的恢复 联系起来 从理论的角度分析了最小 1 l范数与稀疏信号的恢复之间的关系 得 到结论 通过求解最小 1 l范数问题即可精确恢复由欠采样获得的稀疏信号 随 后 在九十年代初期 rudin osher 等人提出了专门用于图像恢复且与最小 1 l范 数相关的最小全变分算法 total variation 10 这类算法至今依然适用于压缩感 知的信号恢复 在研究了针对稀疏信号的恢复问题后 总结得到目前适用于压缩感知信号 恢复的方法主要有组合算法 贪婪算法以及凸松弛法 gilbert 等人在 2006 年 提出了链式追踪 11 chaining pursuit cp 算法 该方法在信号稀疏度较大时 通过分组测试进行采样 该采样过程能够发挥极好的作用 迅速恢复原始信号 在研究链式追踪的组合算法的同时 gilbert 和 tropp 在小波变换奠基人 mallat 12 的基于贪婪算法思想的匹配追踪算法 matching pursuit mp 的基础上提出了 具有更快收敛性的正交匹配追踪算法 13 orthogonal matching pursuit omp 来解决信号重构问题 omp 算法大大提高了计算速度 同年 4 月 donoho 提 出了分段正交匹配追踪算法 14 stagewise omp stomp 该方法对 omp 算 法做了相应的简化 降低了计算复杂度从而提高了计算速度 使得该算法更加 4 适合求解大规模问题 在研究如何降低计算复杂度的同时 maleki 15 和 donoho 在 2010 年 3 月 提出了一种基于最优化相变的最优整合迭代重构算法 该算法 无需选择迭代阈值 且不限制软阈值和硬阈值之间的联系 也不需要知道信号 的稀疏程度 只要实现非零个数的最大化即可通过追踪子空间获得最优结果 这类算法具有非常好的鲁棒性 与此同时 needell 等人在 2009 年正式提出了 正规化正交匹配追踪算法 16 regularized orthogonal matching pursuit romp 该方法依照 omp 算法的思想对原子进行一次筛选之后 引入正规化过程对原子 实施二次筛选 以确保选入原子的能量大于未选入原子的能量 从而对支撑集 进行优化以提高重构速度 donoho 和 sauders 提出的基追踪法 17 basis pursuit bp 是凸松弛法的一种 该算法将表示系统的范数定义为信号的稀疏特性 利 用最小 1 l范数将稀疏信号的重构问题定义为有约束的极值问题 再将极值问题 转化为线性规划问题进行求解 这类方法利用最少的观测点来精确重构原始信 号 除此之外 由 figueirdo nowak 和 wright 提出的稀疏梯度投影算法 18 gradient projection for sparse reconstruction gpsr 也是一种典型的凸松弛 法 gpsr 算法引入隐变量 将目标函数转化为具有边界约束的二次方程规划 问题 bound constrained quadratic programming bcqp 从而解决了求解稀 疏信号重构时最小 1 l范数不可微的问题 确定最优搜索方向恢复原始信号 相比较国外学者在压缩感知理论的压缩和恢复过程方面的研究的多样性 国内学者针对压缩感知理论中压缩过程的理论性研究较少 安徽大学的张亮在 文献 19 中利用分块小波变换的灵活性 结合压缩感知理论 提出了基于小波 变换的帧间可压缩方法 该方法以更低的信噪比取得更好的视觉效果 管蓉 20 在她的硕士论文中提出了一种基于二元树的稀疏分解算法 将已经构造完成的 原子库进行划分 逐层划分为树状结构 利用每层的树状结构进行分解 这种 分解方式是有目的地引导分解方向 从而大大降低计算复杂度 提高分解速度 并且该方法能够使用与任何超完备字典 北京交通大学的李小波 21 在前人的基 础上深入研究了利用多项式来确定观测矩阵的方法 能够减少误差 快速的确 定观测矩阵是否满足 rip 性质 在压缩感知理论的恢复过程研究中 哈尔滨工 业大学的付宁等人 22 针对块稀疏信号的特点 提出了一种基于子空间的块稀疏 信号压缩感知恢复算法 该算法利用回溯思想和最小均方差准则 通过迭代计 算残差直至残差为零 这种算法既减少了迭代次数又提高了重构效率 王天荆 等人 23 基于基追踪算法 提出了一种基于压缩感知理论的恢复过程中的极大熵 的算法 该算法有效避免了 1 l范数最优化问题的非光滑性 构造了极大熵函数 的最优序列 依照该序列逼近全局最优解 练秋生和肖莹 24 在 2010 年 7 月在 压缩感知的理论基础上 利用小波树结构的先验知识 结合小波系数合理树结 构的思想 提出一种改进的硬阈值迭代算法 该算法能够获得更好的重构效果 5 1 2 2 压缩感知理论的国内外应用性研究现状 压缩感知理论的主要思想是利用更低的采样频率和存储空间获得相对令人 满意的恢复效果 这种特性使得压缩感知理论一经提出就受到了很多国内外专 家的关注 诸多学者纷纷成立研究小组 将压缩感知理论运用到实际应用中 美国 rice 大学已经研制出了一款 单像素相机 25 具体工作原理如下图 1 1 所示 图 1 1 单像素 cs 相机 这种单像素相机架构是利用数字微镜阵列 digital micromirror array 完 成图像在伪随机序列二值模型上的线性投影的光学计算 利用单一信号光子检 测器采样得到比原本图像像素少很多的点 恢复得到一幅图像 并且相比较传 统的成像器件 如 ccd 或 cmos 这种相机具有对图像波长的自适应能力 具有良好成像优势 除此之外 因为压缩感知理论具有能够利用少量关键像素 点恢复整体图像的特点 因此 wright 等人 26 应用于人脸识别当中 作者研究人 脸面部表达 光照因素以及遮挡等问题时 利用压缩感知理论将这些问题看做 多个线性回归模型 有效地提取面部特征 并提高了遮挡情况下算法的鲁棒性 压缩感知理论因为在图像恢复方面的突出优势很快被应用到医学影像上 麻省 理工大学研制了一款基于压缩感知的核磁共振 magnetic resonance imaging mri 成像 fr 脉冲仪器 该仪器很好的利用了压缩感知理论能够根据观测值 重构原始图像的特点 有效的克服了医学影像方面无法直接获取原始信号的缺 点 haupt 和 nowak 在 2006 年将压缩感知理论应用到多信号环境中 27 研究 多信号之间的关联性 随后 baron 等人在他们的基础上扩展了单信号的内在联 系 提出了分布式压缩感知理论 distributed compressed sensing dcs 28 分布式压缩感知理论是研究如何利用信号内部的相关性和信号之间的相互关系 对多信号进行联合重构 从而达到节约观测数目的目的 这类思想很快被应用 到无线传感器网络的研究中 目前该课题仍是一个研究热点 压缩感知理论在 6 信号方面的研究还延伸到生物传感 29 信道编码 30 光谱分析 31 无线电 32 以及雷达 33 等方面 在国外学者的研究基础上 国内的诸多大学以及研究机构也逐渐关注这项 新技术 国家自然科学基金在 2008 年就开始支持压缩感知理论的基础性研究 南京邮电大学在 压缩感知的多媒体编码理论与方法研究 中有着丰富的成果 孙林慧 杨震等人 34 提出了应用于语音压缩与重构的自适应多尺度压缩感知 该研究针对人的口音进行采样和识别 利用 sym 小波分解得到的矩阵 提出语 音信号的多尺度压缩感知 实验结果证明该方法在语音方面的应用有较好的效 果 随后 他们还提出了基于压缩感知的低速率语音编码新方案 35 方案中小 波变换的高频系数的压缩感知重构采用 1 l范数优化方案和码本预测方案 1l范数 的优化方案在新型预测编码上的优势以及码本预测方案对稀疏系数的估计的准 确性 使得重构的语音质量有进一步的提升 压缩感知理论作为一种信号处理的新技术 也被应用到国防方面 如无线 电通信以及雷达观测 中科院空间科学与应用研究中心的谢晓春 36 通过对雷达 回波信号的分析 构建了一种匹配滤波体质和去斜体质的雷达回波信号稀疏表 达模型 并且在压缩感知雷达成像中引入 a d 转换器 取得了更好的成像效果 压缩感知在雷达方面的应用还表现在将传统的雷达二维成像技术与 inisar 三 维成像技术相结合 在压缩感知理论的基础上 形成新的雷达成像算法 中国 科学院电子研究所的余惠敏和方广有 37 还将压缩感知理论运用到地探雷达的 三维成像中 利用目标空间的稀疏性 在单道数据中应用压缩感知理论减少采 集的数据量 从噪声和观测矩阵的角度分析了算法的稳定性能和成像效果 1 3 本文的主要研究内容和结构安排本文的主要研究内容和结构安排 本文主要针对二维图像信号 分析研究了压缩感知理论和该理论下的恢复 算法 对比并总结常见恢复算法的优缺点以及各自的适用范围 总结出凸松弛 法的主要优势 针对凸松弛法 做进一步的研究 以稀疏梯度投影算法和内点 法作为主要的研究点 深入分析压缩感知理论下的凸松弛恢复算法 并根据凸 松弛法的优点 利用拟牛顿法的超线性收敛性以及下降特征 提出了基于拟牛 顿的梯度投影恢复算法 并且在此基础上提出了能够较好平衡恢复效果和运行 时间的停止准则 结合仿真实验分析算法性能 本论文的具体章节安排如下 第一章是绪论部分 介绍了压缩感知理论提出的背景知识 以及目前国内 外针对压缩感知理论在理论和应用方面的主要研究成果 分析了压缩感知理论 在图像处理方面的发展前景以及研究价值 第二章是压缩感知理论的框架研究 主要阐述了压缩感知理论的基本原理 和整体过程所包含的基本内容 从压缩过程和恢复过程两方面分析研究了压缩 感知理论 7 第三章针对凸松弛算法进行具体研究 根据第二章的研究内容总结出凸松 弛算法相比较贪婪算法和其他算法具有更广泛的适用性 因此本章节重点分析 了稀疏梯度投影算法和内点法的特点 从理论和实验上分析算法的重构性能 算法收敛速度以及鲁棒性等相关性能 总结出各自的优缺点 第四章提出了基于拟牛顿法的梯度投影算法 通过第三章的分析 针对 gpsr basic 算法重构效果好但收敛速度慢的问题 改进最优化问题 结合拟牛 顿法 提出一种具有较高恢复率又能稳定收敛的恢复算法 除此之外 还提出 了一种有效的算法停止准则 能够在凸松弛法中较好地平衡恢复效率和运行时 间 从理论和实验两个角度分析对比了该算法的良好性能 第五章是总结与展望 对本论文的工作进行总结 提出目前该研究课题还 存在的问题 展望今后可以继续深入研究的问题 8 第二章第二章 压缩感知的理论框架压缩感知的理论框架 2 1 引言引言 本章将对压缩感知理论的基本概念和基本原理做详细介绍 随后就压缩感 知理论的压缩过程和恢复过程做深入分析 解剖信号稀疏分解的具体方法以及 如何选择合适的观测矩阵 分析总结了目前压缩感知领域主要的三种恢复算法 针对图像压缩感知 分析对比了实用性较广的贪婪算法和凸松弛法 并针对图 像信号的恢复 对比了算法的性能 总结各自的优缺点 2 2 压缩感知的基本原理压缩感知的基本原理 信息处理工具的日益数字化使得信号采样成为从模拟世界通往信息世界的 必经之路 长期以来 奈奎斯特采样定理是模拟信号采样的理论基础 该理论 的基本思想是要求采样频率至少达到信号带宽的两倍才可以精确的恢复原始信 号 但是 随着科技的不断进步 诸如医疗成像 雷达成像 传感器网络等实 际应用所携带的信号量越来越大 信号带宽已经远远超出采样频率的两倍 若 依旧按照原来的采样频率 则信号处理速度很难跟上需求速度 很难适应当前 的发展需求 若提高采样频率来迎合不断增加的信号带宽 则采样所增加的硬 件成本无疑是难以承受的 因此解决该问题的常见方法是将信号进行压缩 图 2 1 是传统的采样压缩过程 图 2 1 传统采样压缩过程 从图中我们可以看到 可压缩信号经过采样之后需要通过变换压缩 这个 过程需要对大量的完整信号进行筛选 留下有效信号 丢弃小系数数据 这种 传统采样压缩过程丢弃大量信号不仅造成了采样成本的浪费 同时也增加了压 缩过程的计算复杂度 对整体的采样压缩效率有不小的影响 压缩感知理论是一种全新的思维模式 它突破了传统采样压缩思想的束缚 以远低于 nyqusit 采样定理的采样速率采集信号 并且依然能够精确或者近似 精确地恢复出原始信号 压缩感知理论充分利用了信号的稀疏特性 将信号的 采集和压缩整合成一个过程 实现边采样边压缩 利用观测矩阵将高维信号投 影到低维空间中 保留了绝大多数有效的原始信号 最后通过求解低维空间内 观测值的优化问题而重构出原始信号 压缩感知理论实现了信号采样与信号压 可压缩信号 重构信号 高速采样 变换 压缩 存储 传输 9 缩同步进行 图 2 2 是压缩感知理论下信号采样压缩过程 图 2 2 压缩感知理论下的采样压缩过程 对比图 2 1 和 2 2 我们可以看出 压缩感知理论将传统的采样 变换 压 缩过程集中整合成稀疏变换和低维投影过程 在保证恢复质量的同时有效降低 了采样速率 更好的适应了日益增多的处理信息 压缩感知理论用数学形式描述为 图像信号x的长度为n x可以表示为 空 间 n r内n 1 维 的 列 向 量 即x属 于 n r 假 设 某 正 交 基 或 某 紧 致 结 构 12 n 其中 n n c 其中c是复数集合 h 是 的共轭矩阵 并且 i为单位矩阵 x在 上是可压缩的 则x和 的关系可 以通过变换系数 表示为 1 x n ii i 2 1 其中 是x的变换基 是x的等价或者逼近的稀疏表示 i 是 x i 构成的n 1 的列向量 当 0 k 且k 0 fk fk 结束 y y y n n n 36 数的逼近 将得到的二次函数的极小点作为下一次的迭代点 重复迭代过程 直至满足停止条件或者求出极小点 用数学表示为 在当前点 k x处将目标函数 做二阶泰勒展开 取前三项 至二阶项 得到公式 4 1 tt 1 2 kkkkkkk q xfgxxxxg xx 4 1 其中 kk gf x 2 kk gf x 若 k g非奇异 则计算公式 4 1 中的极值点 作为下一个迭代点 得到式 4 2 1 1kkkk xxg g 4 2 拟牛顿法是牛顿法的一种继承和改进 该方法具有超线性收敛性 同时也 克服了牛顿法中全局收敛性差以及每次迭代计算量大的缺点 拟牛顿法的基本 思想是延续牛顿法的下降方向 利用相邻两点的位移以及一阶导数构造与二阶 导数矩阵近似的正定矩阵 用满足拟牛顿条件的正定矩阵替代二阶导数矩阵求 解极值问题 该方法的计算量比牛顿法少 收敛速度达到超线性收敛 拟牛顿 的基本实现的基本条件是 1 1kkk gys 4 3 其中 1kkk sxx 1kkk ygg 为方便表示 令 1 11kk hg 基于 broyden 族的拟牛顿法的计算步骤如下 步骤 0 选择初值 给定初始点 n 0 rx 0 n n 0 rh 对称正定 计数器0k 步骤 1 检验终止条件 计算 k g 若 k g 则 k xx 算法终止 步骤 2 计算搜索方向 kkk dh g 步骤 3 确定搜索步长 并计算新的迭代点 用线搜索法计算步长0 k 令 1kkkk xxd 步骤 4 利用 broyden 族校正公式校正迭代矩阵 得到 1k h 更新迭代点 k k 1 转到步骤 1 4 2 2 基于拟牛顿的梯度投影算法 本论文将适用于多维无约束的拟牛顿法思想融合到梯度投影算法中 形成 一 种 新 的 梯 度 投 影 算 法 gprs qn gradient projection for sparse reconstruction quasi newton 该算法主要针对公式 3 9 进行处理 目标函 数矩阵作海森近似 将拟牛顿法融合到梯度投影算法中 在满足约束条件的情 况下采用拟牛顿法计算搜索方向和步长 保证了稳定的收敛性 并且在每次迭 代中进行近似矩阵的校正 获得更加逼近目标函数的近似矩阵 从而提高了算 法整体的重构性能和稳定性 gpsr qn 算法主要是公式 3 9 中每个元素的特点 利用矩阵 b 的特殊 结构 采用近似的办法逼近目标矩阵 从而减少每次迭代的大量计算 gpsr qn 算法的主要思想是用近似矩阵 k m替代海森矩阵 k g 然后用牛顿法求得一个确 37 定的下降方向 利用非精确线搜索方法求得使下一迭代点函数值最小的搜索步 长 再用修正的 bfgs broyden fletcher goldfarb shanno 算法进行校正 并 得到矩阵 1 k m 若依照当前下降方向更新的迭代点不能满足约束条件 则记录 上一个迭代点的负值 依据判定条件的结果更新下一个迭代点和近似矩阵 算法的实现原理是将海森矩阵 2 kk gf x 做如下近似 i kk gm 4 4 其中i是单位矩阵 则 k m 满足 111 kkkkk mxxgg 4 5 其中 kk gf x 为简化计算 令 1 11kk hm 则式 4 5 变形得到 111 kkkkk hggxx 4 6 gpsr qn 算法改进了拟牛顿法中一阶导数偏移量 在原先的 1kkk ygg 的基 础上 修改为 11 1 2 2 f f kkkkk kkk k xxggs ygg s 4 7 公式 4 7 在一阶导数偏移量中增加了目标函数与一阶导数和位移量增量值 能够更加逼近目标函数 根据公式 1kkk sxx 和公式 4 7 求出秩矩阵 1 tttt kkkkkkkkkkk k ttt kkkkkk y h ys ss y hh y s d s ys ys y 4 8 将公式 4 8 的秩矩阵与变形得到的近似矩阵相加即可得到近似矩阵的修正 bfgs 校正 算法的具体实现步骤如下 步骤 0 选定初始值 0 x 选取 0 1 迭代计数器 0k 步骤 1 依照近似矩阵 k h 利用牛顿法计算下降方向 kkk dg h 步骤 2 计算差值 kkkk xdx 其中 记作 0 xmaxx 步骤 3 t kkk b 若0 k 则 1 k 否则线搜索步长 k 使得 kkk f x 最小 更新估计值 1kkkk xx 步骤 4 设定h h h kminmax 根据公式 4 8 求得 1 hhd kkk 当 0 k 时 1 hh kmax 否则 11 hmid h h h kminkmax 步骤 5 令1kk 若满足停止准则输出x 否则转到步骤 1 相比较 gpsr basic 算法 虽然其算法的方向搜索和步进长度的计算上能 够取得较好的恢复效果 且从理论上算法具有二阶收敛性 但是在实际应用中 算法的收敛性不高 主要原因在于一般情况下 所求解的问题不是整体收敛的 虽然局部具有二阶收敛性但是整体收敛性却不高 并且每次迭代需要计算二阶 导数矩阵 而且确定搜索步进 的向后算法所需的计算量无法正常估计 因此 算法在运行时间上花费较多 且收敛性不稳定 而基于拟牛顿的梯度投影法最大的贡献是在迭代过程中将原来的目标函数 38 做近似 因而不需要在每次迭代中都计算二阶导数矩阵 因此这样得到的新的 目标函数的计算量相比较原来的目标函数要少很多 为了减少计算量将目标函 数近似得到的结果就是图像恢复效果势必要受到影响 为了弥补近似矩阵导致 的恢复上的不足 gps