Compressed Sensing (2016) | Hacker News Reader

Compressed Sensing (2016)

pyrunner.com

30 pointschaosmachine15 comments

This is a Big Deal in MRI image reconstruction. As the MR scanner samples in the frequency domain (or k-space, in the nomenclature) one can significantly accelarete MR exams by using C/S reconstruction. The only restriction is that the sampling mask is random. This causes incoherent artifacts in image space, which can be removed by denoising the image in a sparse domain, e.g. wavelets. See also the work by Lustig et al. https://onlinelibrary.wiley.com/doi/full/10.1002/mrm.21391

How does the audio example square with nyquist limit? Basically you can get it back, mostly, with some clever tricks, but I’m not crazy thinking that the original was decimated beyond lossless recovery right?

It was, but the goal isn't lossless recovery it's good enough recovery either in an L1 minimizing sense, or some other criteria

> Compressed sensing in this context is made possible by the fact that the signal’s frequency content is highly sparse.

The fact that the signal is so regular is what makes this possible. You're sampling the same signal many times, far more than twice the frequency of the highest frequency.

If the signal's frequencies changed over time or if there were more frequencies in the signal, this wouldn't work or would require far more data.

The nyquist limit is based on recovering a general signal. If you have a-priori knowledge about the signal you can do much better.

I think the glitchy colors arise because the image overflows the 0..255 range of uint8 which is usually used for digital images. The values should be clamped when converting from float to int.

JPEG compression works in a similar way: the image is segmented in blocks, each of them is transformed to frequency domain via DCT and then the frequency coefficients are quantized, or discarded if small. The rules for the last step are optimized to minimize human perception of discrepancy between original and compressed image.

What compressed sensing shows is that even a very rough optimization step, completion unaware of contents and human perception, can give worse but comparable results.

Supposedly Helm.ai is using compressed sensing in some way for self-driving car vision. According to an article/interview I saw.

The way it was mentioned made it sound like the compression could be very smart somehow in terms of useful feature extraction. Although I was probably just reading too much into a fluff-piece. Maybe they are just using it to make it easier to get real-time processing (via normal deep learning techniques).

Finally, a hands-on guide to implementing the "enhance this image" command from SF movies! Sort of.

Also, an important observation about approximation, outliers, and deviation measures.

This is incredible, though I'm a little confused as to why the psi matrix is IDCT and not something of a Fourier flavor...

I suppose the Fourier transform can be formulated as a cosine transform?

I thing DCT is a special case (only real) version of a Fourier transform.

Well, kind of. The FT on a real signal gives you a symmetric spectrum that is complex.

IDK seems kinda weird, there's a lot of handwavey stuff that I don't fully understand.

And I'm also wondering what the significance of the frequency domain is--can you generalize compressed sensing with other transforms as well?

Definitely. JPEG2000 uses a wavelet transform instead of the DCT to achieve similar goals.

One way to think of it is your transforming to some other basis. You could do something similar with any vector base change where you go from a dense representation to a sparse one. Think of things like an eigen decomposition where most of the eigenvalues are small or zero and can be ignored

Yeah. do they like make up tailored wavelet transforms just to get it nice and sparse?

Or does it have to be sparse? I thought it just has to have a low L1 norm

Reply on news.ycombinator.com