A TIME CONTINUATION BASED FAST APPROXIMATE ALGORITHM FOR COMPRESSED SENSING RELATED OPTIMIZATION

摘要

In this paper we introduce a fast approximate algorithm to optimize an augmented version of the Basis Pursuit problem and subsequently find the solution to the compressed sensing problem. Our methodology is to first solve the Lagrangian dual formulation of the problem and then use the result to find an approximate solution to the primal problem. Although we emphasize that our algorithm finds an approximate solution, numerical experiments show that our algorithm perfectly recovers the solution when the solution is relatively sparse with respect to the number of measurements. In these scenarios, the recovery is extremely fast compared to other available methods. Numerical experiments also demonstrate that the algorithm exhibits a sharp phase transition in success rate of recovery of the solution to compressed sensing problems as sparsity of solution varies. The algorithm proposed here is parameter free (except a tolerance parameter due to numerical machine precision), and very easy to implement.