In-crowd algorithm
Encyclopedia
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:
where
is the observed signal, 
is the sparse signal to be recovered, 
is the expected signal under 
, and 
is the regularization parameter trading off signal fidelity and simplicity.
It consists of the following:
Since every time the in-crowd algorithm performs a global search it adds up to
components to the active set, it can be a factor of 
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.
where
is the observed signal, is the sparse signal to be recovered, is the expected signal under , and is the regularization parameter trading off signal fidelity and simplicity.It consists of the following:
- Declare
to be 0, so the unexplained residual 
- Declare the active set
to be the empty set - Calculate the usefulness
for each component in 
- If on
, no 
, terminate - Otherwise, add
components to 
- Solve basis pursuit denoising exactly on
, and throw out any component of 
whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem. - Update
- n.b. can be computed in the subproblem as all elements outside of 
are 0 - Go to step 3.
Since every time the in-crowd algorithm performs a global search it adds up to
components to the active set, it can be a factor of 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.