# In-crowd algorithm

Jump to: navigation, search

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:

${\displaystyle \min _{x}{\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}.}$

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

It consists of the following:

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

Since every time the in-crowd algorithm performs a global search it adds up to ${\displaystyle L}$ components to the active set, it can be a factor of ${\displaystyle 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, [1], demo MATLAB code available [2]
2. ^ See The In-Crowd Algorithm for Fast Basis Pursuit Denoising, IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [3]