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:
- 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 based on their usefulness
- 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.
|This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.|