Compressive sensing (CS) is an exciting new model for signal processing. The author presents a new reconstruction algorithm, which is the main thrust of current CS research.
What is CS? Take a sparse vector x with n components and a fixed m × n measurement matrix A, where m << n. The question is how well one can reconstruct x from the product y = Ax. Directly finding a sparse x consistent with Ax is infeasible, but in applications, it often works out that the computationally easier 1 or 2 minimization does the job.
The excitement is in applications. Take x to be a vector of Fourier, wavelet, or other coefficients. Even when x is not sparse, in practice it is often nearly so. Now, Ax represents a significantly compressed version of x, and the abstract question translates into exact reconstruction of x from relatively few measurements.
The author outlines several known iterative methods for estimating x. These require some kind of thresholding to preserve sparsity. New here is the hard thresholding pursuit method, a hybrid of iterative hard thresholding and matching pursuit. The paper notes the advantages of each method; tests the algorithm using random Bernoulli and Gaussian matrices A (which are pretty standard in CS) and random vectors x; and finds improved performance.
The paper, while intended for experts, is well written enough for newcomers. My major disappointment is that the author did not test the method against “natural” data like images. However, random data is generally harder, so perhaps this omission is excusable.