Compressed Sensing: When It Works

This video provides conditions on when compressed sensing will work to reconstruct a full image from a random subsample of pixels.
Book Website: databookuw.com
Book PDF: databookuw.com/databook.pdf
These lectures follow Chapter 3 from:
"Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control" by Brunton and Kutz
Amazon: www.amazon.com/Data-Driven-Sc...
Brunton Website: eigensteve.com
This video was produced at the University of Washington

[@Seneca_dengo_dengo]

*Me, watching a video on sensing with tears in my eyes* It's ok Steve. Sometimes I feel incoherent too.

[@NowanIlfideme]

Another application that was in the news recently, as I understand, was the black hole image, where the astronomers had data from specific observatories which are semi-randomly scattered across the surface of the Earth. There they also had to select the image from probable ones that fit the model, so *probably* a bit more in-depth than shown here...

[@dapper-alien]

Also to detect gravitational waves!! They used wavelets similar to in the JPEG 2000 standard, one of the vids from the talk I watched on all that: kzbin.info/www/bejne/qn65Z2R4j6ilns0

[@siddgangadhar1234]

Prof. Brunton: I've been following your lecture series on the control Bootcamp and data-drive control for the past month or so and I absolutely adore the amount of effort you have put into them! I'm currently studying robotics at CMU and I really hope to meet you some day and shake your hand; it would be an honor!!

[@rlrfproductions]

Really appreciated the practical applications you mentioned near the end

[@freakphysics]

Incredible explanation, Steve. Thank you so much.

[@jeanbaptisteemmanuelzorg5911]

Thanks - I haven’t heard CS described so clearly before

[@aliscander92]

Great lectures! Steve, could you put all the lectures of Compressed Sensing in one playlist, please!

[@ToufiqMdHossain]

Thank you for this video professor.

[@layaltannous112]

Loved the example that was given at the end

[@sinhangho5128]

Thanks! The idea was explained very clearly!

[@Tman7855]

Steve you are the MAN!

[@fzigunov]

This is awesome!! I wonder if our eyes are also are an example of compressed sensing, as we have lower density of cones/rods away from the center of the optic disk?

[@jaeimp]

Great presentation, and superb series of videos. Highly appreciative of your generosity sharing them with everyone. Not important, but ψ would really be the inverse of the DFT matrix, is that correct?

[@kylebeggs2617]

Just when I thought these videos couldn't get better... now he is throwing jokes in them too 2:50

[@pablo_brianese]

Compressive sensing is beautiful!

[@user-qp2ps1bk3b]

thank you for the video!

[@sadattahmeed7462]

Thank you professor. This was much helpful. How do I calculate the inner product of two matrices of different dimensions (in order to test their coherence)? We usually calculate inner product of vectors, so I am not sure how to do this with matrices. The answers I found online only applies for matrices of the same dimension :(

[@alegian7934]

I like that you like the subject :)

[@swk229]

Thank you!

[@Veptis]

It's interesting to further I watch and I will watch more of the chapter. The random nature makes me question: I'd you build a camera where pixels are more randomly distributed instead of in a nice array: could you actually get the random sample much better than just taking a subsection of the signal? Is the random selection just spatial if you have two dimensional data like an image or could you also take like measurement noise as being the random factor(which is very close to actually random) for inferring the higher accuracy brightness level for pixel. Here you would think for the Luma value as a dimension, where just 0-255 is sparse and you want 0-4095 instead for example.

[@jmburin]

Prof. Brunton: how do I use this concept when my data is 4D - like a parameter that is mapped as a function of 4 independent variables (for example) and sparse in polynomial domain (instead of the frequency domain)?

[@fanalysis6734]

I'm a bit confused by x=psi*s. If the data x is sparse in the fourier basis, would psi be the DFT or the IDFT matrix?

[@jayuyares]

Is there a general approach you take if you don't know ahead of time in which basis your data will be sparse?

[@AmirKhan_KnowTech]

Great!

[@raghibshahriar8447]

question: for a x=50*50 pixels original image, guess y=250*1, s=2500*1 ,psi=2500*2500,and that means c=250*2500 but it was supposed to be 50*50 matrix as it says which pixels we are measuring of a 50*50 original image.

[@EduardoGarcia-tv2fc]

So that means that If C has certain properties it could become a filter? (in the example of 8:44 a high frequencies filter?)

[@AshishPatel-yq4xc]

Coherent lecture. Whete/ which books or articles covers this applied math in detail ?

[@ivan-nm1xn]

You might want to take a look at their book. It's linked on the description of the video.

[@dongwengan612]

How this video produced? I tried to record a video after a mirror while writing on the mirror and then use the mirror function on iphone to correct it. But it looks like I am using my left hand to write. Is this video record seperately or Mr. Bru write in left hand?

[@AhladKumar]

what do mean by saying not parallel at 9.04

[@Eigensteve]

I mean that they have a small inner product (perpendicular would have zero inner product)

[@danielsanntiago]

Does the reconstruction algorithm of the first image of a black hole can be an example of compressed sensing?

[@pabloj.gonzalez1813]

Yes, you are right. That discovery took advantage of compressed sensing. If interested, I let you a recent video of that collaboration and on what are working on now: kzbin.info/www/bejne/qWG8hIWYgs2rh9U

[@periklisdrakousis6537]

Dear Prof. . Great lecture. I do have though a question. You set C metrix as a given. It is neither a diagonial metrix nor a single column so how do you know which ones are active in a real problem that X is not known? We could not solve the y = cx. Is it just a random metrix?

[@apratimdey6118]

Generally, yes, that's the idea behind CS: you do not need to know which positions in the signal are zero, you just use an i.i.d. Gaussian matrix (for example) and you will be able to completely recover the signal if you have enough measurements.

[@osten222312]

I just now understood how much practice it takes to write like that

[@NowanIlfideme]

He mentioned in a previous comment that he flips the video, but I believe he said he can also write backwards.

[@nami1540]

So "in the order of xyz" for him means "in the rough size"? I thought this to be an exponent

[@lololamize]

I would like to know if you could use that to squeeze out more information about some existing measurements - in a sense that regards every measurement as a compressed sensing of reality. Assume you have technical problems to get a better resolution of some image like in astronomy. Assume you have some images of the sky. Can you pretend that they measure only a random subset of a higher resolution image, solve an optimisation problem and obtain more information about that higher resolution image than using traditional techniques?

[@fred0002]

Only if the measurements are incoherent. For example if you were to use a low resolution image to try to recover a higher resolution image that is sparse in the Fourier domain, it would not work because the low resolution measurement matrix is naturally coherent with the Fourier basis - it resides wholly within the lower frequency part of the Fourier basis.

[@sj.j5169]

I have a n*n matrix (x). Two or more of its rows then deleted randomly so it become a m*n matrix. For ψ I have used DCT matrix (and some other matrices) and treated random measurement matrix C (such as Gaussian Random or Bernoulli) such that Cψ satisfies RIP. Many L1 optimization methods such as CVX toolbox, OMP, ReOMP, Cosamp, ... are used to calculate sparse s. y-Cψs becomes very small (10^(-16)) while s has a few nonzero elements. However ψs is not equal to the original x. I appreciate if anyone who has done this work, gives any comment. Why this does not work?

[@flaguser4196]

me trying convex optimization: RIP

[@boyoonlee469]

RIP

[@zipWith]

hold up, is this kind of how JPEG compression works?

[@dapper-alien]

kzbin.info/www/bejne/qn65Z2R4j6ilns0

[@NoName-zn5df]

JPEG is another story, CS is a relatively new compression method of any kind of signals. Cmiiw.

[@dapper-alien]

@@NoName-zn5df JPEG 2000 uses wavelets, I think at some point they allude to using wavelets in the future for compressed sensing in the video and that is where the connection is being drawn.

[@BentoBlocs]

There are strong links here, but there's a fundamental difference. A simplified JPEG compression would be: measure the image at full resolution, take a Fourier transform, throw away the high frequencies and save the low ones. The key point, however, is that you still measure everything. In compressed sensing, you only take a number of measurements proportional to the number of frequencies you would've kept in the JPEG compression process, so you're actually taking fewer measurements.

[@starshipx1282]

Third