Algoritmo de multitudes

El algoritmo in-crowd es un método numérico para resolver la eliminación de ruido de búsqueda de base rápidamente; más rápido que cualquier otro algoritmo para problemas grandes y dispersos. ^[1] Este algoritmo es un método de conjunto activo , que minimiza de manera iterativa los subproblemas de la eliminación de ruido de búsqueda de base global:

${\displaystyle \min _{x}{\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}.}$

donde es la señal observada, es la señal dispersa que se recuperará, es la señal esperada bajo , y es el parámetro de regularización que equilibra la fidelidad de la señal y la simplicidad. La simplicidad se mide aquí utilizando la escasez de la solución , medida a través de su -norma. Las estrategias de conjunto activo son muy eficientes en este contexto, ya que solo se espera que unos pocos coeficientes sean distintos de cero. Por lo tanto, si se pueden identificar, resolver el problema restringido a estos coeficientes produce la solución. Aquí, las características se seleccionan con avidez en función del valor absoluto de su gradiente en la estimación actual. ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle Ax}$ ${\displaystyle x}$ ${\displaystyle \lambda }$ ${\displaystyle x}$ ${\displaystyle \ell _{1}}$

Otros métodos de conjunto activo para la eliminación de ruido mediante búsqueda de base incluyen BLITZ, ^[2] donde la selección del conjunto activo se realiza utilizando la brecha de dualidad del problema, y ​​​​The Feature Sign Search, ^[3] donde las características se incluyen en función de la estimación de su signo.

Algoritmo

Se compone de lo siguiente:

1. Declara que es 0, por lo que el residuo inexplicado ${\displaystyle x}$ ${\displaystyle r=y}$
2. Declarar que el conjunto activo es el conjunto vacío y su complemento (el conjunto inactivo) ${\displaystyle I}$ ${\displaystyle I^{c}}$
3. Calcular la utilidad de cada componente en ${\displaystyle u_{j}=|\langle rA_{j}\rangle |}$ ${\displaystyle I^{c}}$
4. Si está activado , no , terminar ${\displaystyle I^{c}}$ ${\displaystyle u_{j}>\lambda }$
5. De lo contrario, agregue componentes según su utilidad. ${\displaystyle L\approx 25}$ ${\displaystyle I}$
6. Resuelva la eliminación de ruido de búsqueda de base exactamente en , y elimine cualquier componente cuyo valor alcance exactamente 0. Este problema es denso, por lo que las técnicas de programación cuadrática funcionan muy bien para este subproblema. ${\displaystyle I}$ ${\displaystyle I}$
7. Actualización : nb se puede calcular en el subproblema ya que todos los elementos fuera de son 0 ${\displaystyle r=y-Ax}$ ${\displaystyle I}$
8. Vaya al paso 3.

Dado que cada vez que el algoritmo de grupo interno realiza una búsqueda global, suma componentes al conjunto activo, puede ser un factor de más rápido que los mejores algoritmos alternativos cuando esta búsqueda es computacionalmente costosa. Un teorema ^[1] garantiza que se alcanza el óptimo global a pesar de la naturaleza de muchos a la vez del algoritmo de grupo interno. ${\displaystyle L}$ ${\displaystyle L}$

Notas

1. Véase The In-Crowd Algorithm for Fast Basis Pursuit Denoising , IEEE Trans Sig Proc 59 (10), 1 de octubre de 2011, págs. 4595-4605, [1], código de demostración de MATLAB disponible [2]
2. Johnson T, Guestrin C. Blitz: Un metaalgoritmo basado en principios para escalar la optimización dispersa . En actas de la Conferencia Internacional sobre Aprendizaje Automático (ICML) 2015 (pp. 1171-1179).([3])
3. Lee H, Battle A, Raina R, Ng AY. Algoritmos de codificación dispersa eficientes . En Avances en sistemas de procesamiento de información neuronal 2007 (pp. 801-808). [4]