图像工程–下册：图像理解（第4版）

图像工程由清华大学章毓晋教授编著，是图像领域***经典，已印刷60多次，20多万册。全套书分为图像处理、分析、理解三个层次（三册），全面涵盖基本概念、基本原理、典型方法、实用技术以及国际上有关研究的新成果。第1版获全国普通高等学校优秀教材一等奖；第2版评为全国普通高等教育“十一五”精品教材；第3版评为“十二五”普通高等教育本科*规划教材，2013年北京高等教育精品教材。 

本书为《图像工程》第4版的下册，主要介绍图像工程的第三层次——图像理解的基本概念、基本原理、典型方法、实用技术以及国际上有关研究的新成果。
本书主要分为4个单元。第1单元（包含第2~5章）介绍图像采集表达技术，其中第2章介绍摄像机成像模型和标定技术，第3章介绍压缩感知理论及其在成像中的应用，第4章介绍采集含深度信息图像的方法，第5章介绍各种表达3D景物的技术。第2单元（包含第6~9章）介绍景物重建技术，其中第6章介绍双目立体视觉方法，第7章介绍多目立体视觉方法，第8章介绍从多幅图像恢复景物的技术，第9章介绍从单幅图像恢复景物的技术。第3单元（包含第10~12章）介绍场景解释技术，其中第10章介绍知识表达和推理方法，第11章介绍目标和符号匹配技术，第12章介绍场景分析和语义解释的内容。第4单元（包含第13~15章）介绍三个研究方向的示例，其中第13章介绍多传感器图像信息融合方法，第14章介绍基于内容的图像和视频检索技术，第15章介绍时空行为理解的内容。书中的附录介绍了有关视觉和视知觉的一些知识，与各章都有一些联系。书中还提供大量例题、思考题和练习题，并对部分练习题提供了解答。书末还给出了主题索引。
本书可作为信号与信息处理、通信与信息系统、电子与通信工程、模式识别与智能系统、计算机视觉等学科研究生专业基础或专业课教材，也可供信息与通信工程、电子科学与技术、计算机科学与技术、测控技术与仪器、机器人自动化、生物医学工程、光学、电子医疗设备研制、遥感、测绘和军事侦察等领域的科技工作者参考。

 

 

 

目录

 

 

第1章绪论

 

1．1图像工程的发展

 

1．1．1基本概念和定义概括

 

1．1．2图像技术发展情况回顾

 

1．2图像理解及相关学科

 

1．2．1图像理解

 

1．2．2计算机视觉

 

1．2．3其他相关学科

 

1．2．4图像理解的应用领域

 

1．3图像理解理论框架

 

1．3．1马尔视觉计算理论

 

1．3．2对马尔理论框架的改进

 

1．3．3关于马尔重建理论的讨论

 

1．3．4新理论框架的研究

 

1．4内容框架和特点

 

总结和复习

 

第1单元采
集 表 达

 

第2章摄像机成像

 

2．1视觉过程

 

2．2摄像机成像模型

 

2．2．1基本摄像机模型

 

2．2．2近似投影模式

 

2．2．3一般摄像机模型

 

2．2．4通用成像模型

 

2．3摄像机标定

 

2．3．1标定程序和参数

 

2．3．2两级标定法

 

2．4亮度成像

 

2．4．1光度学和光源

 

2．4．2从亮度到照度

 

总结和复习

 

第3章压缩感知与成像

 

3．1压缩感知概述

 

3．2稀疏表达

 

3．3测量矩阵及特性

 

3．3．1采样/测量模型

 

3．3．2测量矩阵特性

 

3．4解码重构

 

3．4．1重构原理

 

3．4．2测量矩阵的校准

 

3．4．3典型重构算法

 

3．5稀疏编码与字典学习

 

3．5．1字典学习与矩阵分解

 

3．5．2非负矩阵分解

 

3．5．3端元提取

 

3．5．4稀疏编码

 

3．6压缩感知的成像应用

 

3．6．1单像素相机

 

3．6．2压缩感知磁共振成像

 

总结和复习

 

第4章深度信息采集

 

4．1高维图像和成像方式

 

4．1．1高维图像种类

 

4．1．2本征图像和非本征图像

 

4．1．3深度成像方式

 

4．2双目成像模式

 

4．2．1双目横向模式

 

4．2．2双目会聚横向模式

 

4．2．3双目轴向模式

 

4．3深度图像直接采集

 

4．3．1飞行时间法

 

4．3．2结构光法

 

4．3．3莫尔等高条纹法

 

4．3．4深度和亮度图像同时采集

 

4．4显微镜3D分层成像

 

4．4．1景深和焦距

 

4．4．2显微镜3D成像

 

4．4．3共聚焦显微镜3D成像

 

总结和复习

 

第5章3D景物表达

 

5．1曲线和曲面的局部特征

 

5．1．1曲线局部特征

 

5．1．2曲面局部特征

 

5．23D表面表达

 

5．2．1参数表达

 

5．2．2表面朝向表达

 

5．3等值面的构造和表达

 

5．3．1行进立方体算法

 

5．3．2覆盖算法

 

5．4从并行轮廓插值3D表面

 

5．53D实体表达

 

5．5．1基本表达方案

 

5．5．2广义圆柱体表达

 

总结和复习

 

第2单元景
物 重 建

 

第6章立体视觉：
双目

 

6．1立体视觉模块

 

6．2基于区域的双目立体匹配

 

6．2．1模板匹配

 

6．2．2立体匹配

 

6．3基于特征的双目立体匹配

 

6．3．1基本步骤

 

6．3．2尺度不变特征变换

 

6．3．3加速鲁棒性特征

 

6．3．4动态规划匹配

 

6．4视差图误差检测与校正

 

总结和复习

 

第7章立体视觉：
多目

 

7．1水平多目立体匹配

 

7．1．1水平多目图像

 

7．1．2倒距离

 

7．2正交三目立体匹配

 

7．2．1基本原理

 

7．2．2基于梯度分类的正交匹配

 

7．3多目立体匹配

 

7．3．1任意排列三目立体匹配

 

7．3．2正交多目立体匹配

 

7．4亚像素级视差计算

 

总结和复习

 

第8章景物恢复：
多图像

 

8．1单目景物恢复

 

8．2光度立体学

 

8．2．1景物亮度和图像亮度

 

8．2．2表面反射特性和亮度

 

8．2．3景物表面朝向

 

8．2．4反射图和亮度约束方程

 

8．2．5光度立体学求解

 

8．3从运动求取结构

 

8．3．1光流和运动场

 

8．3．2光流方程求解

 

8．3．3光流与表面取向

 

8．3．4光流与相对深度

 

总结和复习

 

第9章景物恢复：
单图像

 

9．1从影调恢复形状

 

9．1．1影调与形状

 

9．1．2亮度方程求解

 

9．2纹理与表面朝向

 

9．2．1单目成像和畸变

 

9．2．2由纹理变化恢复朝向

 

9．2．3检测线段纹理消失点

 

9．2．4确定图像外消失点

 

9．3由焦距确定深度

 

9．4根据三点透视估计位姿

 

总结和复习

 

第3单元场
景 解 释

 

第10章知识表达和推理

 

10．1知识基础

 

10．2场景知识

 

10．2．1模型

 

10．2．2属性超图

 

10．2．3基于知识的建模

 

10．3过程知识

 

10．4知识表达

 

10．4．1知识表达要求

 

10．4．2知识表达类型

 

10．4．3图像理解系统中的知识模块

 

10．4．4基本知识表达方案

 

10．5逻辑系统

 

10．5．1谓词演算规则

 

10．5．2利用定理证明来推理

 

10．6语义网

 

10．7产生式系统

 

总结和复习

 

第11章广义匹配

 

11．1匹配概述

 

11．1．1匹配策略和类别

 

11．1．2匹配和配准

 

11．1．3匹配评价

 

11．2目标匹配

 

11．2．1匹配的度量

 

11．2．2对应点匹配

 

11．2．3字符串匹配

 

11．2．4惯量等效椭圆匹配

 

11．2．5形状矩阵匹配

 

11．3动态模式匹配

 

11．4关系匹配

 

11．5图同构匹配

 

11．5．1图论简介

 

11．5．2图同构和匹配

 

11．6线条图标记和匹配

 

总结和复习

 

第12章场景分析和语义解释

 

12．1场景理解概述

 

12．2模糊推理

 

12．2．1模糊集和模糊运算

 

12．2．2模糊推理方法

 

12．3遗传算法图像解释

 

12．3．1遗传算法原理

 

12．3．2语义分割和解释

 

12．4场景目标标记

 

12．5场景分类

 

12．5．1词袋/特征包模型

 

12．5．2pLSA模型

 

12．5．3LDA模型

 

总结和复习

 

第4单元研
究 示 例

 

第13章多传感器图像信息融合

 

13．1信息融合概述

 

13．2图像融合

 

13．2．1图像融合的主要步骤

 

13．2．2图像融合的三个层次

 

13．2．3图像融合效果评价

 

13．3像素级融合方法

 

13．3．1基本融合方法

 

13．3．2融合方法的结合

 

13．3．3小波融合时的分解层数

 

13．3．4压缩感知图像融合

 

13．3．5像素级融合示例

 

13．4特征级和决策级融合方法

 

13．4．1贝叶斯法

 

13．4．2证据推理法

 

13．4．3粗糙集理论法

 

总结和复习

 

第14章基于内容的图像和视频检索

 

14．1图像和视频检索原理

 

14．2视觉特征的匹配和检索

 

14．2．1颜色特征匹配

 

14．2．2纹理特征计算

 

14．2．3多尺度形状特征

 

14．2．4综合特征检索

 

14．3基于运动特征的视频检索

 

14．3．1全局运动特征

 

14．3．2局部运动特征

 

14．4视频节目分析和索引

 

14．4．1新闻视频结构化

 

14．4．2体育比赛视频排序

 

14．4．3家庭录像视频组织

 

14．5语义分类检索

 

14．5．1基于视觉关键词的图像分类

 

14．5．2高层语义与气氛

 

总结和复习

 

第15章时空行为理解

 

15．1时空技术

 

15．2时空兴趣点

 

15．3动态轨迹学习和分析

 

15．3．1自动场景建模

 

15．3．2学习路径

 

15．3．3自动活动分析

 

15．4动作分类和识别

 

15．4．1动作分类

 

15．4．2动作识别

 

15．5活动和行为建模

 

15．5．1动作建模

 

15．5．2活动建模和识别

 

15．6主体与动作联合建模

 

15．6．1单标签主体动作识别

 

15．6．2多标签主体动作识别

 

15．6．3主体动作语义分割

 

总结和复习

 

附录A视觉和视知觉

 

A.1视知觉概述

 

A.2视觉特性

 

A.2．1视觉的空间特性

 

A.2．2视觉的时间特性

 

A.2．3视觉的亮度特性

 

A.3形状知觉

 

A.3．1轮廓

 

A.3．2图形和背景

 

A.3．3几何图形错觉

 

A.4空间知觉

 

A.4．1非视觉性深度线索

 

A.4．2双目深度线索

 

A.4．3单目深度线索

 

A.5运动知觉

 

部分思考题和练习题解答

 

参考文献

 

主题索引

全套书第4版前言

这是《图像工程》第4版，全套书仍分3册，分别为《图像工程（上册）——图像处理》《图像工程（中册）——图像分析》和《图像工程（下册）——图像理解》。它们全面介绍图像工程的基础概念、基本原理、典型方法、实用技术以及国际上相关内容研究的新成果。 《图像工程》第3版也分3册，名称相同。上、中、下册均在2012年出版，而2013年出版了《图像工程》第3版的3册合订本。第3版至今已重印13次，总计3万多册。 《图像工程》第2版也分3册，名称相同。上、中、下册分别在2006年、2005年和2007年出版，2007年还出版了《图像工程》第2版的3册合订本。第2版共重印18次，总计近7万册。 《图像工程》第1版也分3册，名称分别为《图像工程（上册）——图像处理和分析》《图像工程（下册）——图像理解和计算机视觉》和《图像工程（附册）——教学参考及习题解答》。这3册分别在1999年、2000年和2002年出版。第1版共重印27次，总计约11万册。 《图像工程》的多次重印表明作者一直倡导的，为了对各种图像技术进行综合研究、集成应用而建立的整体框架——图像工程——作为一门系统研究各种图像理论、技术和应用的新的交叉学科得到了广泛的认可，也在教学中得到大量使用。同时，随着研究的深入和技术的发展，编写新版的工作也逐渐提到议事日程上来。 第4版的编写开始于2016年，是年暑假静心构思了全套书的整体框架。其后，根据框架陆续收集了一些的相关书籍和文献（包括印刷版和电子版），并仔细进行了阅读和做了笔记。这为新版的编写打下了一个坚实的基础。期间，还结合以往课堂教学和学生反馈，对一些具体内容（包括习题）进行了整理和调整。第4版内容具有一定的深度和广度，希望读者通过本套书的学习，能够独立和全面地了解该领域的基本理论、技术、应用和发展。 第4版在编写的方针上，仍如前3版那样力求具有理论性、实用性、系统性、实时性； 在内容叙述上，力求理论概念严谨，论证简明扼要。在内容方面，第4版基本保留了第3版中有代表性的经典内容，同时考虑图像技术的飞速发展，还认真选取了近年的一些研究成果和得到广泛使用的典型技术进行充实。这些新内容既参考了许多有关文献，也结合了作者的一些研究工作和成果以及这些年来的教学教案。除每册书增加一章全新内容外，还各增加了多个节和小节，并特别增加了许多例题，其中有些介绍新的选学内容，有些则从其他的角度来补充解释已有的概念和方法。这些例题可根据课时安排、学生基础等选择使用，比较灵活。总体来说，第4版的内容覆盖面更广，介绍更全面细致，整体篇幅比第3版有约20%的增加。 第4版在具体结构和章节安排方面仍然保留了第3版的特点： ，各册书均从第2章就开始介绍正式内容，更快进入主题。先修或预备内容分别安排在需要先修部分的同一章前部，从教学角度来说，更加实用，也突出了主线内容。 第二，除第1章绪论外，各册书的正式内容仍都结合成4个主题相关的单元（并画在封面上），每个单元都有具体说明，帮助选择学习。全书有较强的系统性和结构性，也有利于复习考核。 第三，各章中的习题均只有少部分给出了解答，使教师可以更灵活地选择布置。更多的习题和其余的习题解答将会放在出版社网站上，便于补充、改进，网址为www.tup.com.cn。
第四，各册书后均仍有主题索引（并给出了英文），这样既方便在书中查找有关内容，又方便在网上查找有关文献和解释。
第4版还增加了一项新的举措。书中的彩色图片印刷后均为黑白的，但可以通过手机扫描图片旁的二维码，调出存放在出版社网站上的对应彩色图片，获得更多的信息和更好的观察效果。

从1996年开始编写《图像工程》第1版以来至今已20多年。期间，作者与许多读者（包括教师、学生、自学者等）有过各种形式的讨论和交流，除了与一些同行面谈外，许多人打来电话或发来电子邮件。这些讨论和交流使作者获得了许多宝贵的意见和建议，在编写这4版中都起到了不可或缺的作用，特别是在解释和描述的详略方面都结合读者反馈意见进行了调整，从而更加容易理解和学习。值得指出的是，书中还汇集了多年来不少听课学生的贡献，许多例题和练习题是在历届学生作业和课堂讨论的基础上提炼出来的，一些图片还直接由学生帮助制作，在选材上也从学生的反馈中受到许多启发。借此机会对他们一并表示衷心的感谢。 书中有相当内容基于作者和他人共同研究的成果，特别是历年研究室的学生（按姓名拼音排序）： 卜莎莎、边辉、蔡伟、陈权崎、陈挺、陈伟、陈正华、崔崟、程正东、戴声扬、段菲、方慕园、冯上平、傅卓、高永英、葛菁华、侯乐天、胡浩基、黄英、黄翔宇、黄小明、贾波、贾超、贾慧星、姜帆、李佳童、李娟、李乐、李品一、李勍、李睿、李硕、李闻天、李相贤（LEE Sang Hyun）、李小鹏、李雪、梁含悦、刘宝弟、刘晨阳、刘峰、刘锴、刘青棣、刘惟锦、刘晓旻、刘忠伟、陆海斌、陆志云、罗惠韬、罗沄、朴寅奎（PARK In Kyu）、钱宇飞、秦暄、秦垠峰、阮孟贵（NGUYEN Manh Quy）、赛义（Saeid BAGHERI）、沈斌、谭华春、汤达、王树徽、王宇雄、王志国、王志明、王钟绪、温宇豪、文熙安（Tristan VINCENT）、吴高洪、吴纬、夏尔雷（Charley PAULUS）、向振、徐丹、徐枫、徐洁、徐培、徐寅、许翔宇、薛菲、薛景浩、严严、杨劲波、杨翔英、杨忠良、姚玉荣、游钱皓喆、鱼荣珍（EO Young Jin）、俞天利、于信男、袁静、贠亮、张宁、赵雪梅、郑胤、周丹、朱施展、朱小青、朱云峰，博士后高立志、王怀颖以及进修教师崔京守（CHOI Jeong Swu）、郭红伟、石俊生、杨卫平、曾萍萍、张贵仓等。第1版、第2版、第3版和第4版采用的图表除作者本人制作的外，也包括他们在研究工作中收集和实验得到的。该书应该说是多人合作成果的体现。 后，感谢妻子何芸、女儿章荷铭在各方面的理解和支持！

章毓晋2018年元旦于书房

通信： 北京，清华大学电子工程系，100084
办公： 清华大学，罗姆楼，6层305室
电话： (010) 62798540
传真： (010) 62770317
电邮： zhang[email protected]
主页： oa.ee.tsinghua.edu.cn/~zhangyujin/

第3章压缩感知与成像

2006年，Donoho和Candès等提出一种新颖的信号采样和处理理论，即压缩感知(CS)理论［Donoho 2006］、［Candès 2006］。该理论将信号采样和压缩结合进行，提高了信号采集和信息处理能力，突破了奈奎斯特香农采样定理的瓶颈，大大缓解了数据采集、存储、传输和分析的压力。压缩感知理论指出，当信号在某个变换域里可压缩或稀疏时，通过采集少量的信号的非自适应线性投影值，构建数学重构模型并利用重构算法求解，可以较精确地重构原信号。简单地说，稀疏的或具有稀疏表达的有限维数的信号可以利用远少于奈奎斯特香农采样数量的线性、非自适应的测量值而无失真地重建出来。压缩感知的理论框架和研究内容主要涉及稀疏表达、测量编码和解码重构三方面，即用于稀疏表达(表示)的稀疏编码、用于测量编码的测量矩阵和用于重建信号的重构算法。首先，稀疏表达是压缩感知理论的先验/先决条件。其次，测量编码是压缩感知硬件实现的关键，但这里并非直接测量信号本身，而是经过测量矩阵将信号投影到低维空间，并保持信号原本的结构信息。后，解码重构是压缩感知理论的核心，指利用尽量少的测量值，快速、鲁棒、精确地重构原信号。根据上述的讨论，本章各节将安排如下。3．1节介绍压缩感知的整体流程，并引出3个关键处理步骤。另外，还对压缩感知与奈奎斯特香农采样在流程和特性方面进行了对比。3．2节介绍对信号的稀疏表达，通过把信号变换到一个新的基或框架下，使其非零系数的个数远远少于原始信号的项数时，就可以实现压缩感知了。3．3节讨论测量编码模型，不仅介绍了针对本身稀疏信号的测量模型，还介绍了具有普适性的测量模型。另外，还对测量矩阵应满足的两个特性进行了分析。3．4节介绍了基本的重构模型，分析了无噪声和有噪声时重构稀疏信号的原理，并列举了几类典型的重构算法。3．5节讨论了曾与压缩感知并行发展，密切相关又互相影响的稀疏编码与字典学习问题。稀疏编码与信号的稀疏表达对应，而字典学习的目标就是要实现对信号的稀疏表达。3．6节列举两个压缩感知在成像应用方面的典型示例： 一个是单像素相机的设计； 另一个是利用压缩感知的磁共振成像。3．1压缩感知概述压缩感知的整体流程框图可见图3．1．1，其中行的3个方框分别代表压缩感知的3个关键处理步骤(每个方框的左面是输入，右边是输出)，第二行的3个方框分别指示实现压缩感知要完成的3个工作(分别对应3个关键处理步骤)。

图3．1．1压缩感知流程

压缩感知有3个关键处理步骤： (1) 稀疏表达判断信号是否具有稀疏性是实现压缩感知的前提。事实上，自然信号很少是真正稀疏的。当认为某个信号稀疏时，严格地说是指这个信号可以通过稀疏信号近似表达。这里的工作就是要找到对信号可压缩的某个正交基或紧框架(见下)，从而可实现对信号的稀疏表达。从数学角度来说，是要构建稀疏变换矩阵，实现对多维数据进行线性分解的表达方法。(2) 测量编码对信号采用一个与稀疏变换矩阵不相关(与稀疏变换的基不相关且平稳)的线性投影进行稀疏测量/观测，从而获得感知测量值。对感知测量值的表达常称为编码，所以统称测量编码。进行稀疏变换的测量矩阵是压缩感知理论能否成功实现的关键。这里对观测矩阵的设计不仅关系到压缩和采样过程的快慢，而且要保证对稀疏向量降维时重要信息不遭到破坏，从而提高恢复信号的准确性。(3) 解码重构这是压缩感知模型求解的保证，也是压缩感知的核心部分。其含义是运用压缩测量的低维数据(感知测量值)精确地重构高维的原始信号。这里的工作是要设计快速的重构算法，从一个非常少的线性观测中恢复信号，重构算法的优劣决定了恢复信号的质量。

例3．1．1压缩感知与奈奎斯特香农采样的对比从信号处理的角度看，压缩感知与奈奎斯特香农采样有很多区别。图3．1．2同时画出了它们的基本流程，左边为香农采样的流程，高速采样后压缩以减少数据量，在需要原始图像时对压缩结果进行解压； 右边为压缩感知采样的流程，借助稀疏变换实现低速采样，利用观测矩阵实现投影降维，在需要原始信息时将图像重构出来。

图3．1．2压缩感知与奈奎斯特香农采样的流程对比

表3．1．1给出对压缩感知与奈奎斯特香农采样在5个特性方面的对比情况。

表3．1．1压缩感知与奈奎斯特香农采样的特性对比

特性奈奎斯特香农采样压缩感知采样必要条件信号带宽有限： 才可能无损恢复信号具有稀疏性/可压缩性： 才可能实现恢复采样方式直接采样： 通过Sinc函数直接与目标信号进行内积来获取采样非直接采样： 通过采样/测量矩阵与目标信号进行乘积间接地获取采样/测量值采样特点均匀采样： 用目标信号中频率2倍以上的采样率对目标信号进行等间隔采样非均匀采样： 用随机非均匀的采样方式借助非相关测量矩阵对目标信号进行采样/测量采样个数信号频率决定采样个数： 采样率至少为目标信号中频率的2倍，以实现无失真采样稀疏性决定采样个数： 如果目标信号中仅有少量个非零信号，则只需用很少的采样/测量个数以恢复原始信号从采样恢
复信号所采即所得： 只需用Sinc函数插值就可直接重建原始信号需要重建步骤： 因没有直接对目标信号采样，所以需要(如利用基于L1范数小化的步骤)进行信号恢复工作□3．2稀 疏 表 达对信号的稀疏表达是实现压缩感知的先决条件。需要指出的是，虽然自然信号都有一定的稀疏性，但很少有信号是真正稀疏的，直接满足压缩感知的要求。一般认为某个信号是稀疏的时候，是指这个信号可以通过稀疏信号来近似地表达。下面来具体讨论。先复习、介绍和讨论一些预备知识。1． 矢量空间
下面的讨论中将有限域中的离散信号看成分布在N维欧氏空间中的矢量，将这个空间记为RN。在RN中，范数是一个重要描述。矢量x的范数Lp(p≥1)可定义如下： 

‖x‖p=∑Ni=1xip1/pp∈［1,∞)
maxxip=∞i=1,2,…,N(3．2．1)

其中，|S|为集合S的基数，即集合S中元素的个数。常用的几个范数分别为L1，L2和L∞。它们的特性分别如图3．2．1(a)、(b)、(c)所示(可对比上册书中图3．1．5)。在p<1的情况下，式(3．2．1)中定义的范数已经无法满足三角不等式，所以它本质上是拟范数。拟范数所对应的R2中的单位圆不再是凸集。例如，拟范数L1/2所对应的R2中的单位圆{x:‖x‖1/2=1}如图3．2．1(d)所示。又如，拟范数L0所对应的R2中的单位圆{x:‖x‖0=1}如图3．2．1(e)所示。这里，拟范数‖x‖0=|supp(x)|，其中supp(x)={i: xi≠0}表示x的支撑集。

图3．2．1不同范数在R2中的单位圆

例3．2．1不同范数在描述逼近误差时的不同表现可以采用范数来描述信号的强度或误差的大小。假设已知一个信号x∈R2，希望用一个1D仿射空间A中的点来逼近它。如果采用Lp范数来衡量这种逼近误差，那么任务就是找到x′∈A使得‖x-x′‖p小。这里对参数p的选择很关键，不同的p值将使得逼近误差具有不同的特性和表现。为了找出在A中接近x的点，可以想象一个以x为中心的Lp球不断地膨胀，它碰到A的点即为在Lp条件下接近x的点x′。如图3．2．2所示，图(a)对应L1范数，图(b)对应L2范数，图(c)对应L∞范数，图(d)对应L1/2拟范数，图(e)对应L0拟范数。

图3．2．24种p值的Lp在描述逼近误差时的不同表现

从图3．2．2可见，当p较大时，误差被均匀地扩散到2D空间中(与x不在同一水平或垂直轴上)； 当p较小时，这种误差的衡量方式将会有很大概率使所选择的x′与x位于同一水平或垂直轴上，即非对称地把误差缩小到1D空间中(减少了一个维度)，从而促进稀疏特性的产生。□2． 基和框架考虑矢量集ψ={ψi}，i=1,2,…,N，如果其中的矢量可以生成矢量空间V=RN，而且矢量ψi之间是非线性相关的，则ψ可以称为有限维矢量空间V中的基。换句话说，在矢量空间V中的任一个矢量都可以通过ψ中矢量的线性组合地表达，而且这种线性表达的系数可以通过使用信号和该矢量空间中基的内积来表示。表示矢量集的符号也可用来表示矩阵，如ψ可表示由列向量ψi构成的矩阵，其大小为N×N。标准正交集就是一种特殊的基，定义为： 矢量集ψ={ψi}，其中所有矢量之间是正交的且每个基的范数都为单位1，即ψTψ=I，I表示N×N的单位矩阵。此时，对于任何属于该矢量空间中的矢量x，可以很容易地计算出在该标准正交集表示下的系数a，即a=ψTx。把基的概念推广到一些可能线性相关的矢量集就形成列框架，即矢量集ψ={ψi}Ni=1且ψi∈Rd，其中d

L‖x‖22≤‖ψTx‖22≤R‖x‖22(3．2．2)

其中，00表示矩阵ψ中的行矢量一定是线性独立的。如果L被选为使这个不等式成立的可能存在的值，R被选为使这个不等式成立的可能存在的小值，则把它们称为无框架界。如果L=R，则这个框架称为紧框架。如果ψ是一个有限维矩阵，则L和R分别对应ψψT的小特征值和特征值。由于框架具有一定的冗余性，所以它可以对目标数据提供更为丰富的表达，即针对一个目标信号矢量x，存在无数个系数矢量a，使得x=ψa。3． 稀疏性表达为了更精炼地表达一个信号，可以把信号变换到一个新的基或框架下，当非零系数的个数远远少于原始信号的项数时，可以把这些少量的非零系数称为原始信号的稀疏性表达。在压缩感知的理论体系中，稀疏信号模型可以确保高倍的压缩率。只要预先知道目标信号在已知的基或框架下具有稀疏性表达，就可以无失真地重建原始信号。在稀疏性表达中，常把基或框架称为字典或过完备字典，而把其中的矢量元素称为原子。从数学的角度，当信号x中多有K个非零的值时，称信号x是K稀疏的，即‖x‖0≤K，可以采用ΣK={x:‖x‖0≤K}来表示所有K稀疏信号的集合。另外，对一些本身并不稀疏但在一些基矩阵ψ中具有稀疏性表达的信号，这时只要x=ψa，其中‖a‖0≤K，则仍可把这些信号看成K稀疏的。3．3测量矩阵及特性下面先比较讨论传统方法和压缩感知方法是如何获取信号的，然后讨论测量矩阵应具有的特性，后分析如何构建需要的测量矩阵。3．3．1采样/测量模型根据传统的奈奎斯特香农采样模型，对一个只包含K个非零值的信号x∈RN，需要采集N个值才能保证完全保持x中的信息。具体的采样过程可用采样矩阵Φ与信号矢量x的相乘来表示，即

y=Φx(3．3．1)
这个采样过程可用图3．3．1来表示。此时，采样矩阵对应一个对角单位矩阵，它将原始信号逐一映射到采样值矢量y。需要注意，此时在KN的情况下，仍需使用N个采样值，这必然带来很大的浪费。

图3．3．1奈奎斯特香农采样模型

压缩感知采样并不对原始信号逐一进行，而是通过一个测量矩阵Φ获取对x的M个线性观测/测量。这个过程仍可用式(3．3．1)的形式表示，但其中Φ是一个固定的M×N矩阵，采样所得的测量值y∈RM。先假设信号x本身是稀疏的，则此时的测量模型如图3．3．2所示，其中Φ对应一个降维的投影操作，即把RN映射到RM中。一般有K

图3．3．2针对本身稀疏信号的测量模型

由前面对稀疏表达的讨论可知，对本身并不稀疏的信号，可通过将其变换到一个新的基或框架下而使其表现出稀疏特性(可理解为用变换挖掘出了信号的稀疏性)，从而仍可构建压缩感知框架下的测量模型。换句话说，如果x本身不是稀疏信号，但在变换域Ψ中体现出稀疏性，即x=Ψz，则将Φ和Ψ合并，而测量过程仍可用式(3．3．1)的形式来表示。不过这种推广的、具有普适性的测量模型用图3．3．3来表示更为清晰。前面针对本身稀疏信号的测量模型对应Ψ=I的情况。

图3．3．3具有普适性的测量模型

3．3．2测量矩阵特性要实现压缩感知，测量矩阵应满足一定的特性［李2015］。1． 零空间及其特性对一个矩阵Φ： RN→RM，其零空间可定义为N(Φ)

N(Φ)={z:Φz=0}(3．3．2)
对任意稀疏信号x，如果希望基于测量值y=Φx无失真地重建该稀疏信号x，则对任意两个矢量x和x′∈ΣK={z:‖z‖0≤K}，一定有Φx=Φx′，否则基于测量值y将无法区别x和x′。假设Φx=Φx′，则Φ(x-x′)=0，其中x-x′=h∈Σ2K。由此可见，用矩阵Φ可以表达x的充分必要条件是Φ的零空间N(Φ)中不含有任何Σ2K中的元素，即N(Φ)与Σ2K的交集是空集。当要处理的是近似稀疏信号(其含有少数几个明显的非零元素，而其他元素则非常接近零，自然图像经小波变换后的系数就是这样的信号)时，需要对测量矩阵Φ的零空间引入一些更为严格的条件，以确保N(Φ)中不应包含稀疏的矢量，也不应包含可以压缩的近似稀疏的矢量。现在假设S{1,2,…,N}是一个索引集的子集，SC={1,2,…,N}＼S是其相应的补集，则矢量xS表示长度为N的矢量，且这个矢量中所有下标属于集合SC的元素都被设为0。类似地，矩阵ΦS表示长度为M×N的矢量，且其所有下标属于集合SC的列矢量都被设为零矢量。如果存在一个常数C>0，使得下式对所有h∈N(Φ)和所有|S|≤K的S都成立： 

‖hS‖≤C‖hSC‖1K(3．3．3)

则称矩阵Φ满足K阶零空间特性。现在用Δ: RM→RN表示一种基于信号稀疏性的重建算法，即基于M个测量值重建出原始N个目标信号的算法，而且MN。对于所有的x，可以要求该算法确保下式成立： 

‖Δ(Φx)－x‖2≤CσK(x)pKp=1(3．3．4)

其中，σK(x)p=min‖x-x′‖p，表示去除矢量x的K个幅值的元素后的p范数，即如果S表示x的K个元素的下标集合，则σK(x)p=‖xSC‖p。式(3．3．4)可以保证该重建算法能够正确地重建出所有可能的、有K个非零元素的信号，同时也能使得利用重建的稀疏信号来近似逼近非稀疏信号有一定的鲁棒性，所以称为具有普适性的重建条件。另外可以证明，如果(Φ,Δ)满足式(3．3．4)，则矩阵Φ满足2K阶零空间特性。2． 约束等距特性零空间特性是确保重建的必要条件，但推导时并没有考虑噪声的影响。当测量值有噪声或在量化时引入误差时，需要讨论更为严格的重建条件。为此，定义K阶约束等距特性(RIP)如下。如果存在δK∈(0,1)，使得

(1－δK)‖x‖22≤‖Φx‖22≤(1 δK)‖x‖22(3．3．5)

对所有x∈ΣK{x:‖x‖0≤K}都成立，则称矩阵Φ满足K阶约束等距特性，δK称为矩阵Φ的约束等距常数(δK是对所有K阶稀疏矢量x均满足的小整数)。矩阵的RIP是针对两个参数δK和K而言的。如果说某一个矩阵满足RIP，即对特定的δK和K，式(3．3．5)对任意x∈ΣK均成立。如果矩阵Φ满足2K阶约束等距特性，则可以把式(3．3．5)解释为： 任意一对K阶稀疏的矢量经过矩阵Φ的线性变换后，它们之间的欧氏距离几乎保持不变，即测量矩阵近似地保持两个K阶稀疏矢量间的欧氏距离，这一特性对克服噪声起重要作用。这同时也表明K阶稀疏的矢量不在测量矩阵的零空间中，因为如果在其中，则信号就无法重建了。约束等距特性也可以表示成： 随机地从测量矩阵中选取2K列，所构成的子集只能是“近似正交”的。这是因为这个子集的行列长度不同，所以不可能是真正的正交。假设利用测量矩阵Φ获取一维K阶稀疏矢量x的线性测量值y，当δ2K<1时，就可以基于测量矢量y=Φx重建出原始K阶稀疏矢量，这个重建出的K阶稀疏矢量是满足方程y=Φx的稀疏解，即非零元素个数少。所以，如果要重建出独一无二的K阶稀疏矢量，必须要确保δ2K<1，同时约束等距常数δK不可能为0，因为如果δ2K=0，则说明测量矩阵Φ是标准正交矩阵，但这是不可能的，因为测量矩阵的列数远大于行数。约束等距特性指出： 所求解的精度和稀疏度是取决于测量矩阵或约束等距常数的。但是，某个测量矩阵是否满足这个特性并无法通过计算的方式来判断，因为这是一个NP难题。如果一个矩阵满足约束等距特性，则它一定满足零空间特性，即约束等距特性比零空间特性更为严格。如何构建满足RIP的测量矩阵呢？固定地构建满足K阶RIP且尺寸为M×N的测量矩阵是可能的，但要求相对较大的M。如果在构建过程中引入随机性，可以降低对大测量个数M的要求。这些通过随机方法构建的测量矩阵也常称为通用测量矩阵。可以证明，对由亚高斯随机分布产生的测量矩阵所测得的矢量范数高度集中于原始信号的均值，所以服从亚高斯随机分布的矩阵满足RIP。使用这样得到的测量矩阵就可以实现利用少采样个数来完成采样的目的。3．4解 码 重 构重构也称重建，目标是要基于很少的线性观测值来重建出稀疏的目标信号。重构是模型求解的保证。下面先讨论重构的原理，再介绍各种典型的重构算法。3．4．1重构原理先介绍一种直观的重构模型，借此讨论重构的原理以及分析对无噪声稀疏信号重构的问题和对有噪声稀疏信号重构的问题。1． 基本重构模型假设矢量x∈RN是一个长度为N的稀疏信号，测量矩阵Φ: RN→RM已知，现在要基于很少数量的测量值y∈RM，M

min‖x‖0,s.t．y=Φx,测量值无噪声的情况
min‖x‖0,s．t．‖Φx-y‖2≤ε,测量值存在少量有界噪声的情况(3．4．1)

如果原始目标信号在某个正交变换域或稀疏字典Ψ中体现出稀疏特性，即x=Ψz，其中‖z‖0≤K，则可将式(3．4．1)改写为

min‖z‖0,s．t．y=ΦΨx,测量值无噪声的情况
min‖z‖0,s．t．‖ΦΨx-y‖2≤ε,测量值存在少量有界噪声的情况(3．4．2)

可见，如果令Θ=ΦΨ，则本质上前面两式是等价的。下面仅考虑Ψ=I的情况。求解式(3．4．1)或式(3．4．2)是一个组合优化问题，所以是一个NP难题，可采用凸的L1范数来近似非凸的L0范数，把组合优化问题转化为凸优化问题。换句话说，通过这样的近似可把一个无法求解的问题转化为一个通过现代优化理论能够求解的问题。这在统计学中也称为Lasso。当测量值没有噪声时，得到如下基本追踪表达式： 

min‖x‖1，s．t．y=Φx(3．4．3)

当测量值存在少量有界噪声时，得到如下基本追踪去噪方法的表达式： 

min‖x‖1，s．t．‖Φx－y‖2≤ε(3．4．4)

2． 无噪声稀疏信号重构考虑一个更为通用的无噪声稀疏信号重构问题： 

x′=argminx‖x‖1，s．t．x∈B(y)(3．4．5)

其中，B(y)确保x′与测量值y保持一致。对B(y)可有多种选择，对应式(3．4．3)，B(y)为{x: Φx=y}。例如，假设测量矩阵Φ满足2K阶约束等距特性且δ2K<2-1。已知x,x′∈RN，并定义h=x′-x； 设S表示矢量x中K个幅值元素的下标集合，T表示矢量hSC中K个幅值元素的下标集合，R=S∪T。如果‖x′‖1≤‖x‖1，则可以证明

‖h‖2≤C0σK(x)1K C1〈ΦhR,Φh〉‖hR‖2(3．4．6)

其中，σK(x)1=‖xSC‖1=‖x-xS‖1，C0和C1都是仅依赖于δ2K的常数。式(3．4．6)为式(3．4．5)中L1范数小化方法带来的误差建立了一个界限，其中的前提条件是测量矩阵Φ满足2K阶约束等距特性。为了针对具体的B(y)构建出特殊的界限条件，需要考虑x′∈B(y)是如何影响||的。以没有测量噪声的情况为例。可以证明，当x∈ΣK={x:‖x‖0≤K}时，如果Φ满足约束等距特性，则只要O(Kln(N/K))个采样值就可以无失真地重建任何包含K个非零元素的目标信号x，而不需考虑这K个非零元素具体如何分布。3． 有噪声稀疏信号重构考虑一个通用的、存在噪声污染情况下的稀疏信号重构问题： 

x′=argminx‖x‖1，s．t．x∈B(y)(3．4．7)

其中，B(y)确保x′与测量值y保持一致。对B(y)可有多种选择，下面考虑两种情况。(1) 有界噪声污染信号的重构如果被污染信号的噪声是有界的，则假设测量矩阵Φ满足2K阶约束等距特性且δ2K<2-1。假设y=Φx e，其中e是测量过程带来的误差。由于噪声是有界的，即‖e‖2≤ε(ε为噪声界)，则当B(y)={x:‖y-Φx‖2≤ε}时，可以证明式(3．4．7)的解x′满足

‖h‖2=‖x′－x‖2≤C0σK(x)1K C1ε(3．4．8)

其中，C0和C1为仅依赖于δ2K的常数。(2) 高斯噪声污染信号的重构假设y=Φx e，噪声e∈RM的各分量来自于均值为零、方差为σ2的高斯分布，即满足标准正态分布N(0,σ2I)，则可推出总存在正实数k，使得对任何ε>0有下式成立： 

P‖e‖2≥(1 ε)Mσ≤exp－kε2M(3．4．9)

将式(3.4.9)与式(3．4．8)结合考虑，并令ε=1可以推出当B(y)={z:‖Φz-y‖2≤2σM}时，式(3．4．7)的解x′以至少1-exp(-kM)的概率满足

‖h‖2=‖x′－x‖2≤81 δ2K1－(1 2)δ2KMσ(3．4．10)

两种情况下重构都是有界的，这表明压缩感知确可应用到实际中。3．4．2测量矩阵的校准在讨论具体重构算法前，还有一个问题要先分析一下。如果测量矩阵本身存在噪声，则还需要考虑测量矩阵的校准问题。回到式(3．4．3)和式(3．4．4)，有可能测量矩阵并不是确切已知的，它可能通过模型来描述，但并不是实际中的测量矩阵； 或者有些情况下测量矩阵被校准后，随着客观工作条件变化，测量矩阵的物理条件也可能漂移。为解决这类问题，常用以下4种方案。(1) 忽略这个问题，这有可能明显影响重建精度。(2) 简单地把由非精确测量矩阵带来的影响当作噪声： 假设实际的非精确测量矩阵为Φ′，则观测值y=Φ′x ε，这样就可把压缩感知的重建问题转换为解下列问题： 

y=Φx ε η(3．4．11)
其中，η为由测量矩阵不精确带来的误差。实际中，由于很难获取η的统计特性，所以求解式(3.4.11)有一定的难度。(3) 监督校准： 利用已知的训练稀疏信号 x1,x2,…,xl,…,xL和相应的测量值yl=Φ′lxl εl。把所有的矢量排列起来组成矩阵的形式，有

Y=Φ′X E(3．4．12)
其中，需要基于这些已知的训练信号和测量值来校准测量矩阵： 

Φ′··=argminΦ‖Y－ΦX‖2F(3．4．13)

即要优化Φ′以使‖Y-Φ′X‖小。这种方案在能够获得已知稀疏信号的情况下可以使用，但在无法获得训练稀疏信号的情况下就无法实用。如果可以假设待校准的测量矩阵来自某些矩阵族也是有用的。例如，有时已知或假设未知的测量矩阵Φ在已知的字典中是稀疏的，即Φ≈∑jajΦj，且‖a‖0很小，其中a=［a1,…,aj,…］。这样，监督校准问题就可以转化为下面的凸优化问题： 

min‖a‖1s．t．Y－∑jajΦjX2F≤ε(3．4．14)

(4) 非监督校准： 针对少数几个未知信号(需要保证具有稀疏的特性)，利用它们各自有限的、基于压缩感知模型的采样值，开展盲校准，即无须采用已知的训练信号来校准测量矩阵，或训练的目标稀疏信号是未知的。具体是把未知的训练信号矢量x1,x2,…,xl表述成矩阵X，基于已知精确的测量矩阵Φ0和多组观测矢量y1,y2,…,yl形成的矩阵Y，通过一定的方法可以确定增益矩阵D和X，即解决下面这个问题： 

minD,X‖X‖1s．t．Y=DΦ0X(3．4．15)

不过，求解式(3．4．15)有可能导致出现无意义的解。如果对矩阵D和X没有限制，那么只要把矩阵D设为无穷大、让矩阵X趋于零，就可满足式(3．4．15)，但这样的解并没有实际意义。这里用一种描述方法重新表述这个问题，以提供一个凸集公式。将Y=DΦ0X表述为ΔY=Φ0X，其中，Δ=D-1=diag(δi)，diag(δi)是将所有的δi排列在对角线上形成的对角矩阵。为了避免前述的无意义解Δ=X=0，引入一个凸集归一化约束条件Tr(Δ)=Σiδi=M，其中Tr(·)表示矩阵的迹，即D=diag(di)，Σid-1i=M。这个约束条件也可以替换为δi=1等其他形式。由于可以对Δ引入任意约束，Δ和D本质上存在一个比例关系。以非监督方式校准测量矩阵的方法可以表示为 

(X′,Δ′)··=argmin‖X‖1s．t．ΔY=Φ0X,Tr(Δ)=M(3．4．16)

3．4．3典型重构算法有效的图像重构算法是压缩感知的关键技术之一。因为在不同的应用中对重构有不同的要求，所以重构算法和模型的设计多种多样。现在已有了许多不同的重构算法，它们在运算时间、重构精度和稳定性等方面都有各自的特点。1． 重构要考虑的因素设计稀疏信号重构算法需要考虑多方面的因素： (1) 先验信息： 如何充分发掘图像的先验信息从而构造有效的约束条件是图像重构的关键。目前常用的先验信息主要包括信号稀疏信息以及图像全变分信息。信号稀疏性体现在原始图像信号在某固定变换域或稀疏基(如离散余弦变换基、小波基等)上的投影系数稀疏，全变分值则考虑了图像相邻像素之间的相关性。(2) 测量值数量： 要求基于尽可能少的测量，稳定地重构出包含K个非零值的原始稀疏信号。(3) 抗噪声鲁棒性： 要求无论测量值包含噪声或测量系统本身具有系统噪声，重构算法都要稳定地重构出原始稀疏信号。(4) 重构速度： 要求在占用较少计算资源的情况下，重构算法能高效地实现稀疏信号重构。(5) 稳定性： 采用L1范数小化可以确保重建的稳定性，具体需要考虑相同的重建条件。通过考虑上述一些或全部因素，多数重建算法可分成4大类，包括凸优化算法、贪婪算法、组合算法、贝叶斯算法。下面分别对每大类介绍1~2个典型算法。2． 凸优化算法这类算法也称化逼近方法，其基本思路是用凸函数代替L0范数，并在一个RN空间中的凸集里去优化关于未知变量x的凸目标函数J(x)。这类算法重构精度高，需要的测量数据比较少，约为O(Klog(N/K))； 但计算速度慢，计算复杂性约为O(N3)。假设J(x)是一个能促进稀疏性的(即当目标信号x很稀疏时，J(x)的值很小)且凸的代价函数。在测量值没有噪声时，基于测量值y=Φx要重建信号x可以解下面的方程： 

min{J(x)},s．t．y=Φx(3．4．17)

而在测量值有噪声时，解下面的方程： 

min{J(x)},s．t．H(Φx,y)≤ε(3．4．18)

其中，H为用来对Φx和y之间的矢量距离进行惩罚的代价函数。式(3．4．18)也可以改写成没有约束条件的形式： 

min{J(x) λH(Φx,y)}(3．4．19)

其中，λ为一个惩罚因子，它可以通过试错法或交叉验证法来选取。常用的J和H为： J(x)=‖x‖1，即为稀疏信号x的L1范数； H(Φx,y)=0．5×‖Φx-y‖22，即为实际测量值y和理论测量值Φx之间误差的L2范数。在统计学中，在‖x‖1≤δ的条件下小化H(Φx,y)称为Lasso问题。(1) 总变分重构法从广义的角度，J(·)作为一个正则项也可以是其他复杂函数。例如，如果目标信号是阶梯函数，同时又在一个已知变换域Ψ中体现出稀疏性，则可以有一个如下的混合正则项： 

J(x)=TV(x) λ‖Ψx‖1(3．4．20)
其中，TV(x)为目标信号的总变分(所以得名)： 

TV(x)=∑Ni=0xi 1－xi(3．4．21)
可见，针对阶梯函数类型(或有丰富边缘)的信号x，总变分TV(x)将凸显出稀疏性。(2) 收缩循环迭代法如果考虑式(3．4．19)中H是二次型(凸函数且可导)，常可以使用收缩循环迭代法，也称软阈值法来解。该方法原是一种经典的基于小波变换域的图像去噪声方法，其中的收缩运算符定义为 

shrink(t,a)=t－at>a0－a≤t≤at at
用收缩循环迭代法解决式(3．4．19)的问题也很有效，基本方法可写成定点迭代的方式： 对于i=1,…,N，可将目标信号x的第i个分量在第k 1次迭代步骤写成 

xk 1i=shrinkxki－τH(xki)xki,μτ(3．4．23)
其中，τ>0是梯度下降法的步长，它可随着k而变化； μ可以根据噪声大小和经验来选取，μ越大说明允许xk 1i和xki之间的距离越大。针对有噪声污染测量值的重构问题，一种选取凸优化代价函数H(Φx,y)的常规方法是采用残差的L2范数： 

H(Φx,y)=12‖y－Φx‖22Hx=ΦT(Φx－y)(3．4．24)

针对这个特殊的惩罚函数，式(3．4．23)可以简化为 

xk 1i=shrinkxki－τΦT(Φxki－y),μτ(3．4．25)

3． 贪婪算法从本质上来说，稀疏信号重构是基于线性测量值y来重构出稀疏性的目标信号x，即重建出具有少的非零个数的目标信号x。换句话说，是求解 

min|I|:y=∑i∈Iixi(3．4．26)

其中，I{1,…,N}，表示一个索引集(对应支撑集)；  i表示矩阵Φ的第i列。式(3．4．26)可借助经典的稀疏逼近方法通过逐步选择矩阵Φ的列来逼近y，进而逐步确定索引集I。这类算法的复杂度大多是由寻找到正确索引集所需要的迭代次数所决定的，计算速度一般比较快，但是需要的测量数据多且重构的精度比较低。(1) 匹配追踪算法匹配追踪(MP)算法是一种基于迭代的贪婪算法。匹配追踪将一个信号看成由基/字典中的元素通过线性组合而构成的。在压缩感知的稀疏重建中，字典就是采样矩阵Φ∈RM×N，它的每列表示一种原型信号的元素(也称原子信号)。重构可描述为： 给定一个信号y，寻求通过这些基/字典中的元素的稀疏性组合来描述信号y。匹配追踪算法主要是围绕原始观测信号y与线性组合的残差r∈RM展开，残差主要描述没有被解释的测量值。在每次迭代中，从字典里选取一个跟残余分量差相关性的列： 

λk=argmink〈rk－1,λ〉λ‖λ‖2(3．4．27)
其中，λ为矩阵Φ的第λ列。一旦这个列被选中，就获得了一个更为逼近原始信号的结果。这是因为一个新的系数λk被增加到对原始信号逼近的索引集中。然后，进行如下更新： 

rk=rk－1－〈rk－1,λk〉λk‖λk‖2
xk=xk－1 〈rk－1,λk〉(3．4．28)

经过多次迭代，残差将变得越来越小，直到残差的范数小于某个预定的阈值，算法停止。上述算法有两个缺点: 一方面，它不能保证重建误差足够小； 另一方面，它常需要大量的循环次数才能逼近原始信号。这是因为如果将残差对已选择的元素进行垂直投影是非正交的，则每次迭代的结果只是次优而不是，所以收敛需要很多次迭代。(2) 正交匹配追踪算法在正交匹配追踪(OMP)算法中，每次循环时都把残差r投影到与所有已选定的列线性展开的正交子空间中，而不是将残差减去一个与其相关的字典中的矢量。由于残差r总是和已选取的列正交，所以相同的列在OMP中不会被选中两次，因而它的循环次数会明显减少。假设Φk表示矩阵Φ在第k个步骤中选择出的子矩阵(第k个列的选取过程与MP相同)，则

xk=argminx‖y－Φkx‖rk=y－Φkxk(3．4．29)

可以证明，如果原始的待测量信号是稀疏的，同时测量矩阵中每个元素都是从一个服从亚高斯分布的变量中随机选取的，则基于线性混叠的有限个测量值，可通过OMP以极大的概率重建出原始的稀疏信号。这个算法多需要K次循环即可收敛，其中K是原始信号中的非零个数。该算法可保证每次迭代的性，从而减少了迭代次数。但它每次迭代中仅选取一个元素来更新已选的元素集合，迭代的次数与稀疏度K或采样个数M密切相关。另外，每次迭代还需要额外的正交化运算，随着K或M的增加，运算时间也会大幅增加。OMP的运算复杂度为O(MNK)。(3) 分段匹配追踪算法对OMP的一种改进是分段正交匹配追踪(StOMP)。它与OMP在每次循环里仅从字典中选取一个元素不同，它每次选取一个元素集合，该集合的特点是残余分量与字典列的相关性均大于一定的阈值，而后残余分量将更新字典的列集合。StOMP的运算复杂度为O(MNlnN)，远比OMP小。(4) 子空间追踪算法子空间追踪(SP)算法也是对OMP的一种改进。它能在无噪声和有噪声时分别地进行精确的信号重建和逼近的信号重建。对任意测量矩阵，只要它满足约束等距特性，那么SP就能够从无噪声的测量矢量中精确地重建原始信号。在压缩感知信号重建算法中，重要的就是确定测量矢量y位于哪个子空间，且这些子空间是由测量矩阵中哪K个列矢量生成的。一旦确定了正确的子空间位置，通过应用子空间的伪逆运算就可以计算出信号的非零系数。SP的重要特点就是要寻找生成正确子空间的K个列矢量。该算法包含测量矩阵中的K个列矢量的列表，对子空间的初估计是测量矩阵中与实际信号y的K个相关的列。为了修正对子空间的初估计，SP会检测包含K个列矢量的子集，检测这个子空间是否可以很好地重建信号。假如重建信号与实际信号之间的残差没有达到算法的要求则需要更新这个列表。该算法会通过保留可靠的、丢弃不可靠的候选值，同时也加入相同数量的新候选值来更新子空间。更新的原则是新的子空间重建信号残差要小于更新前的子空间重建信号残差。该算法在一定条件下能够确保重建，且可以确保下一个迭代循环能够找到更好的子空间。4． 组合算法组合算法的基本思想是先对信号进行高度结构化采样(线性投影)，再借助组/群测试以快速获得信号的支撑集，实现精确重构。将重构问题表述成： 已知长度为N的矢量x中包含K个非零元素，xi≠0，但它们的位置分布未知。要求设计一种测试方法，通过少的测试次数确定非零元素所在的位置。简单实用的方法是把测试表示成一个二进制矩阵Φ，其元素i,j=1表示在第j次测试中，第i个元素被选用。如果输出信号与输入信号是一种线性关系，则重构目标稀疏矢量x的问题就可转化为标准的压缩感知稀疏重构问题。组合算法需要的测量次数较少，运算速度高，但是一般测量矩阵复杂，且不易确定对测量矩阵的约束条件，这为构建新的测量矩阵带来了困难。下面介绍两个简单的组合算法，均要求测量值没有噪声干扰。(1) 计数小略图法计数小略图法仅考虑非负信号。设H表示所有离散值函数h: {1,…,N}→{1,…,m}的集合，H是一个有限集合，其大小为mN。H中每一个函数h可以通过一个大小为m×N的二进制矩阵Φ(h)来表示，其中每一列都是一个二进制矢量，每一列仅在位置j=h(i)包含一个1。为了构建完整的采样矩阵Φ，可以根据均匀分布从H中独立选取d个函数h1,…,hd，把它们的二进制矩阵垂直堆叠成一个尺寸为M×N的矩阵，该矩阵即为Φ，且其每列均有d个1，其中M=md。针对已知任意信号x，可以获得线性测量值y=Φx。根据下面的两个特性，很容易得到对测量值的一个直观认识。首先，作为测量值矢量的y很容易借助母二进制函数h1,…,hd得到分组的形式； 其次，针对测量矢量y的第i个系数与母函数h有关，即

yi=∑j:h(j)=ixj(3．4．30)

换句话说，对一个固定的信号系数j，每个测量值yi都有函数h把xj以汇总的形式映射到相同的i上。信号重构的目标就是从这些汇总后的观察值yi中，恢复出原始的信号值xj。当原始信号是正数时，计数小略图法非常有用。已知测量值y和采样矩阵Φ，重建目标信号的第j个系数x′j可以由下式完成： 

x′j=minlyi: hl(j)=i(3．4．31)
直观地说，这就意味着重建目标信号的第j个系数x′j可以通过从所有可能有xj介入而形成的测量值中，找出其幅值小的一个观测值(作为x′j)来得到。该方法明显的特点是简单高效。(2) 计数中值略图法计数中值略图法在目标信号有可能为负数时也适用。这里不是取幅值小的一个观测值作为x′j，而是取中值。因为对一个普通的信号，其他的x对y的影响可能是正的也可能是负的，而中值有可能是原始信号的值。已知测量值y和采样矩阵Φ，重建目标信号的第j个系数x′j可以由下式完成： 

x′j=medianl yi: hl(j)=i(3．4．32)
5． 贝叶斯算法前述各种方法都认为信号是确定的或属于某个已知集合，即在已知信号模型的前提下讨论重构。贝叶斯压缩感知的基本思想是在未知信号模型的基础上考虑非确定性因素，即考虑一个概率分布已知的稀疏信号，从随机测量中重构符合此概率分布的信号。该类算法考虑了信号之间的时间相关性，所以对具有较强时间相关性的信号可提供比其他重构算法更高的重构精度。不过，由于在贝叶斯信号建模的框架下没有确切的“无失真”或“重建误差”的概念，所以下面介绍的各种算法与前述算法不同，并不能基于一定数量的测量值无失真地重建原始目标信号。(1) 相关向量机相关向量机(RVM)是一种贝叶斯学习方法。它能够产生稀疏的分类结果，其机理是从许多待选的基函数中选择少数几个，用它们的线性组合作为分类函数来实现分类。从压缩感知的角度出发，可将其视为一种确定稀疏信号中分量的方法，这种信号给一些基函数提供了不同的权重，而这些基函数就是测量矩阵Φ中的列向量。相关向量机使用了几个层次的先验概率模型。首先，假设x的每个分量都独立并服从均值为零而方差待定的高斯分布，即

p(xi|αi)=N(xi|0,α－1i)(3．4．33)

其中,N(x|m,σ2)为随机变量x服从均值为m、方差为σ2的高斯分布。进一步，有

p(x|α)=∏Ni=1N(xi|0,α－1i)(3．4．34)

其中，α=［α1,α2,…,αN］。然后，假设高斯分布中方差的逆(也就是α)也独立且服从参数为a、b的伽马分布

p(α|a,b)=∏Ni=1Gamma(αi|a,b)(3．4．35)

其中，Gamma(αi|a,b)=αa-1ie-aibΓ(a)-1ba，且Γ(a)=∫∞0ta-1e-tdt。可见，使用方差的逆可以控制赋予某个分量的权重。通过使用贝叶斯推理，可以得到在给定参数a和b的条件下，x的边缘分布是一个未标准化学生氏分布，即

p(xi|a,b)=∫p(xi|αi)p(αi|a,b)dαi=baΓa 122πΓab x2i2－a 12(3．4．36)

未标准化学生氏分布是由通过拉伸和平移服从标准化学生氏分布的随机变量得来的。标准化学生氏分布为

p(t|υ)=Γυ 12υπΓυ21 t22－υ 12(3．4．37)

随机变量r=μ st的分布就是未标准化学生氏分布： 

p(t|υ,μ,s)=Γυ 12sυπΓυ21 (r－μ)2υs2－υ 12(3．4．38)

可以看到，x的边缘分布是参数μ=0、υ=2a和s=(b/a)的未标准化学生氏分布。学生氏分布可以促进稀疏性的产生。如果假定误差服从均值为零方差为σ2的高斯分布，即

y=Φx εε~N(0,σ2)(3．4．39)

则给定测量值y，就可以通过贝叶斯推理结合使用各种迭代算法来获得x的后验概率分布。(2) 贝叶斯压缩感知可从RVM模型出发来考虑贝叶斯压缩感知(BCS)。对于给定观测值y，可以通过将y给定x的概率分布对x积分直接求出其边缘对数似然率，进而使用EM算法(见12．5．2小节)求解各个参数。由式(3．4．39)可以得到

p(y|x,α,σ2)=N(y－Φx,σ2I)(3．4．40)

其中，I为大小合适(这里是M×N)的单位矩阵。借助贝叶斯推理，可以得到

p(y|α,σ2)=∫p(y|x,σ2)p(x|α)dx
=(2π)－N/2σ2I ΦA－1ΦT－1/2exp－12yTσ2I ΦA－1ΦT－1y(3．4．41)

其中，A是一个对角矩阵，其对角线上的元素由α组成。在这个过程中，需要对一个N×N的矩阵求逆，所以算法复杂度是O(N2)。采用快速边缘似然率化的方法可以将复杂度降低到O(NM2)。它是一种渐进式的模型构造法，将基函数顺序地加入或删除，所以可极大地利用信号的稀疏性。贝叶斯压缩感知通过逐步迭代的方法逼近待重构稀疏信号的支撑集，它的一个优点是它可以对所估计的信号的每一个分量提供一个置信区间。这样就可帮助了解和判定： 是否该估计是准确的。例如，太大的置信区间表明这个估计可能不是十分可靠。理想情况下，希望得到一个估计值，同时其置信区间很小。3．5稀疏编码与字典学习稀疏编码与字典学习的结合曾与压缩感知并行发展，密切相关又互相影响。稀疏编码源自观察： 某类信号多是由少数几个基本原子的加权组合而构成。这正对应信号的稀疏表达。字典学习的目标就是要估计出给定目标信号的原子信号及其权重，从而实现对目标信号的稀疏表达。可以采用数学模型来描述字典学习。为简便，这里仅考虑实数信号。设yi∈RL是一个维度为L的矢量，用来表示一共N个信号中的第i个； A=［a1,…,aM］∈RL×N表示原子信号矩阵，其中第i列是维度为L的原子信号； wi∈RM是一个维度为M的矢量，用来表示构成矢量yi的原子信号的权重矢量。根据前面的假设，有

yi=AwTi εiwi0≤Ki=1,…,N(3．5．1)

其中，εi∈RL为来自某个概率分布的未知误差； |x|0为矢量x的L0范数； K为一个大于零的正整数。式(3．5．1)表达了多个重要的信息： (1) 信号是原子矢量的线性组合，所以这里使用了线性模型。线性模型的优点是简单、容易理解和操作。其缺点是不易描述具有非线性的数据。不过，这里并没有对信号所在的空间加以限制，所以如果要引入非线性成分，可将信号转换到某个特征给空间后再使用线性模型。(2) 非确定性是由误差项εi来体现的。这里并未假设误差来自何种概率分布，虽然常用的是高斯分布。如果希望原子信号是非相关的，且假设误差分布是均值为零、方差为单位矩阵的多维高斯分布，就可得到PCA模型。(3) 原子信号的权重矢量wi是K稀疏的，这是由|wi|0≤K表达的。这表明感兴趣的信号是由原子信号构成的。需要指出，稀疏性假设并非在字典学习中不可或缺。例如，盲源分离的典型方法，如独立成分分析和因素分析(FA)都是没有稀疏性假设的线性模型，也可被归到字典学习的范畴中。可将式(3．5．1)表达为矩阵形式

Y=AW Ewi0≤Ki=1,…,N(3．5．2)

其中，Y=［y1,…,yN］，W=［w1,…,wN］，E=［ε1,…,εN］。字典学习的目的是从数据矩阵Y中学习，即求解A和W。压缩感知的出发点是已知待测信号是稀疏的，需设计测量矩阵以得到测量值，再从测量值中推出待测信号。所以，在压缩感知的框架中已知测量矩阵和测量值，未知参数只有一个，即待测信号，而且待测信号只有一个样本。但在字典学习中，仅仅知道很多观测信号，而未知参数却有两个，即原子信号矩阵A及权重矩阵W，并且需要考虑多个样本。可见，字典学习更为困难，求解也更复杂。3．5．1字典学习与矩阵分解这里先忽略稀疏性假设，集中讨论字典学习。如果忽略误差，式(3．5．2)具有如下简单形式： 

Y≈AW(3．5．3)
其中，已知量是Y，即众多信号的观察值，需要计算的是A和W。所以，式(3．5．3)是一个矩阵乘式分解的问题。例如可以利用SVD将Y写成

Y=UDVT(3．5．4)

其中，U∈RL×L为一个包含正交单位列向量的矩阵，即(i,j=1,…,L)

uTiuj=1i=j0i≠j(3．5．5)

其中，ui为矩阵U的第i列。D∈RL×N为一个非主对角线上的元素为零、主对角线的元素全部或部分大于零的矩阵，称为矩阵Y的奇异值矩阵。因为在绝大多数情况下维数L不等于N，所以矩阵D不一定为方阵。在这种情况下，取D左上角开始的子方阵的对角线为其主对角线。因此，

如果i=j则dij≥0
如果i≠j则dij=0(3．5．6)

其中，dij为D中第i行第j列元素，dii就是矩阵Y的第i个奇异值，并且如果i>j，有dii≥djj，也就是主对角线上的奇异值按降序排列。Y∈RN×N同U一样是一个包含正交单位列向量的矩阵。将矩阵Y的秩记为R(Y)，它小于或等于min{L,N}，即R(Y) ≤min{L,N}。在SVD分解中，如果已知U和V都是满秩矩阵，则由R(Y)=R(UDVT)可知，奇异值矩阵D中的非零奇异值的个数对应矩阵Y的秩。设R(Y)=T，那么可以截掉SVD分解中各矩阵中冗余的列，得到稍微简洁的SVD分解矩阵，即U∈RL×T，D∈RT×T，并且V∈RN×T，通常称为
瘦SVD。比较式(3．5．3)和式(3．5．4)可见，如果令A=U，W=VDT，则可得到式(3．5．3)的字典学习问题的一个解。但实际上式(3．5．3)中是一个约等号，说明有误差存在。而式(3．5．4)的SVD解没有考虑误差，所以并不符合实际情况。解决的方法是保留若干个重要的奇异值，将不重要的奇异值设为零。这就得到
截断SVD(tSVD)。矩阵的秩决定了非零奇异值的个数。重写式(3．5．4)如下： 

Y=∑Ni=1diui?瘙經Ti(3．5．7)

其中，di为矩阵Y的第i个奇异值，且依次从大到小排列(当i>j时，di≥dj)。tSVD保留的几个奇异值(设保留了T个)，舍弃其余的奇异值来逼近矩阵Y： 

Y′=∑Ti=1diui?瘙經Ti(3．5．8)

所以，Y′只是一个估计值，它与原来矩阵之间的残差R=Y-Y′为

R=∑Ni=T 1diui?瘙經Ti(3．5．9)

所以在采用tSVD方法的字典学习方案中可将误差显式地表示出来，A=［u1,…,uN］，W=［d1?瘙經1,…,dT?瘙經T］。为确定式(3．5．9)的残差在原始信号矩阵Y中所占的比例，可借助矩阵的范数。
F范数是矩阵所有元素的平方和，所以

‖R‖2F=∑Ni=T 1d2i(3．5．10)‖Y‖2F=∑Ni=1d2i(3．5．11)这样，残差在原始信号矩阵Y中所占的比例为

‖R‖2F‖Y‖2F=∑Ni=T 1d2i/∑Ni=1d2i(3．5．12)
可见，在F范数衡量下的残差与原始信号之间的比例差别完全取决于原始信号奇异值平方的分布以及使用多少个(T)奇异值去重建信号。为确定T，可根据SVD与PCA之间的关系，即SVD的U矩阵对应PCA中的主分量，DVT就是数据在主分量上的投影值。这样就可看出，式(3．5．8)的tSVD逼近实际上是要选取若干个主分量来重构信号。所以，可以利用PCA中确定主分量个数的方法来确定tSVD中的T(即保留的奇异值的个数)。3．5．2非负矩阵分解tSVD的优化形式可用下式来表示(行是要优化的目标，下面两行是限定条件)： 

minA∈RL×M,W∈RM×N‖E‖2F
s．t．Y=AW EATA=IM(3．5．13)

其中，IM为M×M的单位矩阵。式(3．5．13)取数据矩阵Y的SVD分解在U矩阵中与T个奇异值相关的列作为原子信号矩阵A，并要求原子信号矩阵A正交。式(3．5．13)有两个问题。首先，tSVD是它的一个解，但由于没有限制W的形式，所以式(3．5．13)可能有无穷多个解。事实上，任何解的酉变换都是合法解，即如果假设A*和W*是一组解，H是一个M×M的酉矩阵(HTH=HHT=IM)，则A*H和W*H也是式(3．5．13)的解。其次，这里对字典信号必须正交的要求过于苛刻。从式(3．5．13)可见，要去掉原子信号必须正交的限制，只要简单去掉第3行就可。但这样可能导致解的空间太大以及平凡解的产生。所以需要对A或W或两者同时进行适当地限制。这样用来限定解空间的规则应满足两个条件： 一个是限定规则本身应具有物理意义； 另一个是限定后优化问题应可解，或者说其近似解可在有限时间内计算出来。字典学习的本质是矩阵分解。非负矩阵分解(NMF)是一种非线性的维数约减手段，可以满足上面两个条件。实际信号有物理意义，所以是非负的，生成这些信号的原子信号也应非负，权重矩阵要帮助构成信号所以也应非负。NMF的限定条件就是原子信号和权重矩阵必须都是非负的。NMF的优化形式类似于式(3．5．13)，可写为

minA∈RL×M,W∈RM×N‖E‖2F
s．t．Y=AW E
A≥0W≥0(3．5．14)

考虑到优化目标的多样性，还可写出更具有普适性的形式

minA∈RL×M,W∈RM×Nd(Y,AW)s．t．Y=AW E
A≥0W≥0(3．5．15)

其中，d(P,Q)为表示矩阵P和Q之间非相似度的函数。如果设

d(P,Q)=‖P－Q‖2F(3．5．16)

则式(3．5．15)退化为式(3．5．14)的形式。NMF的解空间一般还偏大，对它的改进常常是增加一些限制条件以进一步收缩解空间。例如，可以加入权重矩阵的稀疏性条件以实现稀疏非负矩阵分解： 

minA∈RL×M,W∈RM×Nd(Y,AW)s．t．Y=AW EA≥0W≥0‖W‖0≤K(3．5．17)

另外，对流形上的非负矩阵分解可以有

minA∈RD×M,W∈RM×Nd(Y,AW)
s．t．Y=AW EA≥0W≥0
ai∈Si=1,…,S(3．5．18)

其中，S为具有特定结构的流形。3．5．3端元提取端元提取也是一类字典学习方法，其两个限制条件为： 一个是权重矩阵非负； 另一个是权重矩阵每一列的和必须为1，即

yi=Awi εwi≥0wTiL=1(3．5．19)

其中，L为一个长度合适的全为1的列向量。将式(3．5．19)写成矩阵形式为

Y=AW EW≥0WTL=L(3．5．20)

一种典型的端元提取优化方法是迭代约束端元化(ICE)： 

minA∈RL×M,W∈RM×N‖E‖2F λ∑i≠j‖ai－aj‖22s．t．Y=AW EW≥0WTL=L(3．5．21)
其中，A为端元矩阵，其第i列，即ai是第i个端元，求和项表示两两不同端元之间的距离和； λ为正则参数，用以权衡数据重建误差与距离和。ICE的模型和优化问题与非负矩阵分解没有本质区别，但优化过程很不一样。ICE采用的是类似于坐标交替下降迭代的优化方法。在某一个迭代步骤t，固定一个未知量，如Wt，去求解另一个未知量，如At 1； 得到At 1后再固定At 1去求Wt 1。循环迭代就可得到终解。具体将ICE的优化问题简化为

minA∈RL×M,W∈RM×N‖Y－AW‖2F λTr(AHAT)s．t．W≥0WTL=L(3．5．22)

将E=Y-AW代入式(3．5．22)中，并且使用(H=1-LTL/M)

∑i≠j‖ai－aj‖22=Tr(AHAT)(3．5．23)

另定义

J(A,W)=‖Y－AW‖22 λTr(ATHA)(3．5．24)

如果在第t步迭代已得到At和Wt，则Wt 1可由(固定A)求解下式得到： 

Wt 1=argminWJ(At,W)
s．t．W≥0WTL=L(3．5．25)

式(3．5．25)是一个带线性限制条件的二次规划问题(QP)，有标准的算法。接下来，固定W以得到下一步的原子信号矩阵A： 

At 1=argminAJ(A,Wt 1)(3．5．26)

式(3．5．26)也是一个二次规划问题，且无约束条件，所以有直接的解析解： 

At 1=Y(Wt 2)TWt 1(Wt 1)T λH－1(3．5．27)

一般情况下，矩阵Wt 1(Wt 1)T λH是可逆的，因为H的秩为M-1。只有在某些情况如Wt 1为全零矩阵时才会出现Wt 1(Wt 1)T λH不可逆。即便在这种情况下，也可以引入一个小的扰动，即Wt 1(Wt 1)T λH εI(ε≥0，但接近0)取代原矩阵Wt 1(Wt 1)T λH以确保其可逆。所以，从一个初的原子矩阵A0出发，通过上述迭代过程，可以得到一组局部解。但该优化算法也存在类似非负矩阵分解优化算法的问题，ICE的优化目标同样是非凸性的，所以上述算法虽然可以保证收敛，但也可能收敛到局部解，并不能确保全局。另外，解还依赖于初始值，不同的初始值可能会导致不同的解。类似于对非负矩阵分解的改进(参见式(3．5．17)），也可以对式(3．5．21)进行相应的变形，以克服ICE的一些缺点或引入ICE中没有的性质。例如，可得到稀疏迭代约束端元化(SPICE)： 

minA∈RL×M,W∈RM×N‖E‖2F λ1∑i≠j‖ai－aj‖22 λ2‖W‖1
s．t．Y=AW EW=AW
WTL=L(3．5．28)

其中引入的是权重矩阵的稀疏性先验条件。3．5．4稀疏编码稀疏编码就是寻找数据的一种字典表达方式，要使得每个数据都可以表示成为少数几个原子信号的线性组合。直观地说，就是在字典学习中对权重矩阵引入稀疏性约束条件。在稀疏编码中权重矩阵称为稀疏表达矩阵，借助前面的优化问题表示方法，稀疏编码的模型和优化目标可写成

minA∈RL×M,W∈RM×N‖E‖p
s．t．Y=AW E
‖wi‖0≤Ki=1,…,N(3．5．29)

式(3．5．29)所表达的含义是找到用于表示数据Y的字典，使得使用该字典的每个数据的重建系数在一定误差允许范围内是K稀疏的。式(3．5．29)与压缩感知的经典优化问题有些相似之处，但有两点不同需指出： 一是压缩感知中的讨论针对一个信号的感知与重建； 二是压缩感知中的采样矩阵Φ对应稀疏编码中的矩阵A，且Φ已知，但在稀疏编码中矩阵A也是需要求解的目标之一。可见，稀疏编码在优化问题上求解的复杂度远超过压缩感知。1． 方向法方向法(MOD)解决的是式(3．5．29)及以下稍许不同的目标:

minA∈RL×M,W∈RM×N‖W‖0
s．t．Y=AW E
‖ei‖2≤εi=1,…,N(3．5．30)

其中，‖W‖0为矩阵W的L0范数，即矩阵W中非零元素的个数。方向法的本质是交替优化原子信号矩阵和权重矩阵，主要步骤有两个： (1) 稀疏编码阶段： 对i=1,…,N，使用匹配追踪算法以获取

wi=argminA‖yi－At－1w‖22s．t．‖w‖0≤K(3．5．31)

(2) 字典更新阶段： 使用下面的公式更新原子信号矩阵

At=argminA‖Y－AWt‖2F=YWt［Wt(Wt)T］－1(3．5．32)

2． 核奇异值分解
在MOD中，字典更新是通过对权重矩阵进行简单的伪逆计算来实现的，这样会使一些原子信号混入到其他原子信号中并产生影响，从而导致整个算法收敛过程较慢。核奇异值分解(KSVD)是为了消除原子信号之间的互相干扰而提出的。它的基本思想是逐个考查原子信号对数据拟合的贡献并逐个更新原子信号。考虑第j个原子信号aj，令Sj为包含原子信号aj中数据的索引集合，即

Sj={i|1≤i≤M,wji≠0}(3．5．33)
其中，wji为权重矩阵W的第j行第i列元素。因为W是稀疏的，所以并不是每个原子信号都对观测数据有贡献，或者说并不是每个数据都包含所有原子信号，而是多只有K个原子信号具有非零的权重系数。先来计算残差矩阵： 

Ej=Y－∑l≠jalwTl(3．5．34)

式(3．5．34)计算的是除aj外其他原子信号的拟合残差。引入记号ESj以表示矩阵Ej的列子矩阵，即由Ej中属于S的列所组成的矩阵。对aj和wj的更新由求解下式得到： 

(aj,wj)=argmina,w‖ESj－awT‖2F(3．5．35)

式(3．5．35)仍是一个矩阵分解问题，但比原始的矩阵分解问题简单得多，因为该式中的a和w都是矢量而非矩阵。所以，对式(3．5．35)可用经典的矩阵分解来求解。在KSVD中使用对矩阵ESj的秩为1的SVD分解，即tSVD

ESj≈uλ?瘙經T(3．5．36)
可见，u和λ?瘙經分别是a和w的解。如果K=1且限定权重矩阵的值只能取1或0，那么原始问题退化成一个标准的Kmeans聚类问题。类似于在每个Kmeans的迭代步骤中都计算K个子集(类)，这种带前述限制条件的KSVD的每个迭代步骤也是在寻找K个子矩阵(对应K个子集)。它的两个主要迭代步骤为(1) 稀疏编码阶段： 对i=1,…,N，使用匹配追踪算法以获取

wi=argminA‖yi－At－1w‖22s．t．‖w‖0≤K(3．5．37)

的近似解，这样得到Wt。(2) 字典更新阶段： 使用下面公式依次更新原子信号矩阵A的第j个原子信号aj(j=1,…,M)。先计算残差矩阵

Ej=Y－∑l≠jalwTl(3．5．38)

而矩阵ESj的秩为1的tSVD分解为

ESj≈uλ?瘙經T(3．5．39)
aj=u，且权重向量wj=λ?瘙經。可见，稀疏编码与聚类分析有很大的相似性，且与子空间分析(也称子空间学习)密切相关。3．6压缩感知的成像应用压缩感知已得到了许多应用，下面仅举两个成像方面的例子。3．6．1单像素相机单像素相机的设计是使压缩感知得到广泛关注的一个重要事件。它成像灵活，光电转换效率高，大大减少了对高复杂度、高代价光探测器的要求。它的成像流程如图3．6．1所示。

图3．6．1单像素相机成像流程

利用光学透镜将场景中得到光源照射的目标投影到数字微镜器(DMD)上。这是一种借助大量的微小镜片来反射入射光而实现光调制的器件。微镜阵列中的每个单元都可借助电压信号控制以分别进行±12°的机械翻转，如此就可将入射光分别进行对称角度的反射或完全吸收而不输出。这样就构成了一个由1和0组成的随机测量矩阵。以对称角度反射出来的光被光敏二极管(目前常用的快速、敏感、低价高效的单像素传感器，在低光照时也有使用血崩二极管的)所接收，其电压随反射光强度发生变化。量化后可给出一个测量值yi，其中每次DMD的随机测量模式对应测量矩阵中的一行i，此时如果将输入图像看成一个矢量x，则该次测量的结果为yi=ix。将此投影操作重复M次，则通过M次随机配置DMD上每个微镜的翻转角度，就可获得M个测量结果，得到y=Φx。根据总变分重构法(可用DSP实现)，就可用远小于原始场景图像像素的M个测量值重构图像(其分辨率与微镜阵列的分辨率相同)。这相当于在图像采集的过程中实现了对图像数据的压缩。

例3．6．1单像素相机成像效果单像素相机成像的效果目前还离普通CCD相机成像的效果有一定的距离。图3．6．2给出一组示例。图(a)是对一张黑纸上的白色字母R的成像效果，像素个数为256×256； 图(b)是一个用单像素相机成像的效果，此时M为像素个数的16%(进行了11000次测量)； 图(c)是另一个用单像素相机成像的效果，此时M为像素个数的2%(进行了1300次测量)。

图3．6．2单像素相机成像效果示例

由图可见，虽然测量数量有所减少，但质量还不能相比。另外，机械翻转微镜需要一定的时间，所以为获得足够多的测量数量的成像时间比较长(以分钟为单位)。事实上，在可见光范围内，用单像素相机成像的成本比一般CCD相机或CMOS相机要高。由于可见光谱与硅材料的光电响应区域一致，所以CCD或CMOS器件的集成度高且价格低。但在其他光谱范围，例如红外谱段，单像素相机就比较有优势。由于红外谱段的探测器件很昂贵，单像素相机就可与其竞争了。□3．6．2压缩感知磁共振成像磁共振成像是一种借助扫描并进行投影重建来获取图像的方法(参见上册第8章)，在医学中得到广泛应用。磁共振成像可获取人体内部的信息，且对人体无损伤，但其中的扫描过程导致采集图像需要大量的时间，不仅增加了病人的不适感，而且病人的生理运动造成的运动伪影也会给临床诊断带来较大的负面效应。因此，缩短成像时间、提高成像效率和减少图像伪影得到很多关注。利用压缩感知的磁共振成像的基本思路： 首先对图像采用离散傅里叶标准正交基进行稀疏表达，其次对得到的K空间数据进行随机欠采样，后通过非线性重构算法重建出图像。整个流程如图3．6．3所示。

图3．6．3压缩感知磁共振成像流程

具体描述如下： (1) 考虑一幅ND图像x在Ψ={Ψ1,…,ΨN}下具有稀疏性，则

x=∑Ki=1θiΨN=ΨΘ(3．6．1)

其中，Θ=［θ1,…,θN］T(KN)为x在稀疏变换Ψ中的非零系数。(2) 借助F∈RM×N(MN)将图像x投影到低维空间，得到M维的测量值y∈RM： 

y=Fx=FΨΘ(3．6．2)

其中，F为傅里叶变换欠采样矩阵。(3) 图像x可由K空间的测量值y通过求解约束优化问题来精确重构： 

min‖Ψx‖1s．t．‖Fx－y‖2
式(3．6．3)表示在用不等式约束K空间数据的一致性条件下(ε为测量值重构的保真度)通过稀疏变换Ψ对x进行稀疏表达。

例3．6．2压缩感知磁共振成像效果
图3．6．4给出一些压缩感知磁共振成像的效果示例。图像为T1加权脑图像，每幅图像的分辨率为384×324，含有加性复数高斯噪声，信噪比为25dB。其中，左边3幅图是采用基于压缩感知的总变分重构法得到的结果，右边3幅图是采用基于压缩感知的凸优化重构法(使用了加权L1范数)得到的结果。每3幅图中，从左向右，测量数分别是原始像素数的1/4，1/6和1/8(都对应欠采样)。换句话说，成像的加速倍率(反比于测量数)分别为4，6，8。

图3．6．4压缩感知磁共振成像效果示例

由图3．6．4可见，当加速倍率为6和8时，利用总变分重构法得到的结果中解剖结构比较模糊且存在较多块状伪影。利用凸优化重构法得到的结果有所改善，但上述问题仍然存在。□在利用压缩感知的磁共振成像中，扫描仪器采集的并不是原始图像像素，而是由全局傅里叶变换得到的频域图像，每一个频域像素都是时域像素的线性组合，即频域图像包含了原始图像的所有信息。因此，保留部分重要的采集数据并不会导致原始图像信息的缺失。然后，通过仅利用K空间的部分数据就可成功地重构出原始图像。如此，不但加快了成像速度，而且将极大地减少扫描时间并提高病人的舒适性。总结和复习为更好地学习，下面对各小节给予概括小结并提供一些进一步的参考资料； 另外给出一些思考题和练习题以帮助复习(文后对加星号的题目还提供了解答)。1． 各节小结和文献介绍3．1节概括给出了压缩感知的基本框架，相关的内容还可参见［卢2012］、［万2013］、［尹2013］、［荆2015］、［闫2015］等。3．2节介绍了稀疏表达的一些基本知识，可与3．5节结合学习。有关稀疏表达的一个应用可见［Liu 2014］。3．3节分析了测量矩阵及其特性，相关讨论在很多书籍中都有介绍，如［李2015］。3．4节介绍了一些典型的重构算法，凸优化算法还包括： ①Lp重构模型，用Lp(0
31有人将压缩感知的基本流程图用图题31表示，讨论其与图3．1．1的相似和不同处。

图题31

32什么样的信号可认为是稀疏信号？举3个实例。*
33对比传统的信息获取和压缩感知信息获取。(1) 在传统的信息获取中压缩的是数据，而在压缩感知中，压缩的是什么？(2) 在传统的信息获取中只需要解压缩，而在压缩感知中需要重构步骤，为什么？

34试画出范数3/2与拟范数1/4在R2中的单位圆。

35试讨论使用范数3/2与拟范数1/4在描述逼近误差时的不同表现。

36考虑对周期信号y=sin(0．25πi)在i=0,…,16进行采样得到的信号，(1) 画出对其进行傅里叶变换的频谱； (2) 画出对其进行小波变换的频谱； (3) 比较两个频谱，哪个更加稀疏？为什么？

37试证明： 如果(Φ,Δ)满足式(3．3．4)，则矩阵Φ满足2K阶零空间特性。

38对比列出文中介绍的各类重构算法的适用场合、优缺点。还可扩展到其他文献中的算法。

39试证明式(3．4．7)的解x′满足式(3．4．8)。

310非负矩阵分解对原子信号和权重矩阵有什么限定？试举例解释其物理意义。*
311压缩感知的目标和稀疏编码的目标有什么不同？哪一个的要求更高些？

312调查一下，压缩感知除在成像方面外，还在哪些领域得到了应用，介绍几个示例。