Persecución básica para eliminar el ruido.

Problema de optimización matemática

En matemáticas aplicadas y estadística , la eliminación de ruido de búsqueda de bases (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 de búsqueda de bases como el siguiente problema estrechamente relacionado:

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

que, para cualquier valor dado , 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, suele preferirse la formulación sin restricciones, para la cual se desarrollan los algoritmos computacionales más especializados y eficientes. ${\displaystyle \lambda }$ ${\displaystyle \delta }$

Cualquiera de los tipos de eliminación de ruido de búsqueda de bases resuelve un problema de regularización con una compensación entre tener un residuo pequeño ( cerca en términos del error al cuadrado) y simplificar en el sentido de la norma. Puede considerarse como un enunciado matemático de la navaja de Occam , encontrar la explicación más simple posible (es decir, una que rinda ) 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 de búsqueda de bases son a menudo la mejor aproximación computacionalmente manejable de un sistema de ecuaciones indeterminado. ^{[ cita necesaria ]} La eliminación de ruido de búsqueda de bases tiene aplicaciones potenciales en estadística (consulte el método de regularización LASSO ), compresión de imágenes y detección comprimida .

Cuando , este problema se convierte en búsqueda de base . ${\displaystyle \delta =0}$

Chen y Donoho introdujeron la eliminación de ruido de búsqueda básica en 1994, ^[1] en el campo del procesamiento de señales. En estadística, es muy conocido con el nombre de LASSO , tras ser introducido por Tibshirani en 1996.

Resolver la búsqueda de base para eliminar el ruido.

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

Varios métodos populares para resolver la eliminación de ruido de búsqueda de bases incluyen el algoritmo en multitud (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 hacia adelante-hacia atrás ^[3] ) y gradiente espectral proyectado para la minimización de L1 (que en realidad resuelve LASSO , un problema relacionado).

Referencias

1. Chen, Shaobing; Donoho, D. (1994). "Búsqueda de bases". Actas de la 28ª Conferencia de Asilomar sobre señales, sistemas y computadoras de 1994 . 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, Alberto; Molnar, Aliosha (2011). "El algoritmo entre multitudes para la eliminación de ruido de búsqueda rápida". Transacciones IEEE sobre procesamiento de señales . 59 (10): 4595–4605. doi :10.1109/TSP.2011.2161292. S2CID  15320645;Código de demostración MATLAB disponible [1].
3. "Algoritmo de avance hacia atrás". Archivado desde el original el 16 de febrero de 2014.

enlaces externos

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