In-crowd algorithm

The in-crowd algorithm is a numerical method for solving basis pursuit denoising quickly; faster than any other algorithm for large, sparse problems.^[1] Basis pursuit denoising is the following optimization problem:

$\min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1.$

where $y$ is the observed signal, $x$ is the sparse signal to be recovered, $Ax$ is the expected signal under $x$, and $\lambda$ is the regularization parameter trading off signal fidelity and simplicity.

It consists of the following:

1. Declare $x$ to be 0, so the unexplained residual $r = y$
2. Declare the active set $I$ to be the empty set
3. Calculate the usefulness $u_j = | \langle r A_j \rangle |$ for each component in $I^c$
4. If on $I^c$, no $u_j > \lambda$, terminate
5. Otherwise, add $L \approx 25$ components to $I$ based on their usefulness
6. Solve basis pursuit denoising exactly on $I$, and throw out any component of $I$ whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem.
7. Update $r = y - Ax$ - n.b. can be computed in the subproblem as all elements outside of $I$ are 0
8. Go to step 3.

Since every time the in-crowd algorithm performs a global search it adds up to $L$ components to the active set, it can be a factor of $L$ faster than the best alternative algorithms when this search is computationally expensive. A theorem^[2] guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.

Notes

1. See The In-Crowd Algorithm for Fast Basis Pursuit Denoising, IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, , demo MATLAB code available
2. See The In-Crowd Algorithm for Fast Basis Pursuit Denoising, IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605,