  We propose a novel differentiable reformulation of the linearly-constrained
$\ell_1$ minimization problem, also known as the basis pursuit problem. The
reformulation is inspired by the Laplacian paradigm of network theory and leads
to a new family of gradient-based methods for the solution of $\ell_1$
minimization problems. We analyze the iteration complexity of a natural
solution approach to the reformulation, based on a multiplicative weights
update scheme, as well as the iteration complexity of an accelerated gradient
scheme. The results can be seen as bounds on the complexity of iteratively
reweighted least squares (IRLS) type methods of basis pursuit.
