Transcription of © DIGITAL VISION An Introduction To Compressive Sampling
1 DIGITAL VISIOND igital Object Identifier approaches to Sampling signals or images follow Shannon s cel-ebrated theorem: the Sampling rate must be at least twice the maximum fre-quency present in the signal (the so-called Nyquist rate). In fact, thisprinciple underlies nearly all signal acquisition protocols used in consumeraudio and visual electronics, medical imaging devices, radio receivers, andso on. (For some signals, such as images that are not naturally bandlimited, the sam-pling rate is dictated not by the Shannon theorem but by the desired temporal or spatialresolution.)
2 However, it is common in such systems to use an antialiasing low-pass filterto bandlimit the signal before Sampling , and so the Shannon theorem plays an implicitrole.) In the field of data conversion, for example, standard analog -to- DIGITAL converter(ADC) technology implements the usual quantized Shannon representation: the signal isuniformly sampled at or above the Nyquist rate.[Emmanuel J. Cand s and Michael B. Wakin]An Introduction ToCompressive Sampling [A sensing / Sampling paradigm that goes against the common knowledge in data acquisition]1053-5888/08/$ 2008 IEEEIEEE SIGNAL PROCESSING MAGAZINE[21]MARCH 2008 This article surveys the theory of Compressive Sampling , alsoknown as compressed sensing or CS, a novel sensing /samplingparadigm that goes against the common wisdom in data acquisi-tion.
3 CS theory asserts that one can recover certain signals andimages from far fewer samples or measurements than tradition-al methods use. To make this possible, CS relies on two princi-ples: sparsity, which pertains to the signals of interest, andincoherence, which pertains to the sensing modality. Sparsity expresses the idea that the informationrate of a continuous time signal may be much smallerthan suggested by its bandwidth, or that a discrete-timesignal depends on a number of degrees of freedomwhich is comparably much smaller than its (finite)length.
4 More precisely, CS exploits the fact that manynatural signals are sparse or compressible in the sensethat they have concise rep-resentations when expressedin the proper basis . Incoherence extends theduality between time and fre-quency and expresses the ideathat objects having a sparserepresentation in must bespread out in the domain inwhich they are acquired, just as a Dirac or a spike in thetime domain is spread out in the frequency domain. Putdifferently, incoherence says that unlike the signal ofinterest, the Sampling / sensing waveforms have anextremely dense representation in.
5 The crucial observation is that one can design efficientsensing or Sampling protocols that capture the useful infor-mation content embedded in a sparse signal and condense itinto a small amount of data. These protocols are nonadaptiveand simply require correlating the signal with a small num-ber of fixed waveforms that are incoherent with the sparsify-ing basis. What is most remarkable about these samplingprotocols is that they allow a sensor to very efficiently cap-ture the information in a sparse signal without trying tocomprehend that signal.
6 Further, there is a way to usenumerical optimization to reconstruct the full-length signalfrom the small amount of collected data. In other words, CSis a very simple and efficient signal acquisition protocolwhich samples in a signal independent fashion at a lowrate and later uses computational power for reconstructionfrom what appears to be an incomplete set of intent in this article is to overview the basic CS theorythat emerged in the works [1] [3], present the key mathemat-ical ideas underlying this theory, and survey a couple ofimportant results in the field.
7 Our goal is to explain CS asplainly as possible, and so our article is mainly of a tutorialnature. One of the charms of this theory is that it draws fromvarious subdisciplines within the applied mathematical sci-ences, most notably probability theory. In this review, we havedecided to highlight this aspect and especially the fact thatrandomness can perhaps surprisingly lead to very effectivesensing mechanisms. We will also discuss significant implica-tions, explain why CS is a concrete protocol for sensing andcompressing data simultaneously (thus the name), and con-clude our tour by reviewing important sensing PROBLEMIn this article, we discuss sensing mechanisms in which infor-mation about a signal f(t)is obtained by linear functionalsrecording the valuesyk= f, k ,k=1.
8 ,m.(1)That is, we simply correlate the object we wish to acquirewith the waveforms k(t). This is a standard setup. If thesensing waveforms are Dirac delta functions (spikes), forexample, then yis a vector ofsampled values of fin the timeor space domain. If the sensingwaveforms are indicator func-tions of pixels, then yis theimage data typically collected bysensors in a DIGITAL camera. If thesensing waveforms are sinusoids,then yis a vector of Fourier coef-ficients; this is the sensing modality used in magnetic reso-nance imaging (MRI).
9 Other examples one could develop a CS theory of continuoustime/space signals, we restrict our attention to discrete sig-nals f Rn. The reason is essentially twofold: first, this isconceptually simpler and second, the available discrete CStheory is far more developed (yet clearly paves the way for acontinuous theory see also Applications ). Having saidthis, we are then interested in undersampledsituations inwhich the number mof available measurements is muchsmaller than the dimension nof the signal f.
10 Such problemsare extremely common for a variety of reasons. For instance,the number of sensors may be limited. Or the measurementsmay be extremely expensive as in certain imaging processesvia neutron scattering. Or the sensing process may be slowso that one can only measure the object a few times as inMRI. And so circumstances raise important questions. Isaccurate reconstruction possible from m nmeasure-ments only? Is it possible to design m nsensing wave-forms to capture almost all the information about f?
