A dual split Bregman method for fast $\ell ^1$ minimization

Abstract

In this paper we propose a new algorithm for fast $\ell ^1$ minimization as frequently arising in compressed sensing. Our method is based on a split Bregman algorithm applied to the dual of the problem of minimizing $\|u\|_1 + \frac {1}{2 \alpha } \|u\|^2$ such that $u$ solves the under-determined linear system $Au=f$, which was recently investigated in the context of linearized Bregman methods. Furthermore, we provide a convergence analysis for split Bregman methods in general and show with our compressed sensing example that a split Bregman approach to the primal energy can lead to a different type of convergence than split Bregman applied to the dual, thus making the analysis of different ways to minimize the same energy interesting for a wide variety of optimization problems.