Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What algorithm blows your mind? (Reddit compsci)

reddit.com

Post reply on HN
Print view View original

61–70 of 71 posts

Re: What algorithm blows your mind? (Reddit compsci)

#61

Post by nuitblanche »

thalur wrote: post #13
jefffoster wrote: post #10

Compressed Sensing is exciting - using a sequence of low res images to obtain a higher resolution sample. It was discussed in Wired ( http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 ) together with a compelling example (minimizing the time of a young patient in an MRI machine)

That sounds far too good to be true. I guess if you don't care about the fine details then its a decent technique, but to take the MRI example, what if the thing that was wrong was only visible in those small details?

The Wired articles gave the wrong impression. It gave an example of inpainting (the Obama picture) that is NOT compressed sensing. Compressed sensing on the other hand can be applied directly to MRI because the MRI machine actually picks up all the spatial information. It samples randomly in the Fourier domain thereby having access to all the spatial information needed to fully reconstruct an image. It used to be that the reconstruction algorithms were not that good before (they relied on SVD/least square). Candes, Tao, Romberg and Donoho then published papers showing that the reconstruction could be done in a totally different way AND it was exact. With these new reconstruction algorithms something like MRI data is acquired in a much more efficient manner than four years because of compressed sensing.

For mor eon the controversy with the Wired article: http://nuit-blanche.blogspot.com/2010/05/compressed-sensing-... http://nuit-blanche.blogspot.com/2010/03/why-compressed-sens...

The new reconstruction solvers: https://sites.google.com/site/igorcarron2/cs#reconstruction

Hardware that are implementing compressive sensing: https://sites.google.com/site/igorcarron2/compressedsensingh...

Re: What algorithm blows your mind? (Reddit compsci)

#63

Post by nuitblanche »

Retric wrote: post #50
cdavid wrote: post #41

Earlier quoted context omitted.

There are other things which sound too good to be true and yet are true (the sampling theorem for exact reconstruction of periodic signals is pretty unintuitive IMO, and even more "magic")

Filling in missing information with a reasonable guess is vary different from having accurate information. Looking at a low res impressionist painting you are going to fill in based on reasonable estimates for the real world not what is actually there.

In compressed sensing, we don't do guesses. Guesses are reserved for inpainting.

Re: What algorithm blows your mind? (Reddit compsci)

#64

Post by nuitblanche »

anamax wrote: post #43
jefffoster wrote: post #10

Compressed Sensing is exciting - using a sequence of low res images to obtain a higher resolution sample. It was discussed in Wired ( http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 ) together with a compelling example (minimizing the time of a young patient in an MRI machine)

Compressed sensing was the subject of a recent talk which can be viewed at ee380.stanford.edu as well as via itunes and youtube.

I ahve compiled a long list of online talks here: https://sites.google.com/site/igorcarron2/csvideos

start from the bottom.

Re: What algorithm blows your mind? (Reddit compsci)

#65

Post by [deleted] »

RiderOfGiraffes wrote: post #48
jules wrote: post #44

Earlier quoted context omitted.

Why are high dimensional spheres spikey?

Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore. I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful. Please. Thanks.

[deleted]

Re: What algorithm blows your mind? (Reddit compsci)

#66

Post by [deleted] »

jules wrote: post #44
RiderOfGiraffes wrote: post #33

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9... High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

Why are high dimensional spheres spikey?

[deleted]

Re: What algorithm blows your mind? (Reddit compsci)

#67

Post by RiderOfGiraffes »

jules wrote: post #44
RiderOfGiraffes wrote: post #33

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9... High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

Why are high dimensional spheres spikey?

Now written up here:

http://news.ycombinator.com/item?id=1846682

Re: What algorithm blows your mind? (Reddit compsci)

#68

Post by RiderOfGiraffes »

jules wrote: post #44
RiderOfGiraffes wrote: post #33

Lenstra-Lenstra-Lovasz: http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9... High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."

Why are high dimensional spheres spikey?

In response to requests, the write-up is now available here:

http://news.ycombinator.com/item?id=1846682

Re: What algorithm blows your mind? (Reddit compsci)

#69

Post by cosmicray »

while looking thru some 360 assembler code one day, I came across this ...

XC loc1,loc2

XC loc2,loc1

XC loc1,loc2

It took a day of head scratching, and various notes, before I understood that it was a clever way of exchanging the contents of two storage locations, without a third intermediate location. Three consecutive exclusive-Ors.

Re: What algorithm blows your mind? (Reddit compsci)

#70

Post by rdtsc »

gamache wrote: post #29

Singular value decomposition. It continually amazes me how many problems -- from noise reduction to Netflix prediction -- SVD can be usefully applied to. http://en.wikipedia.org/wiki/Singular_value_decomposition

I still do not completely understand it. I see the math, but I see it as symbols that I can memorize, rather than something intuitive (like when I see a moving cursor through a state tree during a binary search for instance).
Post reply on HN