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:
  1. Declare to be 0, so the unexplained residual
  2. Declare the active set to be the empty set
  3. Calculate the usefulness for each component in
  4. If on , no , terminate
  5. Otherwise, add components to
  6. 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.
  7. Update - n.b. can be computed in the subproblem as all elements outside of are 0
  8. 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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK