En matemáticas aplicadas y estadística , eliminación de ruido de búsqueda de bases (BPDN) se refiere a un problema de optimización matemática de la forma
dónde es un parámetro que controla la compensación entre escasez y fidelidad a la reconstrucción, es un vector de solución, es un vector de observaciones, es un transformar matriz y . Este es un ejemplo de optimización convexa y también de programación cuadrática .
Algunos autores se refieren a la eliminación de ruido de búsqueda de bases como el siguiente problema estrechamente relacionado:
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, generalmente se prefiere la formulación sin restricciones, para la cual se desarrollan los algoritmos computacionales más especializados y eficientes.
Cualquiera de los dos tipos de eliminación de ruido de búsqueda de base resuelve un problema de regularización con una compensación entre tener un pequeño residuo (haciendo cerca de en términos del error al cuadrado) y haciendo simple en el -sentido normal. Se puede considerar como una afirmación matemática de la navaja de Occam , que encuentra la explicación más simple posible (es decir, una que produce) capaz de dar cuenta de las observaciones .
Las soluciones exactas para eliminar el ruido de la búsqueda de bases son a menudo la mejor aproximación computacionalmente manejable de un sistema de ecuaciones indeterminado. [ cita requerida ] La eliminación de ruido de búsqueda de bases tiene aplicaciones potenciales en estadística (ver el método LASSO de regularización ), compresión de imágenes y detección comprimida .
Cuándo , este problema se convierte en búsqueda de bases .
La eliminación de ruido de búsqueda de bases fue introducida por Chen y Donoho en 1994, [1] en el campo del procesamiento de señales. En estadística, es bien conocido con el nombre de LASSO , después de haber sido introducido por Tibshirani en 1996.
Resolución de la búsqueda de la base denoising
El problema es un problema cuadrático convexo, por lo que puede ser resuelto por 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 in-crowd (un solucionador rápido para problemas grandes y dispersos [2] ), continuación de homotopía , 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
- ^ Chen, Shaobing; Donoho, D. (1994). "Búsqueda de base". Actas de 1994 28th Asilomar Conference on Signals, Systems and Computers . doi : 10.1109 / ACSSC.1994.471413 .
- ^ Ver Gill, Patrick R .; Wang, Albert; Molnar, Alyosha (2011). "El algoritmo en la multitud para la reducción de ruido de búsqueda de base rápida". Transacciones IEEE sobre procesamiento de señales . 59 (10): 4595–4605. doi : 10.1109 / TSP.2011.2161292 ;código de demostración MATLAB disponible [1] .
- ^ "Algoritmo hacia adelante y hacia atrás" . Archivado desde el original el 16 de febrero de 2014.
enlaces externos
- Una lista de solucionadores de BPDN en el wiki de aproximación de rango bajo y escaso .