Búsqueda básica de eliminación de ruido

Problema de optimización matemática

En matemáticas aplicadas y estadística , la eliminación de ruido mediante búsqueda de base (BPDN) se refiere a un problema de optimización matemática de la forma

${\displaystyle \min _{x}\left({\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}\right),}$

donde es un parámetro que controla el equilibrio entre escasez y fidelidad de reconstrucción, es un vector de solución, es un vector de observaciones, es una matriz de transformación y . Este es un ejemplo de optimización convexa . ${\displaystyle \lambda }$ ${\displaystyle x}$ ${\displaystyle N\times 1}$ ${\displaystyle y}$ ${\displaystyle M\times 1}$ ${\displaystyle A}$ ${\displaystyle M\times N}$ ${\displaystyle M<N}$

Algunos autores se refieren a la eliminación de ruido por búsqueda de base como el siguiente problema estrechamente relacionado:

${\displaystyle \min _{x}\|x\|_{1}{\text{ subject to }}\|y-Ax\|_{2}^{2}\leq \delta ,}$

que, para cualquier , es equivalente a la formulación sin restricciones para algún valor (generalmente desconocido a priori ) de . Los dos problemas son bastante similares. En la práctica, la formulación sin restricciones, para la que se desarrollan los algoritmos computacionales más especializados y eficientes, suele ser la preferida. ${\displaystyle \lambda }$ ${\displaystyle \delta }$

Ambos tipos de eliminación de ruido mediante búsqueda de base resuelven un problema de regularización con un equilibrio entre tener un residuo pequeño (haciendo que se acerque a en términos del error al cuadrado) y hacerlo simple en el sentido de la norma. Se puede considerar como una declaración matemática de la navaja de Occam , que busca la explicación más simple posible (es decir, una que dé ) capaz de dar cuenta de las observaciones . ${\displaystyle y}$ ${\displaystyle Ax}$ ${\displaystyle x}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \min _{x}\|x\|_{1}}$ ${\displaystyle y}$

Las soluciones exactas para la eliminación de ruido por búsqueda de base son a menudo la mejor aproximación computacionalmente factible de un sistema de ecuaciones subdeterminado. ^{[ cita requerida ]} La eliminación de ruido por búsqueda de base tiene aplicaciones potenciales en estadística (ver el método de regularización LASSO ), compresión de imágenes y detección comprimida .

Cuando este problema se convierte en una cuestión de base . ${\displaystyle \delta =0}$

La eliminación de ruido por búsqueda de base fue introducida por Chen y Donoho en 1994 ^[1] en el campo del procesamiento de señales. En estadística, es conocida con el nombre LASSO , después de que Tibshirani la introdujera en 1996.

Solución de búsqueda de base para eliminar el ruido

El problema es un problema cuadrático convexo, por lo que puede resolverse mediante muchos métodos generales, como los métodos de puntos interiores . Para problemas muy grandes, se han propuesto muchos métodos especializados que son más rápidos que los métodos de puntos interiores.

Varios métodos populares para resolver la eliminación de ruido por búsqueda de base incluyen el algoritmo in-crowd (un solucionador rápido para problemas grandes y dispersos ^[2] ), la continuación de homotopía , la continuación de punto fijo (un caso especial del algoritmo de avance-retroceso ^[3] ) y el gradiente espectral proyectado para la minimización de L1 (que en realidad resuelve LASSO , un problema relacionado).

Referencias

1. Chen, Shaobing; Donoho, D. (1994). "Basis persecution". Actas de la 28.ª Conferencia Asilomar de 1994 sobre señales, sistemas y ordenadores . Vol. 1. págs. 41–44. doi :10.1109/ACSSC.1994.471413. ISBN 0-8186-6405-3.S2CID 96447294  .
2. Véase Gill, Patrick R.; Wang, Albert; Molnar, Alyosha (2011). "El algoritmo In-Crowd para la eliminación rápida de ruido mediante búsqueda de base". IEEE Transactions on Signal Processing . 59 (10): 4595–4605. doi :10.1109/TSP.2011.2161292. S2CID  15320645;Código MATLAB de demostración disponible [1].
3. "Algoritmo de avance y retroceso". Archivado desde el original el 16 de febrero de 2014.

Enlaces externos

• Una lista de solucionadores BPDN en la wiki de aproximación de rango disperso y bajo.