CS: Are We Hitting a Ceiling ?

This is the time of the year where one reflects on past achievements. Here is one and a question:

The figure above is from Radu Berinde and Piotr Indyk's Sequential Sparse Matching Pursuit paper, or in clearer terms (using rough numbers), the number of seconds it takes different solvers to reconstruct a vector with one million components, most of them being zeros :

Most new solvers: NESTA, APM, C-SALSA seem to have a similar speed as GPSR or are maybe an order of magnitude faster in terms of how fast one can reconstruct a sparse vector. We have gained 3 orders of magnitude over 3 years on the gold standard (?) of photography of 1 million pixels. Are we now going to see only slight incremental improvement over these results in the coming years ? I also agree that not all applications look for the same figure of merit and this is why we ought to have a benchmarking capability along the lines of the problems sets in SPARCO.