# Compressed Sensing Tobias Bertelsen Malay Singh Hirak Sarkar Nirandika Wanigasekara

Yamilet Serrano Llerena Parvathy Sudhir 3 + Introduction Mobashir Mohammad + The Data Deluge

Sensors: Better Stronger Faster Challenge: Exponentially increasing amounts of data Audio, Image, Video, Weather, Global scale acquisition

4 + 5 + Sensing by Sampling Sampl e N 6 +

Sensing by Sampling (2) N >> L Sampl e N Compress 7 L JPEG N >> L

L Decompress N + Compression: Toy Example 8 + Discrete Cosine Transformation Transformatio n

9 + Motivation Why go to so much effort to acquire all the data when most of the what we get will be thrown away? Cant we just directly measure the part that wont end up being thrown away? 10 Donoho

2004 11 Outline + Compressed Sensing Constructing Sparse Signal Recovery Convex Optimization Algorithm

Applications Summary Future Work 12 + Compressed Sensing Aditya Kulkarni + What is compressed sensing? A paradigm shift that allows for the saving of time and space during the process of signal acquisition, while

still allowing near perfect signal recovery when the signal is needed Analog Audio Signal High-rate LowNyquist rate CompressedCompression rate Sampling Sensing (e.g. MP3) 13 + Sparsity

The concept that most signals in our natural world are sparse a. Original image c. Image reconstructed by discarding the zero coefficients 14 + How It Works 15 + Dimensionality Reduction Problem

= I. Measure II. Construct sensing matrix III. Reconstruct 16 + Sampling 17 measurements

=I sparse signal nonzero entries + 18

measurements sparse signal nonzero entries <

+ 19 1 1 nonzero entries

nonzero entries + Sparsity The concept that most signals in our natural world are sparse a. Original image c. Image reconstructed by discarding the zero coefficients 20

+ 21

1 1 22 + Constructing Tobias Bertelsen + RIP - Restricted Isometry Property A matrix satisfies the RIP of order K if there exists a such that:

holds for all -sparse vectors and Or equally holds for all 2K-sparse vectors The distance between two points are approximately the same in the signal-space and measure-space 23 + RIP - Restricted Isometry Property 24

RIP ensures that measurement error does not blow up Image: http://www.brainshark.com/brainshark/brainshark.net/portal/title.aspx? pid=zCgzXgcEKz0z0 + Randomized algorithm 1. Pick a sufficiently high 2. Fill randomly according to some random

distribution Which How distribution? to pick ? What is the probability of satisfying RIP? 25 + Sub-Gaussian distribution

Defined by Tails decay at least as fast as the Gaussian E.g.: The Gaussian distribution, any bounded distribution Satisfies the concentration of measure property (not RIP): For any vector and a matrix with sub-Gaussian entries, there

exists a such that holds with exponentially high probability where is a constant only dependent on 26 + Johnson-Lidenstrauss Lemma Generalization to a discrete set of vectors For any vector the magnitude are preserved with:

For all P vectors the magnitudes are preserved with: To account for this must grow with 27 + Generalizing to RIP RIP:

We want to approximate all -sparse vectors with unit vectors The space of all -sparse vectors is made up of -dimensional subspaces one for each position of non-zero entries in We sample points on the unit-sphere of each subspace 28 + Randomized algorithm

Use sub-Gaussian distribution Pick Exponentially Formal high probability of RIP proofs and specific formulas for constants exists 29

+ Sparse in another base We assumed the signal itself was sparse What if the signal is sparse in another base, i.e. is sparse. must have the RIP As long as is an orthogonal basis, the random construction works.

30 + Characteristics of Random Stable Universal

Robust to noise, since it satisfies RIP Works with any orthogonal basis Democratic Any element in has equal importance Robust to data loss Other Methods

Random Fourier submatrix Fast JL transform 31 32 + Sparse Signal Recovery Malay Singh +

The Hyperplane of 33 + 34 Norms for N dimensional vector x = Unit Sphere of norm {

1 ( | | ) =1 if >0 | ()| if =0 max | | if = =1,2 , , Unit Sphere of

norm Unit Sphere of norm Unit Sphere of quasinorm + 35 Balls in higher dimensions + How about minimization

But the problem is nonconvex and very hard to solve 36 + We do the minimization We are minimizing the Euclidean distance. But the arbitrary angle of hyperplane matters 37 + What if we convexify the to

38 + Issues with minimization is non-convex and minimization is potentially very difficult to solve. We convexify the problem by replacing by . This leads us to Minimization.

Minimizing results in small values in some dimensions but not necessarily zero. provides a better result because in its solution most of the dimensions are zero. 39 40 + Convex Optimization Hirak Sarkar

+ What it is all about Find a sparse representation Here Two and Moreover ways to solve (P1) where is a measure of sparseness

(P2) 41 + How to chose and Take the simplest convex function A simple

Final unconstrained version 42 + Versions of the same problem 43 + Formalize Nature of

Convex Differentiable Basic Intuition Take an arbitrary Calculate Use the shrinkage operator

Make corrections and iterate 44 + 45 Shrinkage operator We define the shrinkage operator as follows

+ 46 Algorithm Input: Matrix ignal measurement parameter sequence Output: Signal estimate Initialization: + Performance

For closed and convex function any the algorithm converges within finite steps For and a moderate number of iterations needed is less than 5 47 48 + Single Pixel Camera Nirandika Wanigasekara

+ Single Pixel Camera What is a single pixel camera An optical computer sequentially measures the Directly acquires random linear measurements without first

collecting the pixel values 49 + Single Pixel CameraArchitecture 50 + Single Pixel Camera- DMD Array Digital Micro mirror Device

A type of a reflective spatial light modulator Selectively redirects parts of the light beam Consisting of an array of N tiny mirrors Each mirror can be positioned in one of two states(+/10 degrees) Orients the light towards or away from the second lens

51 + Single Pixel CameraArchitecture 52 + Single Pixel CameraPhotodiode Find the focal point of the second lens Place a photodiode at this point

Measure the output voltage of the photodiode The voltage equals , which is the inner product between and the desired image . 53 + Single Pixel CameraArchitecture 54

+ 55 Single Pixel Camerameasurements A random number generator (RNG) sets the mirror orientations in a pseudorandom 1/0 pattern Repeats the above process for times Obtains the measurement vector and

Now we can construct the system in the j + Single Pixel CameraArchitecture 56

+ Sample image reconstructions 256*256 conventional image of black and white R Image reconstructed from How can we improve the reconstruction further? M = 1300 256 256 57

256 256 256256 M = 1300 + Utility 58 This device is useful when measurements are expensive

Low Light Imager Conventional Photomultiplier tube/ avalanche photodiode Single Pixel Camera Single photomultiplier Original 800 1600 65536 pixels from 6600

+ Utility CS Infrared Imager IR photodiode CS Hyperspectral Imager 59 60

+ Compressed Sensing MRI Yamilet Serrano Llerena + Compressed Sensing MRI 61 Magnetic Resonance Imaging (MRI) Essential medical imaging tool with slow data acquisition process. Applying Compressed Sensing

(CS) to MRI offers that: We can send much less information reducing the scanned time We are still able to reconstruct the image in based on they are compressible + Compressed Sensing MRI Scan Process 62

+ Scan Process Signal Received 63 K-space Space where MRI data is stored K-space trajectories: K-space is 2D Fourier transform of the MR image

+ In the context of CS : 64 y= x Is depends on the acquisition device Is the Fourier Basis Is an M x N matrix

y: Is the measured k-space data from the scanner x: + Recall ... 65 The heart of CS is the assumption that x has a sparse

representation. Medical Images are naturally compressible by sparse coding in an appropriate transform domain (e.g. Wavelet Transform) Not significant + Compressed Sensing MRI Scan Process 66 + Image Reconstruction

CS uses only a fraction of the MRI data to reconstruct image. 67 + Image Reconstruction 68 + Benefits of CS w.r.t Resonance Allow for faster image acquisition (essential for cardiac/ pediatric imaging)

Using same amount of k-space data, CS can obtain higher Resolution Images. 69 70 + Summary Parvathy Sudhir Pillai + Summary

Motivation Data deluge Directly acquiring useful part of the signal Key idea: Reduce the number of samples

Implications Dimensionality reduction Low redundancy and wastage 71 + Open Problems

72 Good sensing matrices Adaptive? Deterministic? Nonlinear compressed sensing Numerical algorithms

Hardware design Intensity (x) Coefficients () Phase () + Impact Data generation and storage Conceptual achievements

Exploit minimal complexity efficiently Information theory framework Numerous application areas Legacy - Trans disciplinary research 73

Information Hardware C S Software Complexity + Ongoing Research New mathematical framework for evaluating CS schemes

Spectrum sensing Not so optimal Data transmission - wireless sensors (EKG) to wired base stations. 90% power savings 74

+ In the news 75 + References Emmanuel Candes, Compressive Sensing - A 25 Minute Tour, First EU-US Frontiers of Engineering Symposium, Cambridge, September 2010 David Schneider, Camera Chip Makes Already-Compressed Images, IEEE Spectrum, Feb 2013

T.Strohmer. Measure what should be measured: Progress and Challenges in Compressive Sensing. IEEE Signal Processing Letters, vol.19(12): pp.887-893, 2012. Larry Hardesty, Toward practical compressed sensing, MIT news, Feb 2013 Tao Hu and Mitya Chklovvskii, Reconstruction of Sparse Circuits Using Multi-neuronal Excitation (RESCUME), Advances in Neural Information Processing Systems, 2009

http://inviewcorp.com/technology/compressive-sensing/ http://ge.geglobalresearch.com/blog/the-beauty-of-compressive-sensing/ http://www.worldindustrialreporter.com/bell-labs-create-lensless-camera-th rough-compressive-sensing-technique/ http://www.lablanche-and-co.com/ 76 + 77 THANK YOU