Extensive work on compressed sensing has yielded a rich collection of sparse recovery algorithms, each making different tradeoffs between recovery condition and computational efficiency. In this paper, we propose a unified framework for accelerating various existing sparse recovery algorithms without sacrificing recovery guarantees by exploiting structure in the measurement matrix. Unlike fast algorithms that are specific to particular choices of measurement matrices where the columns are Fourier or wavelet filters for example, the proposed approach works on a broad range of measurement matrices that satisfy a particular property. We precisely characterize this property, which quantifies how easy it is to accelerate sparse recovery for the measurement matrix in question. We also derive the time complexity of the accelerated algorithm, which is sublinear in the signal length in each iteration. Moreover, we present experimental results on real world data that demonstrate the effectiveness of the proposed approach in practice.
Clarity: Paper is generally well written; however, certain theoretical statements (e.g. Theorem 1) are not very precise.
Originality: Contribution seems to be incremental; the proposed method seems to be a straightforward concatenation of well-known existing results in sparse recovery and nearest-neighbor search.
Significance: Unclear whether the techniques significantly advance the state of the art.
Quality: Overall, I think this is a promising direction but the idea might not have fully fleshed out.
----
Summary: 
the paper proposes a scheme to accelerate popular sparse recovery methods that rely on hard thresholding (specifically, CoSaMP and IHT, but presumably other similar methods can also be used here). The key idea is that if the measurement matrix is normalized, then the k-sparse thresholding of the gradient update can be viewed as solving a k-nearest neighbor problem. Therefore, one can presumably use fast k-NN methods instead of exact NN methods. Specifically the authors propose to use the prioritized DCI method of Li and Malik.
Pros: 
reasonable idea to use fast (sublinear) NN techniques in the k-sparse projection step.
Cons: 
* It appears that the running time improvement over the baseline IHT (which has Otilde(mn) complexity) heavily depends on the intrinsic dimensionality of A. However, the authors do not characterize this.
* The authors neglect to mention in the paper that prioritized DCI has a pre-processing time of O(mn), so the final algorithm isn't really asymptotically faster.
* I cannot parse Theorem 1 (especially, the second sentence). Is epsilon the failure probability of DCI?
* Experimental results are far too synthetic. In real-life problems k itself is big, so there may be other bottlenecks (least squares, gradient updates, etc) and not necessarily the hard thresholding step.