压缩感知课件

1、压缩感知理论与应用,智能信息处理研究所 智能感知与图像理解教育部重点实验室 2011年8月,Intelligent Perception and Image Understanding Key Lab of Ministry of China,上次课内容回顾,Lecture 1： 压缩感知概述 为什么研究压缩感知 压缩感知的涵义 压缩感知的过程 压缩感知的关键问题,From Nyquist to CS,Compression,Original 2500 KB100,Compressed 950 KB38,Compressed 392 KB15,Compressed 148 KB6,Sparse

2、 representation of an image via a multiscale wavelet transform. (a) Original image. (b) Wavelet representation. Large coefficients are represented by light pixels, while small coefficients are represented by dark pixels. Observe that most of the wavelet coefficients are close to zero,Sparse in wavel

3、et-domain,Sparse approximation of a natural image. (a) Original image.(b) Approximation of image obtained by keeping only the largest 10% of the wavelet coefficients,Sparse in wavelet-domain,Our Point-Of-View,Compressed Sensing(CS) must be based on sparsity and compressibility. The signals must be s

4、parse in time-domain or in frquency-domain,Compressed Sensing,Nyquist rateSampling,AnalogAudioSignal,Compression(e.g. MP3,High-rate,Low-rate,CompressedSensing,Concept,Goal: Identify the bucket with fake coins,Nyquist,Weigh a coinfrom each bucket,Compression,Bucket ,numbers,1 number,Compressed Sensin

5、g,Bucket ,1 number,Weigh a linear combinationof coins from all buckets,Mathematical Tools,non-zero entries at least measurements,Recovery: brute-force, convex optimization, greedy algorithms, and more,CS theory,Compressed sensing (2003/4 and on) Main results,Maximal cardinality of linearly independe

6、nt column subsets,Hard to compute,is uniquely determined by,Donoho and Elad, 2003,Smallest number of columns that are linearly-dependent,is uniquely determined by,is random,with high probability,Donoho, 2006 and Cands et. al., 2006,NP-hard,Convex and tractable,Greedy algorithms: OMP, FOCUSS, etc,Don

7、oho, 2006 and Cands et. al., 2006,Tropp, Cotter et. al. Chen et. al. and many other,Compressed sensing (2003/4 and on) Main results,CS theory,Donoho and Elad, 2003,RIP criterion,a)The measurements can maintain the energy of the original time-domain signal . (b)If is sparse, the must be dense to main

8、tain the energy,Vector space,Unit spheres in for the norms with , and for the quasinorm with,Vector space,The norms is used to reconstruct the signal Best approximation of a point in by a one-dimensional subspace using the norms for , and the quasinorm with,Lecture 2 : Modern Sampling Methods and CS

9、,Sampling: “Analog Girl in a Digital World” Judy Gorman 99,Digital world,Analog world,Signal processing Denoising Image analysis,Reconstruction D2A,Sampling A2D,Interpolation,Applications:Sampling Rate Conversion,Common audio standards: 8 KHz (VOIP, wireless microphone, ) 11.025 KHz (MPEG audio, ) 1

10、6 KHz (VOIP, ) 22.05 KHz (MPEG audio, ) 32 KHz (miniDV, DVCAM, DAT, NICAM, ) 44.1 KHz (CD, MP3, ) 48 KHz (DVD, DAT, ),Lens distortion correction Image scaling,Applications:Image Transformations,Applications: CT Scans,Applications:Spatial Superresolution,Our Point-Of-View,The field of sampling was tr

11、aditionally associated with methods implemented either in the frequency domain, or in the time domain Sampling can be viewed in a broader sense of projection onto any subspace or union of subspaces Can we sample a signal below Nyquist sampling rate.(We must know something about the signals,Shannons

12、sampling theorem revisited,Cauchy (1841): Whittaker (1915) - Shannon (1948): A. J. Jerri, “The Shannon sampling theorem - its various extensions and applications: A tutorial review”, Proc. IEEE, pp. 1565-1595, Nov. 1977,Bandlimited Sampling Theorems,Limitations of Shannons Theorem,Towards more robus

13、t DSPs: General inputs Nonideal sampling: general pre-filters, nonlinear distortions Simple interpolation kernels,Sampling Process,Employ estimation techniques,Sampling Process Noise,Signal Priors,x(t) bandlimited,x(t) piece-wise linear,Different priors lead to different reconstructions,Sparsity,If

14、a sequence has elements and only of them are nonzeros .Then the sequence is sparse. If a sequence is a sparse vector, then the,Signal Priors：Sparsity Priors,Wavelet transform of images is commonly sparse STFT transform of speech signals is commonly sparse Fourier transform of radio signals is common

15、ly sparse,From discrete to analog,Discrete Compressed Sensing Analog Compressive Sampling,Analog Compressed Sensing,A signal with a multiband structure in some basis,no more than N bands, max width B, bandlimited to,Mishali and Eldar 2007,Each band has an uncountable number of non-zero elements,Band

16、 locations lie on an infinite grid,Band locations are unknown in advance,What is the definition of analog sparsity ,Eldar 2008,Sampling and Reconstruction,Sampling,Reconstruction,Union of subspaces,If the filter is different from ,then a multirate correction system must be given.(In practice, the fi

17、lters are often undesirable,Problem,Sub-Nyquist sampling,Both process and recovery are based on lowrate computation. The raw data can be directly stored,Some questions about the Sub-Nyquist sampling,How to obtain the digital signal at a sub-nyquist rate? Can we reconstruct the signal with high proba

18、bility approximately,Sub-Nyquist sampling and Compressed Sensing,Multi-Band Sensing: Goals,bands,Sampling,Reconstruction,Goal: Perfect reconstruction,Constraints,Minimal sampling rate Fully blind system,Analog,Infinite,Analog,What is the minimal rate ? What is the sensing mechanism ,How to reconstru

19、ct from infinite sequences ,Sub-Nyquist sampling,Landau minimum rate means sampling at of the Nyquist rate can reconstruct the signal perfectly. （but the spectral support must be known,Nonuniform sampling,Analog signal,In each block of samples, only are kept, as described by,Point-wise samples,0,2,3

20、,0,0,2,2,3,3,Multi-Coset: Periodic Non-uniform on the Nyquist grid,Nonuniform sampling,Denote by the sequence of samples taken at the Nyquist rate,Therefore， in which,Nonuniform sampling,The building blocks are uniform samplers at rate , so that the average sampling rate is ,which is lower than the

21、Nyquist rate where,Nonuniform sampling,Reconstruction of the original signal is achieved if we recover its spectral components . But there are fewer equations than the unknown for each,HOW TO RECONSTRUCT THE SIGNAL,Nonuniform sampling,A method should be used to reduce the degree of the problem,Some

22、subcell are active,while the others are not.The analog signal can be reconstructed perfectly if the amplitude and locations of has been known,Some problem,1 Practical ADCs introduce an inherent bandwidth limitation,which distorts the samples. Any spectral content beyond bHz is attenuated and distort

23、ed. 2 Another practical issue of multicoset sampling, arises from the time shift elements. Maintaining accurate time delays between the ADCs in the order of the Nyquist interval is difficult,Introduce to RD,To solve the parctical problems somethings about the RD(random demodulated) methord can be us

24、ed,a Our system exploits spread-spectrum techniques from communication theory . An analog mixing front-end aliases the spectrum, such that a spectrum portion from each band appears in baseband. b Sign alternating functions can be implemented by a standard(high rate) shift register. Todays technology

25、 allows to reach alternation rates of 23 GHz and even 80GHz . c Blind multiband signal(arbitrary spectral locations) can be reconstructed by this system with high probablity,Advantage,多频带信号-许多信号只占用了少量带宽，因而具有稀疏性,子空间采样理论,MWC模块,这里我们需要大量的滤波器，才能精确的重构，也就是 值越大越好（对应的采样频率也逐渐增大），由于信号的稀疏性，一般要求 ， 为频带个数,实际采样框图,傅

26、里叶变换原子,如果是离散信号的重构，我们可以直接通过优化求解，模拟信号我们有无穷多个方程要解，必须转化成有限的模型，高概率的重构原始信号,引入一个CTF模型，通过 和支撑区间 ，我们可以重构出信号,AIC via Random Demodulation,理论框图,公式描述,Qusi-Toeplitz矩阵观测,理论框图,几个参数的说明 B随机滤波器的长度，d是信号的长度，N是采样点数，s是原始信号，h是随机滤波器,可以看成是,其中观测矩阵 为每一行元素移位 个单元，构成的观测矩阵,实验结果,Definition：Those that are determined by a finite numb

27、er of parameters per time unit. The -local rate of innovation of a signal x(t), denoted , is the minimal number of parameters defining any length- segment of x(t), divided by . An FRI signal is one for which is finite, at least for large enough . Perhaps the simplest class of FRI signals corresponds

28、 to functions that can be expressed as,Finite rate of innovation Signals,This set of signals is a linear subspace of L2, which is often termed a shift-invariant (SI) space,Finite rate of innovation Signals,A union of subspaces,This model generalizes the family of multiband signals,The frequencies de

29、termine the subspace and the amplitudes a,m determine the position within the subspace,Our goal is to recover x by observing N generalized samples c = (c1, . . . , cN)T obtained as where S : H RN is some (possibly nonlinear) Frechet differentiable operator. This representation is more general than t

30、he widely used linear setting, in which for some set of vectors sn in H. In particular, it may account for nonlinear distortions introduced by the sampling device. For example, S can represent the samples where f() is a nonlinear sensor response. We say that a sampling operator S is stable with resp

31、ect to X if there exist constants 0 s s such that for all x1, x2 X,Sampling method,The pulse shape is known a-priori, and therefore the signal has only 2K degrees of freedom per period. Since x is periodic it can be represented in terms of its Fourier series coefficients where in a we used Poisson s

32、ummation formula, and,where uk and p-1 denotes the multiplicative inverse of p. Since p is known a-priori, we assume for simplicity of notation that p=1 . In order to nd the values uk in (1.23), let h denote the filter whose z-transform is, where the last equality is due to the fact that h=0. The fi

33、lter is called an annihilating filter , since it zeroes the signal xm. Its roots uniquely define the set of values uk, provided that the locations tk are distinct,Sinc kernels,E-spline kernels,Sos kernels,Super-resolution,Ultrasound imaging,Super-resolution radar,Sinc函数观测矩阵,Sinc函数观测矩阵,加入 个周期的观测矩阵,Po

34、isson求和公式的变形,为 的傅里叶变换,用有限个求和表示无穷多个周期相加的观测矩阵,Sinc函数观测矩阵,Compressed Sensing,Explosion of interest in the idea of CS: Recover a vector x from a small number of measurements y=Ax Many beautiful papers covering theory, algorithms, and applications,Analog Compressed Sensing,Can we use these ideas to build new sub-Nyquist A/D converters? Prior work: Yu et. al., Ragheb et. al., Tropp et. al,Input Sparsity Measurement