In-crowd algorithm

From Wikipedia, the free encyclopedia
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:

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 based on their usefulness
  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[2] guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.

Notes[edit]

  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]