-
压缩感知和稀疏恢复中的L1同伦算法
2015-11-08 21:52:55压缩感知,稀疏恢复中能够用到的L1同伦算法,性能好,速度快,有一定参考价值。 -
压缩感知中稀疏信号恢复的贪婪正交匹配追踪算法
2021-03-26 14:07:20稀疏信号恢复问题一直是几个不同社区中广泛研究的主题。... 与OMP算法相比,对高斯和零一稀疏信号进行的实验表明,提出的GOMP算法可以提供更好的恢复性能。 最后,我们通过实验研究了GOMP中贪婪常数对恢复性能的影响。 -
一种改进的图像压缩感知稀疏恢复算法
2021-03-16 13:42:18稀疏信号的分布模型是影响基于近似信息传递(AMP)的压缩感知(CS)信号重建效果的关键因素。因实际图像的小波近似系数、各级的水平细节系数、垂直细节系数以及对角细节系数的模型参数存在较大差异,现有基于拉普拉斯、贝... -
压缩感知和稀疏信号处理课程笔记(陆吾生)
2016-04-26 16:52:44一、The Shannon-Nyquist Sampling Theorem 问题:原始数据是连续函数,是否能用有限个采样百分之百重现原始数据? 香农回答了这个问题:如果原始数据中最大频率为f,如果采样频率...图a是采样和恢复过程,图b表示原一、The Shannon-Nyquist Sampling Theorem
问题:原始数据是连续函数,是否能用有限个采样百分之百重现原始数据?
香农回答了这个问题:如果原始数据中最大频率为f,如果采样频率为2f,即每隔1/(2f)秒取一次样,则可完全恢复原始数据。
陆吾生教授2010年的视频中给出了非常直观的解释:
图a是采样和恢复过程,图b表示原始函数的傅里叶变换得到的频域分布,图c表示取样后的频域分布,可以看到是原始频域分布复制粘贴,且按采样频率位移,因为频率分布不能重叠,否则信息就会丢失,这个用公式表示就是下图的关系,所以可以很容易得到采样频率和原始频率的关系,图d是低通滤波器,图e是低通部分,即原始数据的频率分布。
最终的恢复公式就是,可以看成是采样后的信号与sinc函数卷积的结果:
其中sinc(x)部分是
,它的图示曲线是:
二、Sparse and Compressible Signals
(我的理解)如果信号是由某种分布或者几种分布构成,则信号是可以被压缩的。
比如离散余弦变换DCT和离散小波变换DWT,本质上即是预先设定的两组正交基,通过θ=C’x或θ=W‘x即可将原始向量解释为预设空间中的坐标。将θ中接近0的部分设为0,得到θ‘,则转换后的数据x' = Cθ'或x' = Wθ',其中C'和W’分别为C和W的转置。
- %Below is a MALAB code to generate matrix DCT.
- function C = gen_dct(n)
- alp = [sqrt(1/n) sqrt(2/n)*ones(1,n-1)];
- ind = (1:2:(2*n-1))*pi/(2*n);
- C = zeros(n,n);
- for k = 1:n,
- C(k,:) = alp(k)*cos((k-1)*ind);
- end
- %Our second example is about an orthonormal basis based on discrete wavelet transform <span style="font-family: Arial, Helvetica, sans-serif; font-size: 12px;">DWT.</span>
- % Suppose signal length n= 2^p
- %for some integer p, then the basis matrix Wof size nby n
- %associated with Daubechies’ orthogonal discrete wavelets can be readily constructed in MATLAB
- %using Toolbox Uvi_Wave toolbox as follows:
- % n -- signal length, must be a power of 2.
- % L -- length of Daubechies wavelet, must be an even integer.
- % W -- orthonormal DWT matrix of size n x n.
- function W = gen_wave(n,L)
- p = log2(n);
- [h0,h1,f0,f1] = daub(L);
- I = eye(n,n);
- W = I;
- for i = 1:n,
- Ii = I(:,i);
- W(:,i) = wt(Ii,h0,h1,p);
- end
上面两图为余弦变换和小波变换的结果,50,100为对应的阈值,可以看出不同的正交基得到的结果不尽相同。
陆吾生教授的视频里小波变换讲得非常好,想学习的一定要去看看。
三、Sensing a Sparse Signal
小波变换W,θ= W‘x,其实可以理解为用W中基底解释x的过程,x的稀疏性取决于W基底的”完备性“。这个可以理解为W是一个字典,W中的基底就是字典中的词,词越多你对原句的解释就可以越简洁,比如”上海“可以解释为”上“+”海“,也可以解释为”沪“,因此增加一个矩阵得到[I W],可以得到更好的稀疏性。字典可以用其他已知的基底构成,比如单位矩阵I,离散余弦变换DCT,离散小波变换DWT,离散傅里叶变换DFT,Hadamard-Walsh矩阵等等。
现在问题变为Dθ= x,D是n*l的字典,θ是l*1的解,x是输入向量,如何找到最稀疏的θ?
Dθ = x其实是一个方程数小于变量数的线性方程组,所以这个方程的解一定是特解加通解的形式,特解是类似于广义逆的形式,θ1 = D‘inv(DD')x,通解需要对D进行SVD分解D=UΛV,U是n*n的特征向量矩阵,Λ是n*l特征值矩阵,V是l*l的特征向量矩阵,θ2 = Vn*δ,Vn是V后(l-n)列,即l*(l-n)的矩阵,δ是(l-n)*1的自由变量(随便是啥),问题就变成了如何选择δ确定的解空间中寻找最稀疏的θ1+θ2。
最优化问题形式化为:
其中0-norm表示θ中非0元素的个数,可是这个问题是NP-hard问题,不过可以转化为:
1-norm就是绝对值的和,上面问题就可以转化为另一个不带绝对值的线性规划问题,这个问题可以用sedumi这个工具求解(具体过程请看陆教授的视频),得到的解比直接用DWT要好很多。
四、Compressed Sensing
按照香农的理论,假设采样频率为f=n,则一秒钟需要采样n个数据,从线性代数的角度来看,是将无限维原始数据映射到n维正交空间。DCT和DWT或者他们构成的字典提供了巧妙的正交基,使得新向量变得稀疏。现在有个想法,为什么不直接采样到好空间?换句话说,能否在采样时不是按照原始数据的频率,而是按照原始数据信息的频率。
假设信号在Ψ空间中是r-sparse,转化为压缩信号θ:
现在有另外一个空间Φ,采样x:
Φ^{\hat}是Φ随机抽取m行的结果,y是m*1,Φ^{\hat}是m*n,x是n*1,m<n,所以这里是压缩采样。
已知y重建x的过程就是最优化一个最稀疏的θ,然后用上面的公式求出x
当m满足下面公式时,可以保证信号可以恢复:
可以简化为:
压缩感知的Matlab tool可以用CalTech的l1-MAGIC。
Ψ的选择很重要,直接确定原始数据中哪些信息是noise哪些是真实信息,也就是决定信号是否可以压缩以及压缩后是否可以恢复,Φ可以是随机的矩阵。
-
压缩感知动目标检测
2015-08-10 21:59:17利用压缩感知和稀疏恢复联合空时自适应信号处理检测动目标,从而进行杂波抑制,稀疏恢复出我们所需的动目标信号 -
基于压缩感知的信号恢复算法研究
2012-09-26 10:28:13发现了一种新的信号处理方法--压缩感知理论。针对稀疏信号或者可压缩信号,该理论可 以使用远低于传统奈奎斯特采样定理所要求的采样速率,成功实现了信号采样与压缩同时 进行,并且能够精确的恢复出原始信号。 -
压缩感知的局部支持恢复和信号重构性能分析
2021-03-16 03:40:38压缩感测领域的最新工作主要集中在对稀疏信号的完整支持的完美恢复上。 但是,在许多实际情况下,部分支撑恢复(信号支撑的一部分已正确恢复)可能就足够了。 在这项研究中,在高维和嘈杂的环境中,作者开发了最优... -
压缩感知应用实例(1)——不完备测量数据的稀疏向量恢复(经典线性规划求解方法)
2019-01-29 21:16:49在本例中,原始稀疏向量。假设,中的非零向量数目为10。 如果不对数据压缩,...在压缩感知中,我们希望通过对的线性变换减少观测数据的数目。例如,令矩阵,使得,并假设矩阵是由矩阵随机选择行元素所生成。利用...在本例中,原始稀疏向量
。假设
,
中的非零向量数目为10。
如果不对数据压缩,直接用一个矩阵
对数据
进行变换,得到全观测数据:
(1)
这里,
为线性变换矩阵,本文中假设其为离散傅里叶(DCT)变换矩阵,原始稀疏向量
和对其进行DCT变换之后和全观测数据如下图所示:
在压缩感知中,我们希望通过对
的线性变换减少观测数据的数目。例如,令矩阵
,使得
,并假设矩阵
是由矩阵
随机选择
行元素所生成。利用矩阵
对原始稀疏数据
进行线性变换之后得到压缩之后的观测数据:
(2)
不失一般性,我们假设
,即我们观测到40%的数据。这些数据如下图所示。
其中,为了便于对比,把
的数据进行了重新排序,使得其数据与
的数据位置对位。例如,矩阵
的第
行数据
在矩阵
中的位置为第
行,则
。这样,我们得到一个与全观测数据
对位的压缩数据
。
实时上,如果不进行排序对位,M=80个数据取决于随机产生的A中的行向量,如下图(第2个子图)所示
如果给定压缩之后的观测数据
,如何恢复原始数据
呢?
为了恢复
,我们构建如下的稀疏恢复优化问题:
(3)
然而,上述
优化问题是非凸优化问题,其求解为NP-hard,难以直接求解。为了求解,我们将它转化为
优化问题:
(4)
该问题为凸优化问题,因而可以有效求解。求解方法有多种,我们采用最经典的算法,即将其转化为线性规划求解。具体而言,可以将
范数转化为如下等效表示方式:
(5)
这样,问题(4)可以转化为:
(6)
问题(6)是线性规划,可以很容易求解得到最优解
。则问题(4)的最优解为:
(7).
应用上述算法,得到如下图所示的恢复结果。
如果改变M的数值,恢复效果如何呢?下面我们改变M的数值,可以看到,当M<40时,无法精确恢复原始信号。
Summary: 利用压缩感知,可以大幅度减少采样数据点,从而实现稀疏数据量的压缩。当然,这种压缩不是任意小,而是要有最小观测数据量的保证。最后,给出一张本次实例的全家福。
-
论文研究-基于神经动力学优化的压缩感知信号恢复方法.pdf
2019-07-22 20:04:07针对稀疏信号的准确和实时恢复问题,提出了一种基于神经动力学优化的压缩感知信号恢复方法。通过引入反馈神经网络(recurrent neural network,RNN)模型求解l1范数最小化优化问题,计算RNN的稳态解以恢复稀疏信号。... -
压缩感知和深度学习的区别
2015-09-29 10:35:14本质上是两个问题。如果一定要找联系,两者都涉及...线性逆问题和稀疏性在这类问题中的应用有相对完整的理论体系,楼上 yang liu推荐的 Michael Elad的书是很好的入门教材。 另一类关系密切的问题是低秩矩阵恢复(l本质上是两个问题。如果一定要找联系,两者都涉及数据的稀疏表达。
压缩感知解决“逆问题”:Ax=b。对于欠定的线性系统,如果已知解具有稀疏性(sparsity),稀疏性可以作为约束或者正则项,提供额外的先验信息。线性逆问题和稀疏性在这类问题中的应用有相对完整的理论体系,楼上 yang liu推荐的 Michael Elad的书是很好的入门教材。
另一类关系密切的问题是低秩矩阵恢复(low-rank matrix recovery),使用low-rank作为先验知识,解关于矩阵的线性逆问题,发展出一套理论。
压缩感知的思想被应用在了更多的领域,比如非线性逆问题。相关的理论正在快速的发展,但是应用已经领先一步。我个人感兴趣的是双线性逆问题(bilinear inverse problem),比如盲反卷积(blind deconvolution)、矩阵分解(matrix factorization)。
在应用压缩感知的过程中,我们发现大部分信号本身并不是稀疏的(即在自然基下的表达不是稀疏的)。但是经过适当的线性变换后是稀疏的(即在我们选择的另一组基(basis)或者框架(frame,我不知道如何翻译)下是稀疏的)。比如谐波提取(harmonic retrieval)中,时域信号不稀疏,但在傅里叶域信号是稀疏的。再比如大部分自然图像不是稀疏的,但经过DCT(离散余先变换)或者wavelet transform(小波变换),可以得到稀疏的表达。一个一度非常热门的研究课题是字典学习(Dictionary Learning)和变换学习(Transform Learning),通过大量的信号实例,自适应地学习稀疏性表达。
深度学习是机器学习的一种手段,参见楼上Stephen Wang的解释。深度学习中通常都涉及非线性环节。这里数据表达的目的通常不再是数据恢复(recovery),而是分类(classification)等机器学习的任务。
下面是我理解的区别:
在信号处理中的稀疏表达学习(sparse representation learning)侧重对信号建模,即目标是获取原信号的一个忠实的表达(faithful representation)。我们通常需要变换和逆变换,来实现信号的重建(reconstruction)。即使在不需要重建的问题中,我们也需要这种表达能够很好地区分有意义的信号和无意义的噪声(discriminate signal against noise)。所以这类变换通常有很多良好的性质(可逆、很好的条件数(condition numer)等)。
深度学习或者更广泛的机器学习中,数据表达的目标因问题而异,但是通常我们都不需要这种表达过程的可逆性。比如在分类问题中,我们的目标是把数据变换到有“意义”的空间,实现不同类别信号的分离。这种变换可以是线性或非线性的,可以是可逆或不可逆的,可以变换到稀疏的表达或其他有意义的便于分类的表达。
-
稀疏贝叶斯算法.zip
2020-06-03 16:34:27利用MATLAB实现稀疏贝叶斯算法,对于压缩感知的学习是一个比较好的东西,可以对具体的过程实现有进一步的了解,用在压缩感知和稀疏恢复重建之中 -
论文研究-压缩感知和相似性约束的图像超分辨率重构算法.pdf
2019-07-22 21:10:52针对通过外部学习进行超分辨率存在图像质量不佳、细节不真实的问题提出一种压缩感知和相似性约束的单帧图像超分辨率算法。算法首先利用压缩感知中测量域与频域的线性关系对训练库图像在测量域分类,对不同类别图像块... -
压缩感知笔记
2021-03-30 14:56:38压缩感知笔记 CS理论认为,我们可以从比奈奎斯特...**压缩感知(CS)主要利用测量矩阵和表示矩阵之间的非相干性(incoherence)。在CS框架下测量矩阵和表示矩阵之间的低相干性表示可以用更少的采样重建原始信号。 ...压缩感知笔记
CS理论认为,我们可以从比奈奎斯特采样所需的更少的样本中恢复某些信号。如果信号在原始域或变换域中是稀疏的(完全恢复)或可压缩的(近似恢复),我们可以用比奈奎斯特采样所需的更少的采样样本对其进行采样,并保持原信号的绝大部分信息。
**核心
**压缩感知(CS)主要利用测量矩阵和表示矩阵之间的非相干性(incoherence)。在CS框架下测量矩阵和表示矩阵之间的低相干性表示可以用更少的采样重建原始信号。s-稀疏
如果一个信号只有s个非零系数,则称该信号为s-稀疏信号。如果大部分映射系数小到可以忽略不记,则称该信号是可压缩的(compressible)。限制等距性(RIP)
被广泛用于评估压缩感知重建算法性能的工具。随机测量
只要φ满足以下条件,就可以对任意基的s-稀疏信号进行随机测量:m = s*log(n/s)
基追踪
根据现有文献,测量矩阵φ可以是高斯、伯努利、傅里叶或非相干测量矩阵。对于一类被称为基追踪的重构算法表明,大多数s稀疏信号都可以精确恢复,只要确保m >= 4*s
重建模型
在接收端采用一种非线性算法重建原始信号。这种非线性重建算法需要了解信号稀疏(精确恢复)或可压缩(近似恢复)的表示基(原始域或转换域),即最终目的是得到x,用已知的Ψ恢复出X。感兴趣信号为X,则可用表示基表示为:
Ψx = X
其中x是s-稀疏向量,表示X在Ψ上的投影稀疏。
因此测量向量Y可以写成x的形式:Y = Θx
其中Θ = ΦΨ,是m×n维的重建矩阵。CS中的重构算法,尝试求解上式,并利用解是稀疏的这一事实,通常通过最小化解空间上的l0、l1或l2范数。根据经典的最小二乘解(l2范数的最小化),重建解可表示为:
类似地,通过使用l1最小化或BP,正如在CS文献中所知,通过线性规划解决一个简单的凸优化问题,信号可以从’ m '测量值精确恢复。一些重构技术是基于l0最小化的。
然而,由于现实世界中绝大多数信号都不是稀疏的,而是可压缩的,l2最小化通常不能给出较好的结果。另一方面,l0最小化则能给出较为准确地结果,但这是一个NP难题,因此很多文献采用l1最小化,因为它在很多情况下能给出与l0相同的结果。虽然最小化的基本概念是所有求解框架的共同概念,但在求解范数最小化方程的方法中存在着变量。
重建算法
文献中存在许多有效的算法,它们不是同时找到“m”个最大的系数,而是尝试迭代地找到这些系数。为了对CS稀疏信号恢复的重构算法进行概述,这些算法大致可以分为六种,如下图:
-
DeepMind论文:深度压缩感知,新框架提升GAN性能
2019-05-26 10:18:02【新智元导读】DeepMind提出一种全新的“深度压缩感知”框架,将压缩感知与深度学习相结合,显著提高了信号恢复的性能和速度,并提出一种改进GAN的新方法。 压缩感知(CS)是一种优雅的框架,用于从压缩信号中恢复... -
基于压缩感知的脑电信号压缩采样
2012-07-12 16:21:07基础知识和压缩感知的理论框架。接下来研究了基于压缩感知理论对单通道EEG信号 的压缩采样,内容包括脑电信号最佳稀疏分解,通过实验对比发现,对于EEG信号, 以高斯函数、高斯小波函数、墨西哥草帽函数作为原子的... -
用于非均匀可压缩信号的扩展窗口压缩感知
2021-03-18 01:54:58利用这种先验信息,本文通过引入称为扩展窗口压缩感知(EW-CS)的开窗策略,提出了一种具有不平等保护能力的新型压缩感知(CS)方案。 根据信号不同部分的重要性,信号被分为几个嵌套的子集,即扩展窗口。 每个窗口... -
压缩感知重构算法综述-学习笔记
2021-03-10 09:43:00压缩感知理论:对于稀疏或可压缩的信号,能够以远低于奈奎斯特频率对其进行采样,并通过设计重构算法来精确的恢复信号。 文章工作: 1、介绍压缩感知理论的基本框架,讨论该理论关于信号压缩的采样过程; 2、综述... -
图像分块的贝叶斯压缩感知算法研究
2020-06-26 23:36:35为增加信号重构的可信度和减少重构过程的人为干预,采用贝叶斯压缩感知的方法,将待重构信号赋予先验分布,不仅重构出信号参数,并能同时获得信号参数的置信区间,以此实时调整重构模型使信号恢复达到最佳。基于拉普拉斯... -
基于压缩感知的监控视频重构
2021-03-05 12:29:43恢复时利用关键帧和差值可以得到初步重构的视频序列,最后通过运动估计和运动补偿得到优化。实验结果表明,与仅使用压缩感知对差分帧进行重构的方法相比,该方法对监控视频重构帧序列图像的平均峰值信噪比有较大的... -
长时延扩展水声信道的联合稀疏恢复估计
2021-01-14 15:54:43压缩感知信道估计方法可有效利用多径稀疏特性改善性能,但需采用较大的训练序列长度以保证稀疏恢复精度,由此导致额外的系统开销。利用水声信道多径稀疏结构在数据块间存在的相关性,建立基于分布式压缩感知的长时延... -
论文研究-基于压缩感知的无线传感网络数据压缩.pdf
2019-09-07 04:03:11压缩感知(Compressed Sensing,CS)理论表明,利用最优化理论,稀疏信号可以从少量的非自适应线性投影中高概率精确恢复。根据CS理论设计WSN的数据压缩方法只依赖于信号内在的结构和内容,而不是信号的带宽,弥补了... -
深度压缩感知-应用于GAN
2019-06-05 10:39:24压缩感知(CS,Compressed Sensing)是一种优雅的框架,用于从压缩信号中恢复稀疏信号。 例如,CS可以利用自然图像的结构,仅从少量的随机测量中恢复图像。 思想:在信号采样的过程中,用很少的采样点,实现了和全采样... -
压缩感知图像重构中矩阵互相关性的研究
2020-10-17 22:49:30从测量矩阵和稀疏矩阵的互相关性角度出发,通过对测量矩阵和稀疏矩阵所...通过在DWT、DCT下的压缩感知图像重构实验验证了该方法的可行性,恢复效果得到一定程度的提高,相比于传统的小波恢复重构,达到了预期的效果。 -
压缩感知启发式字典学习和空间光谱正则化的高光谱图像超分辨率
2021-04-02 09:41:09首先,受压缩感测(CS)框架的启发,为了学习高分辨率词典,我们鼓励在图像块上增强稀疏性,并提高所学习的词典和感测矩阵之间的连贯性。 因此,提出了一种稀疏性和不连贯性受限的字典学习方法,以实现更高效率的... -
无线传感器网络中基于压缩感知的异常事件检测与定位
2021-03-17 18:16:33无线传感器网络的主要挑战是事件... 在假设传感器的传输信号为二进制的情况下,分析了基本追踪算法与乘法器交替方向法以及其他压缩感知恢复算法相结合的性能。 仿真结果验证了基本追踪算法在准确检测和定位方面的优势。 -
DCS_SOMP分布式压缩感知
2013-12-12 17:22:35DCS_SOMP分布式压缩感知 根据 CS 理论可知,在信号长度一定的情况下, 稀疏度越好,所需的测量值个数越少。对于一个信号群,选择不同的共同分量会有不同的联合稀疏效果。如果能够知道每个节点采集到的信号,那么可以... -
基于压缩感知的后调制远距离三维成像研究
2021-02-07 23:08:27基于压缩感知(CS)理论,提出使用高功率纳秒脉冲激光...同时也证实利用压缩感知进行远距离图像恢复,随着采样率的提高,图像恢复的质量和对比度都有一定程度的提高;目标物体图像越稀疏,重构图像所需的采样次数越少。 -
自适应线性预测卡尔曼滤波压缩感知算法
2021-01-12 17:27:30针对压缩感知中时变稀疏信号的重建问题,提出一种基于自适应线性预测的卡尔曼滤波恢复算法.该算法采用滑动窗口对信号进行观测,基于前后窗信号之间的相关性并利用自适应线性预测方法,建立前后窗口信号的状态转移方程,... -
论文研究-残差分布式视频压缩感知.pdf
2019-07-22 23:06:36压缩感知(CS)是一种能同时进行数据采集和压缩的新理论,为简化编码算法提供了依据,同时,分布式视频编码(DVC)为低复杂度的视频编码提供了思路。因此,通过整合DVC和CS各自的特性以构建编码简单的视频编码框架, ... -
压缩感知基本概括——三大基本问题
2019-08-15 19:37:30压缩感知是对于N维的信号x,使用小的观测维数M≪N,设计一个M*N的测量矩阵Φ,得到测量结果y=ϕx,最终通过测得的y和已知的矩阵Φ来求得信号x。 x信号特点:具有稀疏性。即信号本身或者使用一组基地展开后大多数...