`a`
Inverse Problems and Imaging (IPI)
 

Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm

Pages: 487 - 503, Volume 3, Issue 3, August 2009      doi:10.3934/ipi.2009.3.487

 
       Abstract        Full Text (682.0K)              Related Articles       

Yingying Li - UCLA Mathematics Department, Box 951555, Los Angeles, CA 90095-1555, United States (email)
Stanley Osher - UCLA Mathematics Department, Box 951555, Los Angeles, CA 90095-1555, United States (email)

Abstract: We propose a fast algorithm for solving the Basis Pursuit problem, minu $\{|u|_1\: \Au=f\}$, which has application to compressed sensing. We design an efficient method for solving the related unconstrained problem minu $E(u) = |u|_1 + \lambda \||Au-f\||^2_2$ based on a greedy coordinate descent method. We claim that in combination with a Bregman iterative method, our algorithm will achieve a solution with speed and accuracy competitive with some of the leading methods for the basis pursuit problem.

Keywords:  Basis Pursuit, shrinkage, greedy sweep, Bregman iteration, constrained problem.
Mathematics Subject Classification:  Primary: 90C25; Secondary: 65K05.

Received: February 2009;      Revised: June 2009;      Available Online: July 2009.