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 1 2 ∥ y − A x ∥ 2 2 + λ ∥ x ∥ 1 .

where y is the observed signal, x is the sparse signal to be recovered, A x is the expected signal under x , and λ 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 = | ⟨ r A j ⟩ | for each component in I c
4. If on I c , no u j > λ , terminate
5. Otherwise, add L ≈ 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 − A x - 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.