Electromigrated nanogaps: Difference between revisions
en>Antony-22 m cat sort |
en>Antony-22 m cat |
||
| Line 1: | Line 1: | ||
The '''in-crowd algorithm''' is a numerical method for solving [[basis pursuit denoising]] quickly; faster than any other algorithm for large, sparse problems.<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245], demo [[MATLAB]] code available [http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip]</ref> Basis pursuit denoising is the following optimization problem: | |||
<math>\min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1.</math> | |||
where <math>y</math> is the observed signal, <math>x</math> is the sparse signal to be recovered, <math>Ax</math> is the expected signal under <math>x</math>, and <math>\lambda</math> is the regularization parameter trading off signal fidelity and simplicity. | |||
It consists of the following: | |||
# Declare <math>x</math> to be 0, so the unexplained residual <math> r = y</math> | |||
# Declare the active set <math>I</math> to be the empty set | |||
# Calculate the usefulness <math>u_j = | \langle r A_j \rangle | </math> for each component in <math>I^c</math> | |||
# If on <math>I^c</math>, no <math>u_j > \lambda</math>, terminate | |||
# Otherwise, add <math>L \approx 25</math> components to <math>I</math> | |||
# Solve basis pursuit denoising exactly on <math>I</math>, and throw out any component of <math>I</math> whose value attains exactly 0. This problem is dense, so quadratic programming techniques work very well for this sub problem. | |||
# Update <math> r = y - Ax</math> - n.b. can be computed in the subproblem as all elements outside of <math>I</math> are 0 | |||
# Go to step 3. | |||
Since every time the in-crowd algorithm performs a global search it adds up to <math>L</math> components to the active set, it can be a factor of <math>L</math> faster than the best alternative algorithms when this search is computationally expensive. A theorem<ref>See ''The In-Crowd Algorithm for Fast Basis Pursuit Denoising'', IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5940245]</ref> guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm. | |||
==Notes== | |||
{{reflist}} | |||
[[Category:Mathematical optimization]] | |||
{{Mathapplied-stub}} | |||
Revision as of 22:18, 3 August 2013
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:
- 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[2] guarantees that the global optimum is reached in spite of the many-at-a-time nature of the in-crowd algorithm.
Notes
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.