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. 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 rA_{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 guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.