Introduction to Compressive Sensing Aswin Sankaranarayanan system Is

Introduction to Compressive Sensing Aswin Sankaranarayanan system Is

Introduction to Compressive Sensing Aswin Sankaranarayanan system Is this system linear ?

system Is this system linear ? Given y, can we recovery x ? Under-determined problems measurements

signal measurement matrix If M < N, then the system is information lossy Image credit Graeme Pope

Image credit Sarah Bradford Super-resolution Can we increase the resolution of this image ? (Link: Depixelizing pixel art)

Under-determined problems measurements signal measurement matrix Fewer knowns than unknowns!

Under-determined problems measurements signal measurement matrix Fewer knowns than unknowns! An infinite number of solutions to such problems

Credit: Rob Fergus and Antonio Torralba Credit: Rob Fergus and Antonio Torralba Ames Room Is there anything we can do about this ?

Complete the sentences I cnt blv I m bl t rd ths sntnc. Wntr s cmng, n .. Wntr s hr Hy, I m slvng n ndr-dtrmnd lnr systm. how: ?

Complete the matrix how: ? Complete the image Model ?

Dictionary of visual words I cnt blv I m bl t rd ths sntnc. Shrlck s th vc f th drgn Hy, I m slvng n ndr-dtrmnd lnr systm. Dictionary of visual words

Image credit Graeme Pope Image credit Graeme Pope Result Studer, Baraniuk, ACHA 2012

Compressive Sensing measurements signal measurement matrix A toolset to solve under-determined systems by exploiting additional structure/models on

the signal we are trying to recover. modern sensors are linear systems!!! Sampling sampling

Can we recover the analog signal from its discrete time samples ? Nyquist Theorem An analog signal can be reconstructed perfectly from discrete samples provided you sample it densely.

The Nyquist Recipe sample faster sample denser the more you sample, the more detail is preserved The Nyquist Recipe

sample faster sample denser the more you sample, the more detail is preserved But what happens if you do not follow the Nyquist recipe ?

Credit: Rob Fergus and Antonio Torralba Image credit: Boston.com The Nyquist Recipe sample faster sample denser

the more you sample, the more detail is preserved But what happens if you do not follow the Nyquist recipe ? Breaking resolution barriers

Observing a 40 fps spinning tool with a 25 fps camera Normal Video: 25fps Compressively obtained video: 25fps Recovered Video:

2000fps Slide/Image credit: Reddy et al. 2011 Compressive Sensing Use of motion flow-models in the context of compressive video recovery 128x128 images sensed at 61x comp.

Nave frame-to-frame recovery single pixel camera CS-MUVI at 61x compression Sankaranarayanan et al. ICCP 2012, SIAM J. Imaging Sciences, 2015*

Compressive Imaging Architectures Scalable imaging architectures that deliver videos at mega-pixel resolutions in infrared visible image Chen et al. CVPR 2015, Wang et al. ICCP 2015

SWIR image A mega-pixel image obtained from a 64x64 pixel array sensor Advances in Compressive Imaging

Linear Inverse Problems Many classic problems in computer can be posed as linear inverse problems Notation Signal of interest measurement matrix

Observations measurement noise Measurement model

Problem definition: given , recover Linear Inverse Problems measurements

signal Measurement matrix has a (N-M) dimensional null-space Solution is no longer unique Sparse Signals measurements

sparse signal nonzero entries How Can It Work?

Matrix not full rank columns and so loses information in general

But we are only interested in sparse vectors Restricted Isometry Property (RIP) Preserve the structure of sparse/compressible signals K-dim subspaces

Restricted Isometry Property (RIP) RIP of order 2K implies: for all K-sparse x1 and x2 K-dim subspaces How Can It Work? Matrix

not full rank columns and so loses information in general Design so that each of its Mx2K

submatrices are full rank (RIP) How Can It Work? Matrix not full rank columns

and so loses information in general Design so that each of its Mx2K submatrices are full rank (RIP)

CS Signal Recovery Random projection not full rank Recovery problem: given find Null space Search in null space

for the sparsest (N-M)-dim hyperplane at random angle Signal Recovery Recovery: given

(ill-posed inverse problem) find (sparse) Optimization:

Convexify the optimization Candes Romberg Tao

Donoho Signal Recovery Recovery: given (ill-posed inverse problem)

find Optimization: Convexify the optimization

Polynomial time alg (linear programming) (sparse) Compressive Sensing Let.

If satisfies RIP with , Then

Best K-sparse approximation

Recently Viewed Presentations

  • Regulating Global Imbalances How Equitable and Sustainable Is

    Regulating Global Imbalances How Equitable and Sustainable Is

    By running current-account surpluses, emerging and developing countries are exporting their 'excess savings' to rich countries, and to the US in particular This is a reverse flow of capital, moving in the opposite direction to that of ODA ('capital is...
  • The Black Swan, the turkey, and the bell

    The Black Swan, the turkey, and the bell

    Turn Black Swans into white swans by. Identifying areas of vulnerability. Addressing areas of vulnerability. Continuously adapting to avoid becoming the turkey. So what can we do as a National Society to be ready for a Black Swan event?
  • Nikolay Novitskiy, Lab Exp. Psych., KU Leuven 01/30/2020

    Nikolay Novitskiy, Lab Exp. Psych., KU Leuven 01/30/2020

    Visual P1 and N1 . Omnipresent in visual ERP studies . Higher amplitude and/or shorter latencies in the contralateral hemisphere (Di Russo et al., 2002
  • MERV MCCORMACK EXECUTIVE DIRECTOR  GOOGLE: 15,000,000 entries LEADER

    MERV MCCORMACK EXECUTIVE DIRECTOR GOOGLE: 15,000,000 entries LEADER

    Peter Drucker: "Of course, success in any job is impossible without the requisite technical or vocational skills. But whereas those skills alone might have once constituted a success formula, [leaders] today must also be able to assess their strengths, weaknesses,...
  • Dealing with Opioid and Heroin Epidemic &amp; Non-Medication ...

    Dealing with Opioid and Heroin Epidemic & Non-Medication ...

    DEALING WITH OPIOID AND HEROIN EPIDEMIC & NON-MEDICATION TREATING OF PAIN ... Methadone vs Buprenophine vs XR-NTX (extended release naltrexone) Patient preference and family preference Failure of other treatments, try something new Side effects, anxious anticipation Long acting duration of...
  • Welcome to the Virtual Facial Party!

    Welcome to the Virtual Facial Party!

    Arbonne is a highly regarded premium brand with a Swiss heritage. The products are botanically based and inspired by nature. 36 year old company GREEN company. We Educate you: We Empower you with more options for your Health, Wellness and...
  • Gas Laws - University of California, Irvine

    Gas Laws - University of California, Irvine

    Reactions: Single Gas Product. Suppose that 200.0 mL of propane gas C 3 H 8. at 1.00 atm and 298K is mixed with 1.00 L of oxygen gas at the same pressure and temperature and burned to form carbon dioxide...
  • שקופית 1 - Biu

    שקופית 1 - Biu

    J Burford Fields (b December 26, 1953 Oberlin, Kansas), cited as the inventor of the electronic newsletter when, as editor of the Osborne Hawaii Users' (OHU) Newsletter, 1981-1984, he began uploading the monthly editions to the Source.