A year ago, I wrote the following entry: Are We Hitting a Ceiling ?. But then this morning, I read about Moore's law and algorithms developmemnt. Here is what happened roughly in compressed sensing:
The find of Candes, Tao, Romberg and Donoho in 2004 just dropped the NP-hard issue into the P domain. Since then, several teams and algorithms have been going at reducing the time to reconstructing spaarse signals. If we follow the numbers given in the report, it looks like if we had relied on just Moore's law, we would be about two orders of magnitudes off. I stopped at 2008, as we don't really have a good benchmark to compare all the new solvers. Another thing of interest is the appearance of GPU computing as a commodity. My rule of thumb is that GPU or multicore computing only bring about an order of magnitude improvement but I want to be convinced otherwise.
Anyway, good job y'all!