Iterative Algorithms in Compressive Sensing

Abstract

The field of compressive sensing is a modern field in applied mathematics which receives a lot of attention. In this thesis, we will give some insight into the iterative algorithms used in compressive sensing. We will study in particular the primal-dual algorithm, as proposed by Chambolle and Pock, and Nesterov's algorithm, NESTA. In general, the primal-dual algorithm is a more traditional algorithm than NESTA. Nesterov proved that for general convex functions, the primal-dual algorithm cannot achieve a better convergence rate than O(1/k), where k is the number of iterations, whereas Nesterov's algorithm with general convex functions achieves a convergence rate of O(1/(k^2)).