Project to L1 ball of specified radius
There are two typos in their algorithm.  Fixing them yields an algorithm that does work.  Here's the fixed algorithm:

Algorithm $A$, with input $x$:
 1. $c := \max(||x||_1 - \lambda,0)$
 2. $d := ||x||_0$
 3. $\tau := c/d$
 4. for each non-zero element $i$ of $x$, do:
 5.     $\qquad s := \text{sign}(x_i)$
 6.     $\qquad x_i := s \times \max(x_i - \tau,0)$
 7. return $x$

The first typo was in line 1: $\lambda - ||x||_1$ should have been $||x||_1 - \lambda$.

The second typo was in line 6: $|x_i - \tau|$ should have been $x_i - \tau$ (no absolute value).

With these changes, everything makes sense and the algorithm now seems to work correctly.  For instance:


If $||x||_1 \le \lambda$, then $A(x)=x$ (since $c=0$ in this case).
If $||x||_1 &gt; \lambda$, then $\lambda \le ||A(x)||_1 &lt; ||x||_1$ (since each $x_i$ gets mapped to something whose absolute value is smaller).
The sequence $x,A(x),A(A(x)),\dots$ converges to the desired $y$.
Convergence should typically be pretty fast.  In particular, if $\max_i |x_i|$ is not too much larger than $\lambda / ||x||_0$, then this procedure should converge exponentially fast.

(There are definitely some bad cases where this procedure converges very slowly: e.g., if $x$ has many elements whose absolute value is tiny but non-zero, and a single element whose absolute value is enormous.  In this case, the algorithm still converges, but it requires $\Theta(||x||_0)$ iterations, which might be as bad as $\Theta(d)$.  However, these bad cases are pretty rare.)