翻译 压缩感知

压缩感知1、范围香浓/尼奎特斯采样定理告诉我们当我们采集一个信号，为了避免丢失信息，我们必须采集两倍于原信号的频率。在很多应用领域包括数字成像和摄影机，尼奎特斯率对于它们太高了，我们会得到非常多的采样样品，并旦为了储存和传输必须将它们压缩。在另外的一些领域例如成像系统（医学扫描仪，雷达）和高速模数转换器，在超出当代最先进的水平下增加采样频率或密度的成本是非常高昂的。在本次讲座中，我们将会了解到用来解决这些问题的新技术一一压缩感知。我们会一种更具通用性的最优化的线性耦合测量方法来获取一定的远远低于尼奎特斯率信号来取代传统采样和重构方法。2、相关性这里提出的想法可以用来举例说明数据采集，线性代数，基础扩展，逆问题，压缩，降维和进程优化之间的关联，从本科生或研究生的数字信号处理到统计数学和应用数学。3、先决条件理解和讲解本材料的预备知识是线性代数，基础优化和基础概率。4、问题陈述尼奎特斯率采样通过利用信号的有限带宽来完整的描述信号。我们的目标是通过信号的可压缩性来减少所需的测量量来描述完整信号。这要求我们不用点采样的方法而用更普遍的线性函数的信号采集。假设一个实数域有限长一维离散时间的信号X,我们把它看做RN中的n*1个列向量,睥中的元素为x［n］,n=l,2,...,N。我们把一个图像或更高维度的数据向量化为一个长的一维向量中。任何一个信号在rn中可以表示为基础的n*i向量｛巾』i?］。为简单起见，假设基础是正交的。通过把矩阵｛。i｝转换形成N*N的基矩阵W:=［叩1饵项...I%］，我们可以把任何信号X表示为：X=Zi=lS］电。rX=Us（1）其中s是N*1列的加权系数向量si=<X,电>=甲以，其中.7表示转置。亳无疑问，X和S是同一信号的等价表示，X表示时域，S表示W域。我们把目光集中于具有稀疏性的信号，其中X是基向量的K线性组合且K«N。就是说在（1）S,中只有K个非零值和（N-K）个零值。实际上，稀疏性使很多自然信号和人造信号具有可压缩性，这就存在表现在（1）中的W，有很少的小系数和很多的大系数。可压缩的信号可以近似表示为K-稀疏值；这是转换编码的基础。例如，JPEG和JPEG-2000压缩标准就是自然图像可以用离散余弦变换和小波变换压缩。音频信号和许多通信信号在局部傅里叶变换基中是可压缩的。转换编码在数据收集系统中扮演了中心角色,例如数码相机采样数量非常高但信号是可压缩的。在这个框架中，我们获取完整的N-采样信号X：通过S=W『X计算完整的转换系数伉｝：查找K个最大系数，舍弃（N-K）个最小系数；并且将这K个值编码定位这些最大系数。（在实际中，我们也把这些值和位置转化为二进制编码。）不幸的是，这种采样然后压缩的框架有三个自身缺陷：第一，即使所需的K很少，我们也必须开始时采集大量潜在的N点。第二，即使只需要K个转置系数，编码器也必须计算所有的N个转置系数伉｝°第三，编码器要面对大系数定位编码的开销。作为一种选择，我们将学习一种更为普遍的数据收集方法，将信号直接用压缩表示而不

必经过采样N点的中间步骤。运用一种更为普遍的线性测量过程计算X和收集向量沽｝中M<N个内积，设h=<X,兮〉。将测量值弘转置成为M*1的向量y并且把测量向量作为行形成一个M*N的矩阵①，并将其代入（1）式，得到：Y=（Dx=（D,4Js=0s（2）其中0：=（DW是一个M*N的矩阵。图1（a）是（2）的描述。注意测量过程是非适应性的。就是说（D不取决于信号X。接下来我们的目标是设计一个测量矩阵（D和一个基于K—稀疏旦可压缩信号的重构算法，只要获得M@K或者稍多一点的测量值或者与传统变换编码一样多的测量值。我们的方法是基于最近的压缩感知理论。5、解决方法解决方法包括两步。第一步我们设计一个稳定的测量矩阵（D来确保任何K-稀疏可压缩信号的显著特征在维度从X*减少到时不被破坏。第二步，我们开发一个将测量值V恢复成x的重构算法。首先，我们先关注确切的K-稀疏信号。5.1稳定的测量矩阵首先，我们设计一个依靠矩阵0的数据收集系统的测量方法。我们的目标是从可以稳固的重构长度N的信号X或者在W中相等的稀疏向量中获得M个测量值。很明显，如果测量过程中破坏了x中的信息，将不能重构为原信号。不幸的是，通常情况下会是这样：在测量过程中矩阵W和（D是线性有限的，在（2）中通过y求解s是一个线性代数问题，由于M<N,方程的个数少于未知量，用通常的方法不适合解这个问题。然而s的K-稀疏带给我们解决方法。在这种情况下测量向量是0的列K的线性组合,Sj知（见图1（b））°如果我们知道先验条目s中有K个非零值，那么我们可以组成一个M*K的线性方程来求解这些非零值，其中已知方程M等于或大于未知数K。一个确保矩阵M*K状态良好的充分必要条件是对于任意具有相同K个非零值的向量V满足llQv||2

llv||2<1+0(3)总之，矩阵。必须保证K-llQv||2

llv||2<1+0(3)当然，在实际中我们并不需要知道s中K-稀疏的位置。有趣的是，K-稀疏和可压缩信号s有稳定的逆的充分条件是。符合（3）o这就是为什么称之为有限等距约束。一种可选的保持稳定的方法是确保测量矩阵（D与W是不相关的，向量｛甲丁｝不能稀疏表示向量｛电｝,反之亦然。典型的例子是：傅里叶的不确定性立即屈服于这种不相关性。所以，给定一个稀疏基W，我们怎样构建一个测量矩阵①使0=（D^满足有限等距约束。不幸的是，仅仅验证0满足有限等距约束是一个复杂的组合问题；我们必须验证长度为N的向量v中K个非零值所有的（修）种可能性。A在压缩感知中，我们通过选择随机矩阵①来回避这个问题。例如，我们从均值为零方差为1/N的高斯矩阵（白噪声）随机抽取相互独立均匀分布的元素％,/然后测量值y仅仅是M中x中元素的线性随机组合。一个高斯矩阵（D有两有趣有用的特点。第一，（D有很高的概率与W=l不相关，因为它充分地利用N个脉冲表示①的每一行。更严格地说，运用浓缩的测量参数，如果M^cKlog(N/K)旦c是一个小常量则一个M*N的相互独立均匀分布的高斯矩阵0=(DI=(D满足有限等距约束。因此我们可以认为有很高的概率从一个满足M>cKlog(N/K)«N的随机高斯测量矩阵回复出一个长度为N的K-稀疏可压缩信号。第二，由于高斯分布矩阵W的互相独立均匀分布的特性，不论如何选取稀疏矩阵W，矩阵O=(DW也是高斯分布的。因此随机选取的高斯测量矩阵(D对于每个可能的W都有很高的概率严格意义上普遍让O=(DW满足有限等距约束。在其他情况下，随机值±1的德拉马赫矩阵也满足有限等距约束和普适性。5.2信号重构算法有限等距约束性质提供了理论上通过y中M个测量值完整地描述一个K-稀疏可压缩信号，但并没有告诉我们怎么恢复它。信号重构的步骤必须采用测量值y,随机测量矩阵0(或生产它的随机种子)，以及稀疏矩阵W来再生出长度为N的信号x,或者其等价的稀疏系数向量s。我们将再次关注K-稀疏信号。由于(2)中M<N,因此有非常多的s，满足Os^y；他们都依赖于R”中(N-M)维超平面H:=N(0)+s相应的是0对于零空间N(€>)化为稀疏解so这是因为如果0s=y那么对于任何零空间的向量v都有。(s+!•)=y°一次，我们的目标是在零空间里找到信号的稀疏系数向量s。定义向量s的范数；为(||s||p)P=£；L|Sj|P。当p=0时，我们计算s中非零值的数量得到范数Z。。因此K-稀疏向量具有I。范数K。最小范数侃重构：经典的解决这种类型的反问题的方法是最小二乘法；既在被转化为零空间H中选择具有最小范数侃的向量：s'argmin|Is'lb例如0sz=y(4)甚至有一个更方便的闭型解s*=0r(€>®r)Ty。但不幸的是当向量我们寻找的向量s是K-稀疏的，最小的侃总是不能被发现。相反我们找到的是非稀疏的厂(详见6.1节)最小范数1。重构：由于范数侃在(4)中并不能反映信号的稀疏性，一种合理的选择是寻找被转化为零空间H的最稀疏向量：s"=argmin||s'||o例如0sr=y(5)由上式知只要有M=K+1个相互独立均匀分布的高斯测量值，就有很高的概率最优化地恢复出一个K-稀疏信号。但不幸的是解(5)不仅在数学上不稳定而旦还是一个NP完全问题，它要求我们详尽地列举出s中非零值位置的所有(^)种可能的组合。最小范数九重构：压缩感知的惊奇之处在于我们可以从M^cKlog(N/K)个相互独立均匀分布的高斯测量值中正确地重构出K-稀疏向量并且通过九高概率的最优化近似压缩向量。s'argmin||s'||i例如Os'=y(6)这是一个被成为基追踪的减少到线性问题的凸优化问题，其计算复杂度大概是0(N3)。总而言之，一个压缩感知数据收集系统由基于(D随机测量值组成，通过线性问题重构得到信号X。6讨论6.1几何解释压缩感知问题在空间睥中的几何结构可•以帮助我们形象的理解为什么九的重构能成功而侃却会失败。首先，要注意在空间RV中的所有K-稀疏向量s是由在坐标轴上对其的所有K维超空间组成的高度非线性空间(见图2(a))°因此在空间A”中稀疏向量十分靠近坐标轴。为形象得理解为什么Z2的重构会失败，注意被转化为零空间H=N(0)+s是(N-M)维,并且由于矩阵。的随机性H被定向成了一个随机角度。观察图2(b)，但要注意在实际中N,M,K>>3,你需要将直觉外推到高维度中。(4)中侃的极小变化量厂在H上是一个非常靠近原点的点。我们可以找到这个点通过在超球面(侃球)接触H前放大它。由于H方向的随机性，最接近的点厂有很高概率远离坐标轴，因此它可能既不稀疏也不接近正确答案s。与球形成鲜明对比的是，。球在图2(c)是沿着坐标轴对齐的点形成的尖锐形状(并且会随着维度N的增长变得更加尖锐)。因此当我们放大九球时，它会第一时间在靠近坐标轴的点上触碰到转化为零空间的H,这个点恰恰就是稀疏向量S的位置。6.2模拟信号当我们集中于离散时间信号X上时，压缩感知也能应用于模拟信号X(t),其稀疏性可用从一些连续基或字典{乳(t)}?Li中的N种可能元素表示。当每个弭(t)拥有大大带宽(或一个高的尼奎斯特频率)时信号x(t)只有K自由度，并且我们可以用以上理论以一个低于尼奎斯特定律的值去测量这个信号。一给模拟压缩感知系统的实例被称为“模拟-信息”的采集器在【7】中给出。7实例想一想不先收集N个像素值而收集M随机线性测量值的单像素压缩数字相机。期待图形的入射光并未集中在CCD或是CMOS采样组上，而是反射到由N个小镜子组成的数字微镜装置上(数字微镜装置多用于电脑放映机和投影仪上)。反射光稍后由第二个透镜收集并聚集在一个单光电二极管上(单像素)。每个镜子可■以独立的调整是朝向光电二极管或者远离光电二极管。每个测量值为用如下方法获得：随机数字发生器以伪随机序列0/1设置镜子朝向来创造测量向量<p广光电二极管的电压等于力，就是甲/和期待图形x的内积。这个过程充分M次来获得所有y中的值。图3(b)和(c)以次图像和目标物体阐明单像素照相机样机使用比重构信号所需少％60的随机测量值获