6 ms·

Compressed Sensing (2016)

30 points by chaosmachine 6y ago

hatsunearu 6y ago
This is incredible, though I'm a little confused as to why the psi matrix is IDCT and not something of a Fourier flavor...
- nine_k 6y ago
  I suppose the Fourier transform can be formulated as a cosine transform?
- timeinput 6y ago
  I thing DCT is a special case (only real) version of a Fourier transform.
  - hatsunearu 6y ago
    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?
    - timeinput 6y ago
      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
      - hatsunearu 6y ago
        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
nine_k 6y ago
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.
notajoke 6y ago
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?
- timeinput 6y ago
  It was, but the goal isn't lossless recovery it's good enough recovery either in an L1 minimizing sense, or some other criteria
- flaviu2 6y ago
  > 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.
- im3w1l-alt 6y ago
  The nyquist limit is based on recovering a general signal. If you have a-priori knowledge about the signal you can do much better.
occamrazor 6y ago
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.
ilaksh 6y ago
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).
nyanpasu64 6y ago
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.
SimplyUnknown 6y ago
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 https://onlinelibrary.wiley.com/doi/full/10.1002/mrm.21391

30 points by chaosmachine 6y ago

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

nine_k 6y ago
I suppose the Fourier transform can be formulated as a cosine transform?
timeinput 6y ago
I thing DCT is a special case (only real) version of a Fourier transform.
- hatsunearu 6y ago
  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?
  - timeinput 6y ago
    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
    - hatsunearu 6y ago
      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

nine_k 6y ago

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.

notajoke 6y ago

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?

timeinput 6y ago
It was, but the goal isn't lossless recovery it's good enough recovery either in an L1 minimizing sense, or some other criteria
flaviu2 6y ago
> 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.
im3w1l-alt 6y ago
The nyquist limit is based on recovering a general signal. If you have a-priori knowledge about the signal you can do much better.

occamrazor 6y ago

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.

ilaksh 6y ago

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).

nyanpasu64 6y ago

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.

SimplyUnknown 6y ago

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 https://onlinelibrary.wiley.com/doi/full/10.1002/mrm.21391