压缩感知理论与应用(附重建算法详述)

压缩感知理论与应用Compressedsensing:theoremandApplications一.压缩感知背景知识二.压缩感知理论三.压缩感知重建方法四.压缩感知应用内容概览一.压缩感知背景知识Nyquist-Shannon采样定理1928年由美国电信工程师H.奈奎斯特首先提出1933年由苏联工程师科捷利尼科夫首次用公式严格地表述这一定理1949年信息论的创始人香农对该定理加以明确地说明并正式作为定理引用，因此在许多文献中又称为香农采样定理HarryNyquistClaudeShannon插值重建数字信号的获取----Nyquist-Shannon采样定理信号采样非带限信号香农定理的数学表示香农采样定理后采样理论的发展Nyquist-Shannon采样定理局限性问题1:真实信号没有真正带限的；问题2:理想的低通滤波器不存在；获取的大量数字信号为处理、存储、传输的软硬件增加了很多负担高分辨率大量的传感器图像数据库，照相阵列，分布式无线传感网越来越多的成像形式X-Ray，GammaRay,PET，MRI,红外，超声波，毫米波SAR成像海量的数据问题3:当信号的带宽过宽时，采样率过高难于实现限制了超宽带通信和超宽带雷达的发展；限制医学图像成像的发展，比如MRI；等等。多种成像形式采样压缩传输/存储NKx小波系数局部放大大量采样数据有无必要性？1M25K项系数近似原始图像近似后的图像2004~2006，ECandes（加州理工大学）D.Donoho(斯坦福大学)（Ridgelet和Curvelet的创始人）•一种新的采样方法•以不确定准则为基础Romberg(佐治亚理工大学)Tao（加州大学洛杉矶分校）CS提出者用更一般的测量值代替信号样本值压缩感知或压缩采样直接获取压缩后的信号；压缩采样传输/存储NxMy接收重建y二.压缩感知理论2.1压缩感知问题描述假设x是一离散时间信号：NxR，这样压缩感知问题简化为是否存在一组测量信号MyR能完全恢复出x，其中MN。设y的每个分量ky是x与一组测量矢量,1NkRkM的内积，即：,kkyx，1kM，测量矩阵的行向量为k，的大小为MN，则测量信号y可以写为yx（2.1.1）问题为：是否存在一种测量，能使原始信号NxR由测量信号MyR恢复，这里MN。可以看出，式（2.1.1）是一个欠定方程，存在无穷多组解。要想唯一恢复x，信号x和矩阵还需要满足什么条件。三种线性方程组根据变量个数和方程个数来确定是欠定、适定还是超定方程组MN欠定方程组，无穷多解MN适定方程组，有唯一解MN超定方程组，无解良态问题1923年Hadamard提出了良态问题（Well-posedproblem）的概念，根据其定义，如果下述条件满足，称为良态问题（1）方程的解是存在的；（2）解是唯一的；（3）解连续地依赖于数据（观测矩阵或数据微小变化导致解很大变动）病态问题如果良态问题的三个条件任意一个不能满足，就称问题是病态的（ill-posedproblem）良态与病态问题：1212400201200800401200xxxx12100200xx1212401201200800401200xxxx124000079800xx病态问题举例系数矩阵A或者观测项(常数项)y的微小变化引起解的巨大变化,该问题为病态问题病态问题求解：用规整化（Regularization）理论处理病态问题目的是修改一个病态问题为一个良态问题，使得问题的解在物理上合理，并且解连续依赖于数据。基本思想是利用关于解的先验知识，构造附加约束或改变求解策略，使得逆问题的解变得确定且稳定。即对解进行约束J(x)约束信号x为平滑的应用Lagrange乘子，将P2问题约束转换为无约束问题2.如何设计测量矩阵，让其作用于信号后能保持信号的所有信息不丢失？（对应于香农采样定理中对采样率的要求）3.如何从测量中重建原信号？（对应依据香农采样定理采样后内插实现重建）1.信号应满足什么要求，方可重建？（对应香农采样定理中对信号的带宽要求）CS关注的问题信号表示将信号表示为一组正交基的线性组合如果合理选择基底，处理系数序列比直接处理信号简单；如果系数序列具有稀疏结构，可以从实质上降低信号处理的成本，提高压缩效率。二.压缩采样理论2.2信号的稀疏与可压缩性信号的稀疏（Sparsity）与可压缩性(Compressibility)设,1iiN为一组标准正交基，由这组基张成的空间为NR，设信号NxR，1Niiix，或用矩阵表示x，（的列为i，是元素为i的列向量）。x，其中,iix如果矢量的大多数元素都为0，称x为－域稀疏的。将其不为零的个数记为S，0S，称x为S-稀疏。如果矢量的元素按幅值大小排列，其幅度衰减很快，具有幂次速度（Powerlaw）衰减趋势。则称信号x为域可压缩的(Compressible)。光滑信号其Fourier变换,Wavelet变换系数呈现幂次衰减趋势其全变差（TotalVariation）呈现幂次衰减趋势有界变差函数给定一个定义于有界开集Ω上的可微函数f，其全变差（thetotalvariation）为对于图像x而言，其TV范数为Cameraman原图4层小波分解傅里叶幅频MRI图像4层小波分解傅里叶幅频原图垂直水平全变差根据信号x的先验知识，可以设计规整化项为R2空间，一维子空间用lp范数进行约束的解2.3.1不确定原理（测不准原理UncertaintyPrinciple,UP）物理学中经典的测不准原理两个共轭的物理量，如微观粒子的位置和动量，不能同时测准，其中一个量越确定，另一个量的不确定程度就越大2.3测量离散时间不确定准则（DiscreteTimeUncertaintyPrinciple）令()xt是长度为N的离散序列，01,,,tN，其离散Fourier变换为ˆx，01,,,N，tN，N分别为()xt和ˆx中不为零元素的个数，则2ttNNNNNN或者将记:supTpx，ˆ:suppx；TN；2TN注：集的势：集合元素的个数05010015000.10.20.30.40.50.60.70.80.9105010015000.10.20.30.40.50.60.70.80.9110110,,,,tmNmNxt其他其Fourier变换ˆx与x完全一样。ˆxx；此时2tNNN，或者说2TN如果信号的长度N为质数，排除了上述DiracComb的情况，则离散不确定准则为tNNNˆxxt2.3.2部分Fourier变换已知的信号重建与RobustUncertaintyPrinciplesCS提出的最初研究：2004年，EmmanuelCandes,JustinRomberg和TerenceTao对以下问题进行了研究离散时间信号NxC，其离散Fourier变换ˆ:NNFxxCC，如果已知x的N点Fourier系数ˆ[],NxkkZ，可以通过Fourier反变换完全恢复出x。问题：如果只是已知部分的Fourier系数ˆ[],xkk，其中为NZ的子集，NZ，N，是否可以恢复出原信号？注：集的势：集合元素的个数MRI图像Fourier采样，22线Fourier幅度定理2.1：假设信号x的长度N，且N为质数，x的支撑集为T，T为011,,,N的子集，若令其傅里叶变换xˆ的支撑集也为011,,,N的子集，如果满足：12T则x可以从和ˆx唯一恢复。反之，当N时，存在两个不同的信号1x和2x，1T和2112T，并且12ˆˆxx。定理2.2：NxC是离散信号，其支撑集为未知集NTZ，在所有M的集合中，随机选择一个频率集合，对于给定的精确度参数m，如果1mTCN(log)，其中常数0mC，能以至少1mON()的概率，从求解下式10ˆˆmin[]..[]Nngnstgkxkforallk得到的解是唯一的，且等于x。对于,20,24NNm，有1231mCmM=logN.S以往的ＵＰ：2TN(1)如果N为质数，则有TN（2）有NZ的两个子集T和，讨论T应为多大才可能构造出一个信号使得其时域和频域的支撑分别为T和。由于DiracComb代表的是特例，当其幅值不为1时，则ˆx在N点均不为0；对多数信号而言，(2)比（1）更接近实际情况；如果随机选择一对(,)T，如果1logNTN（RUP）（3）定理与UP的关系，以及RUP（RobustUncertaintyPrinciple）是预先确定的数，则能以超过1()ON的概率找到一个信号其时域和频域的支撑分别为T和。2.3.3随机采样与重建定义2.1互相干互定理2.3几点说明：2.信号表示越稀疏、两组基之间的互相干性越小，所需要的样本数就越少3.常用的测量矩阵有高斯和伯努利分布，因为其与大多数的稀疏表示基相干性小。测量结果稀疏信号x随机投影（测量）矩阵压缩采样的情况1:信号本身稀疏信号是时域稀疏的，频域测量结果含有信号的所有信息；信号测量01020304050607080901000123456789signalx05101520253035404550-1-0.8-0.6-0.4-0.200.20.40.60.8measurementresulty原信号xx*xM=50；S=19；N=100重建信号x时域信号频域1-维信号信号是频域稀疏的，时域测量结果；压缩采样的情况2信号可以用一组基稀疏表示2-维图像信号2.3.4一致不确定准则（UniformUncertaintyPrinciple,UUP）2222221322MMxxxNN假设为Fourier变换，为随机抽取行，上式说明，2ˆlx至多为232lMxN由于22ˆnlZlxx，可以看到，时域稀疏的信号x将在频域内平铺，而不是集中在内。除非M选得接近N，即测量点数要足够多。对Gaussian和Binary矩阵，是以logN，而傅立叶矩阵以6logN满足UUP；严格重建准则（ExactReconstructionPrinciple,ERP）称测量矩阵以过采样因子服从ERP，如果对足够小的a0和固定的正参数0，对于每个满足MTa的T，定义在T上的每个符号向量1t，以1()aON的概率存在具有下述性质的向量NPR，（i）Ptt对所有tT(ii)P是行向量的线性组合（iii）12Pt，对所有01:,,\CtTNT定义2.2：可压缩信号：设,1iiN为一组标准正交基，由这组基张成的空间为NR，设信号NxR，1Niiix，将这些系数的绝对值按降序重新排列12N对于0p,如果对于每个1nN，有1pnRn则称属于半径为R弱-lp球，或者将x记为pxwlR，换句话说，p控制衰减的速度，其值越小，则衰减越快。可压缩信号（近似稀疏信号）的重建定理1.4：令分别以1满足UUP，以2满足ERP，令12max,，假设M，如果信号NxR，且对01p，有1pnRn，或者1p时，1xR，令112rp，则对任意足够小的a，P1问题的解*x至少以概率1()aON满足2rpaMxxCR*,对Gaussian和Binary矩阵，是以logN满足UUP和ERP；而Fourier矩阵以6logN满足UUP，以logN满足ERP，因此，定理2.4对Guassian和Binary矩阵而言2rpaMxxCRN*,log1min,..styx（P1）