The in-crowd algorithm is a numerical method for solving

basis pursuit denoising In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form : \min_x \left(\frac \, y - Ax\, ^2_2 + \lambda \, x\, _1\right), where \lambda is a parameter that controls the trad ...

quickly; faster than any other algorithm for large, sparse problems.See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605

demo

MATLAB MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementa ...

code availabl

/ref> This algorithm is an active set method, which minimizes iteratively sub-problems of the global basis pursuit denoising:

\min_x \frac\, y-Ax\, ^2_2+\lambda\, x\, _1.

where

y

is the observed signal,

x

is the sparse signal to be recovered,

Ax

is the expected signal under

x

, and

\lambda

is the regularization parameter trading off signal fidelity and simplicity. The simplicity is here measured using the sparsity of the solution

x

, measure through its

\ell_1

-norm. The active set strategies are very efficient in this context as only few coefficient are expected to be non-zero. Thus, if they can be identified, solving the problem restricted to these coefficients yield the solution. Here, the features are greedily selected based on the absolute value of their gradient at the current estimate. Other active-set methods for the basis pursuit denoising includes BLITZ, where the selection of the active set is performed using the

duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...

of the problem, and The Feature Sign Search,Lee H, Battle A, Raina R, Ng AY. ''Efficient sparse coding algorithms''. In Advances in neural information processing systems 2007 (pp. 801-808)

/ref> where the features are included based on the estimate of their sign.

Algorithm

It consists of the following: # Declare

x

to be 0, so the unexplained residual

r = y

# Declare the active set

I

to be the empty set, and

I^c

to be its complement (the inactive set) # Calculate the usefulness

u_j = ,  \langle r A_j \rangle ,

for each component in

I^c

# If on

I^c

, no

u_j > \lambda

, terminate # Otherwise, add

L \approx 25

components to

I

based on their usefulness # 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. # Update

r = y - Ax

- n.b. can be computed in the subproblem as all elements outside of

I

are 0 # 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.

Notes

Optimization algorithms and methods {{Mathapplied-stub