第1章压缩感知概述
本章主要概述压缩感知的基本概念、相关应用以及发展历史，并简要介绍本书的内容安排，目的是让读者对压缩感知理论与应用形成一个系统图景.
1.1基本概念
压缩感知[1-2]兴起于逆问题理论[3-5].传统的正问题可表述为由输入的原因和模型来求结果；而逆问题的任务是由己知的部分结果确定模型或反求原因.逆问题具有广泛而重要的应用背景，在地球物理、信号处理、材料科学、遥感技术和工业控制等众多的科学技术领域中大量涌现，吸引了国内外众多学者的持续研宄.一般而言，模型的复杂度直接决定了逆问题的复杂度，尽管逆问题涉及的模型多种多样，但是线性模型始终占据着主导位置.关于线性模型的逆问题一般可转换为求解线性系统，其中欠定线性系统的求解*具难度，也往往具有吸引力.压缩感知理论为欠定线性系统的求解提供了新思路.
1.1.1欠定线性系统
工程技术领域中的诸多模型都可表述为线性系统，例如采样系统、图像降质、信号传输等.假设线性系统对应的测量矩阵为，原始信号与获得的观测信号分别为与，则通过线性系统获得观测信号的过程可建模为
（1.1.1)
求解上述线性系统即在己知测量矩阵A的条件下从观测信号y中重构原始信号x.当M=N，且A为满秩矩阵时，方程（1.1.1)存在唯一解，此时系统为适定线性系统；当M<N时，系统为欠定线性系统，此时若y未位于由A的列向量张成的子空间，方程（1.1.1)无解，否则存在无穷多解.为了便于讨论，无特别说明时一般假设A为列满秩矩阵，即A的列向量可张成空间CM，此时欠定线性系统存在无穷多解.换言之，在无额外信息的情况下，欠定线性系统不能获得其唯一解.
事实上在工程技术领域中的很多问题都可归纳为求解欠定线性系统.例如图像盲复原问题，其正过程可表述为原始图像x经过图像模糊A生成降质图像y，图像复原即从降质图像y重构原始图像x.通常而言A是欠定的，在无额外信息的情况下存在无穷多个图像满足正过程模型，如何重构原始图像x呢？通过大量研宄发现了一个“奇怪”的现象：尽管欠定线性系统（1.1.1)存在无穷多解，但是在某些条件下确实能够从观测信号y中重构原始信号x，即获得（1.1.1)的唯一解.压缩感知便是对该现象做出的理论解释，其重点回答了三个问题：其一，在哪些条件下欠定线性系统存在唯一解？其二，在满足这些条件时如何获得欠定线性系统的唯一解？其三，如何保证获得的唯一解就是我们所“期望”的解（真值）？后续三个小节的内容分别针对上述三个问题进行阐述.
1.1.2稀疏性
稀疏性是压缩感知回答第一个问题的核心，即当原始信号x满足稀疏性条件时欠定线性系统（1.1.1)存在唯一解，下面通过类比初步分析其中原理.将欠定线性系统转换为适定线性系统是系统存在唯一解的关键，正则化通过缩减欠定线性系统的解空间可实现这一目标.正则化的基本思路是选择一函数J(x)用以评估x与真值的符合度，设函数值越小符合度越高，则通过正则化可建立优化问题：
(1.1.2)
其中，函数J(x)表示解的先验信息，决定了解的性质.例如，令
(1.1.3)
表示解能量极小，则通过Lagrange乘子法可知优化问题（1.1.2)具有解：
(1.1.4)
此外，在图像处理中还经常用到图像光滑性、分段光滑性等先验信息.正则化正是利用解的先验信息将欠定线性系统转换为适定线性系统.
稀疏性作为一类更广泛的先验信息，是压缩感知理论与应用的基础与前提.若某信号的大部分成分为零，则称该信号为稀疏信号；若某信号可以由稀疏信号很好地逼近，则称该信号为可压缩信号.事实上，稀疏信号与可压缩信号通常并不做严格区分，都具有稀疏性，且若某信号经过变换后是稀疏信号或可压缩信号，依然称该信号具有稀疏性.自然界中可压缩信号广泛存在，这也是为什么JPEG、MPEG、MP3等国际信号压缩标准能够成功应用的原因.例如，国际图像压缩标准JPEG的核心是离散余弦变换，通过保留图像具有较大绝对值的离散余弦变换系数即可实现图像的压缩，如图1.1.1所示，仅保留了前10%具有*大绝对值的离散余弦变换系数，可以发现原始图像与压缩图像在视觉效果上并没有显著区别，这便表明该图像在离散余弦域具有稀疏性.
既然自然界中稀疏性是普遍存在的，则传统信息获得的方式就存在一个天然的矛盾.例如在天基光学成像系统中，设探测器阵列是256×256的，则一次曝光获得遥感图像大小为256×256，为了便于传输与存储，一般利用图像压缩标准对图像进行压缩，舍去大部分变换系数，此时自然产生一个疑问：是否可以直接获取压缩图像？一方面可以减小成像能源、时间等成本，另一方面避免图像压缩环节，提升信息处理效率.事实上该问题的答案是肯定的，这既是提出压缩感知理论的初衷，也是稀疏性作为压缩感知理论的基础与前提的关键.换言之，以压缩的方式去感知可压缩信息，这正是压缩感知的首要目标.
为了更直观地解释利用稀疏性可以求解欠定线性系统这一事实，下面从解方程的视角进一步阐述该原理.事实上，线性系统（1.1.1)可以展开成方程组的形式，其中仅有x为未知向量，当x中未知元素个数大于方程的个数时，方程组有无穷多个解（没有解的情况暂不考虑），线性系统显然是欠定的.若X本身具有稀疏性，且未知非零元素的个数为正整数s，其中0≦s<N，此时X中真正的未知量包括s个非零元素的值以及其相应的位置，因此共2s个未知数.当x非常稀疏时，即2s≧M，此时尽管有M<N，但方程组的个数已经大于事实上的未知数的个数，因此方程存在唯一解.这便解释了为什么欠定线性系统在稀疏性的条件下依然有可能存在唯一解.同时注意到非零元素的位置未知与非零元素的值未知“地位”并不相同，位置未知对应的解空间是一个非线性集合，求解位置的难度要远远大于求解值的难度，因此上述阐述仅是一个直观的解释，并非严格的数学证明.
1.1.3稀疏重构
1.1.2节针对压缩感知所回答的第一个问题进行了阐述，本节重点讨论第二个问题，即在满足稀疏性条件时如何获得欠定线性系统的唯一解？由1.1.2节讨论可知，由稀疏性获得欠定线性系统的唯一解属于非线性问题，不能通过简单的线性重构解决该问题.因此本节重点介绍稀疏重构的相关概念与基本原理，主要包括稀疏重构模型与稀疏重构算法两部分.
由优化问题（1.1.2)可知，正则化是求解欠定线性系统的基本途径与思路，而不同的先验信息代表着不同的解的性质，稀疏性是压缩感知采用的先验信息，寻求能度量稀疏性的函数J(x)时建立稀疏重构模型的基础.由向量见0范数的定义可知，彳。范数能够精确地表示向量的稀疏程度，即
(1.1.5)
其中，表示集合中元素的个数.若令，则稀疏重构模型可表示为
(1.1.6)
该模型可理解为寻找符合观测数据y=Ax的*稀疏的解.然而*小化t。范数的优化问题（1.1.6)是一个非确定多项式难度（NP-hard)问题，因此一般将其松弛为*小化A范数的优化问题：
(1.1.7)
其中，向量的t范数定义为
(1.1.8)
这里需要注意两个问题，一是在什么情况下优化问题（1.1.6)能够松弛为（1.1.7)，该问题涉及测量矩阵A的可重构条件分析，在1.1.4节详细讨论；二是松弛为优化问题（1.1.7)能够带来哪些优势.注意到向量A范数不仅能够度量向量的稀疏性，还是一个凸函数，由凸分析可知，该优化问题可以通过凸优化算法精确求解.当然，A范数带来凸优化算法的代价便是对稀疏性的度量有一定的“松弛”.为了更好地平衡稀疏性与算法复杂度，提出了基于向量t范数的优化模型：
(1.1.9)
其中，0<q≦1，向量tq范数定义为
(1110)
尽管后续提出了更多关于稀疏性的度量函数，但基本都是上述目标函数的变形或改进.
关于稀疏重构模型有三个注意事项：
(1)当q≧1时，表达式（1.1.10)称为向量的范数是符合范数定义的，但是表达式（1.1.5)以及当0<g<1时的表达式（1.1.10)严格说来并非范数，因为范数定义中的三角不等式不再成立，但是考虑到领域习惯，依然称其为范数.
(2)上述稀疏重构模型中的目标函数都是针对x本身具有稀疏性而言的，若x在某一变换T下具有稀疏性，即x=Ts，且s具有稀疏性，则以（1.1.9)为例，稀疏重构模型可以表示为
(1.1.11)
若上述优化问题的解为玉，则x的估计值为x=Ts.
(3)上述稀疏重构模型中的约束条件皆为等式约束，即观测过程不含任何误差和噪声，事实上这是理想状态，观测一般都会受到误差或噪声的干扰，因此等式约束一般松弛为关于f.2范数的不等式约束，即
(1.1.12)
其中，s为较小的正常数.
针对上述稀疏重构模型，己经提出多种稀疏重构算法，主要包括求解*小化范数优化问题（1.1.6)的贪婪类算法、求解*小化A范数优化问题（1.1.7)的凸优化类算法、求解*小化范数优化问题（1.1.10)的非凸优化类算法，以及一些基于特殊测量矩阵形式的算法，具体如图1.1.2所示.求解*小化范数优化问题（1.1.6)的贪婪类算法有：匹配追踪算法、正交匹配追踪算法、正则化正交匹配追踪算法、分段式正交匹配追踪算法、压缩感知匹配追踪算法、子空间追踪算法等，该类算法针对组合优化问题提出，基本原理就是通过迭代的方式寻找稀疏向量的支撑集，并且使用受限支撑*小二乘估计来重构信号.算法的复杂度大多是由找到正确支撑集所需要的迭代次数决定的，算法计算速度快但是需要的测量数据多且精度低.求解*小化f'范数优化问题（1.1.7)的凸优化类算法主要针对基追踪模型，实现算法有单纯形、内点法、不动点延拓、梯度投影稀疏重构算法等.凸优化算法稀疏重构精度较高，但是当问题的规模较大时，算法的复杂度非常高，重构时间变长且硬件实现较困难.求解*小化fq范数优化问题（1.1.10)的非凸优化类算法主要有迭代加权(范数、加权*小二乘算法等，其基本原理是利用性质较好的加权函数逼近范数，进而求解关于加权函数的优化问题，利用该问题的解逼近*小化范数优化问题的解.该稀疏优化过程可用贝叶斯估计进行解释，但容易陷入局部极小值，且不能一致地优于A范数凸优化的结果.
下面基于稀疏重构模型与稀疏重构算法给出一个算例.如图1.1.3所示，原始信号，其中非零元素共有8个，因此信号本身具有稀疏性.测量矩阵，为一高斯随机矩阵，通过观测过程y=Ax获得观测信号，即采样数据量为原信号维度的一半，此时数据压缩率为0.5.通过稀疏重构模型(1.1.6)及子空间追踪算法获得的重构信号，由图1.1.3可知重构信号与原始信号几乎完全重合，这既验证了稀疏重构模型与稀疏重构算法的可行性，也体现了压缩感知的优势.
展开
