Iterative hard thresholding for compressed sensing (Q734323)

In the presented paper, it is shown that one of the previously by the authors developed iterative hard thresholding algorithms (termed IHTs) has similar performance guarantees to those of Compressed Sampling Matching Pursuit. Section 2 of the paper starts with a definition of sparse signal models and a statement of the compressed sensing problem. In Section 3, an iterative hard thresholding algorithm is discussed. The rest of the paper shows that this algorithm is able to recover, with high accuracy, signals from compressed sensing observations. This result is formally stated in the theorems of the first subsection of Section 4. The rest of Section 4 is devoted to the proof of the theorems. In fact, the derived result is near-optimal as shown in Section 5. Section 6 takes a closer look at a stopping criterion for the algorithm, which guarantees certain estimation accuracy. The results of the paper are similar to those for the Compressed Sampling Matching Pursuit algorithm and a more detailed comparison is given in Section 7. However, as discussed in Section 8, uniform guarantees are not the only consideration and in practice marked differences in the average performance of different methods are apparent. For many small problems, the restricted isometry property of random matrices is often too large to explain the behavior of the different methods. Furthermore, it has long been observed that the distribution of the magnitude of the non-zero coefficients also has an important influence on the performance of different methods. Whilst the theoretical guarantees derived in the presented and similar papers are important to understand the behavior of an algorithm, it is also clear that other facts have to be taken into account in order to predict the typical performance of algorithms in many practical situations.