La búsqueda de coincidencia (MP) es un algoritmo de aproximación escasa que encuentra las proyecciones de "mejor coincidencia" de datos multidimensionales en el intervalo de un diccionario sobrecompleto (es decir, redundante). La idea básica es representar aproximadamente una señaldesde el espacio de Hilbert como una suma ponderada de un número finito de funciones (llamados átomos) tomados de . Una aproximación con los átomos tiene la forma
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/21/Matching_pursuit.png/350px-Matching_pursuit.png)
dónde es el a columna de la matriz y es el factor de ponderación escalar (amplitud) para el átomo . Normalmente, no todos los átomos dese utilizará en esta suma. En cambio, la búsqueda de emparejamiento elige los átomos de uno en uno para reducir al máximo (con avidez) el error de aproximación. Esto se logra encontrando el átomo que tiene el producto interno más alto con la señal (asumiendo que los átomos están normalizados), restando de la señal una aproximación que usa solo ese átomo, y repitiendo el proceso hasta que la señal se descompone satisfactoriamente, es decir, la norma del residual es pequeña, donde el residual después de calcular y se denota por
- .
Si converge rápidamente a cero, entonces solo se necesitan unos pocos átomos para obtener una buena aproximación a . Estas representaciones dispersas son deseables para la codificación y compresión de señales. Más precisamente, el problema de la escasez que la búsqueda de coincidencias intenta resolver aproximadamente es
dónde es el pseudo-norma (es decir, el número de elementos distintos de cero de ). En la notación anterior, las entradas distintas de cero de están . Resolver el problema de la dispersión exactamente es NP-difícil , por lo que se utilizan métodos de aproximación como MP.
Para comparar, considere la representación de la transformada de Fourier de una señal; esto se puede describir usando los términos dados anteriormente, donde el diccionario se construye a partir de funciones de base sinusoidal (el diccionario completo más pequeño posible). La principal desventaja del análisis de Fourier en el procesamiento de señales es que extrae solo las características globales de las señales y no se adapta a las señales analizadas.. Al tomar un diccionario extremadamente redundante, podemos buscar en él átomos (funciones) que mejor se adapten a una señal.
El algoritmo
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/38/Orthogonal_Matching_Pursuit.gif/500px-Orthogonal_Matching_Pursuit.gif)
Si contiene una gran cantidad de vectores, buscando la representación más escasa dees computacionalmente inaceptable para aplicaciones prácticas. En 1993, Mallat y Zhang [1] propusieron una solución codiciosa que llamaron "Persecución a juego". Para cualquier señal y cualquier diccionario , el algoritmo genera iterativamente una lista ordenada de índices de átomos y escalares de ponderación, que forman la solución subóptima al problema de la representación de señales dispersas.
Búsqueda de emparejamiento de algoritmos Señal de entrada: , diccionario con columnas normalizadas . Salida: lista de coeficientes e índices para los átomos correspondientes . Inicialización: ; ; Repetir: Encontrar con máximo producto interior ; ; ; ; Hasta la condición de parada (por ejemplo: ) regreso
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina el algoritmo y genera el siguiente valor.
En el procesamiento de señales, el concepto de búsqueda de coincidencias está relacionado con la búsqueda de proyecciones estadísticas , en las que se encuentran proyecciones "interesantes"; los que se desvían más de una distribución normal se consideran más interesantes.
Propiedades
- El algoritmo converge (es decir ) para cualquier que está en el espacio que abarca el diccionario.
- El error disminuye monótonamente.
- Como en cada paso, el residual es ortogonal al filtro seleccionado, la ecuación de conservación de energía se satisface para cada :
- .
- En el caso de que los vectores en son ortonormales, en lugar de ser redundantes, entonces MP es una forma de análisis de componentes principales
Aplicaciones
La búsqueda de coincidencias se ha aplicado a la codificación de señales, imágenes [2] y video, [3] [4] representación y reconocimiento de formas, [5] codificación de objetos 3D, [6] y en aplicaciones interdisciplinarias como el monitoreo de la salud estructural. [7] Se ha demostrado que funciona mejor que la codificación basada en DCT para velocidades de bits bajas tanto en eficiencia de codificación como en calidad de imagen. [8] El principal problema con la búsqueda de coincidencias es la complejidad computacional del codificador. En la versión básica de un algoritmo, es necesario buscar en el diccionario grande en cada iteración. Las mejoras incluyen el uso de representaciones de diccionario aproximadas y formas subóptimas de elegir la mejor coincidencia en cada iteración (extracción de átomos). [9] El algoritmo de búsqueda de coincidencias se utiliza en MP / SOFT, un método para simular la dinámica cuántica. [10]
MP también se utiliza en el aprendizaje de diccionarios . [11] [12] En este algoritmo, los átomos se aprenden de una base de datos (en general, escenas naturales como imágenes habituales) y no se eligen de diccionarios genéricos.
Extensiones
Una extensión popular de Matching Pursuit (MP) es su versión ortogonal: Orthogonal Matching Pursuit [13] [14] (OMP). La principal diferencia con MP es que después de cada paso, todos los coeficientes extraídos hasta ahora se actualizan, calculando la proyección ortogonal de la señal en el subespacio atravesado por el conjunto de átomos seleccionados hasta ahora. Esto puede conducir a resultados mejores que el MP estándar, pero requiere más cálculos. Se demostró que OMP tiene garantías de estabilidad y rendimiento bajo ciertas condiciones de isometría restringida . [15]
Extensiones como Multichannel MP [16] y Multichannel OMP [17] permiten procesar señales multicomponente. Una extensión obvia de Matching Pursuit se encuentra en múltiples posiciones y escalas, al aumentar el diccionario para que sea el de una base de ondas. Esto se puede hacer de manera eficiente utilizando el operador de convolución sin cambiar el algoritmo central. [18]
La búsqueda de coincidencias está relacionada con el campo de la detección comprimida y los investigadores de esa comunidad la han ampliado. Extensiones notables son Ortogonal Matching Pursuit (OMP), [19] Stagewise OMP (StOMP), [20] búsqueda de emparejamiento de muestreo compresivo (CoSaMP), [21] OMP generalizada (gOMP), [22] y Multipath Matching Pursuit (MMP). [23]
Ver también
Referencias
- ↑ Mallat, SG; Zhang, Z. (1993). "Búsqueda de coincidencias con diccionarios de frecuencia de tiempo" . Transacciones IEEE sobre procesamiento de señales . 1993 (12): 3397–3415. Código Bibliográfico : 1993ITSP ... 41.3397M . doi : 10.1109 / 78.258082 .
- ^ Perrinet, L. (2015). "Modelos dispersos para visión artificial" . Visión por computadora de inspiración biológica . 14 : 319–346. arXiv : 1701.06859 . doi : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.
- ^ Bergeaud, F .; Mallat, S. (1995). "Búsqueda de imágenes a juego". Proc. Congreso Internacional de Procesamiento de Imágenes . 1 : 53–56. doi : 10.1109 / ICIP.1995.529037 . ISBN 978-0-7803-3122-8.
- ^ Neff, R .; Zakhor, A. (1997). "Codificación de video de muy baja tasa de bits basada en búsquedas coincidentes" . Transacciones IEEE sobre circuitos y sistemas para tecnología de video . 7 (1): 158-171. doi : 10.1109 / 76.554427 .
- ^ Mendels, F .; Vandergheynst, P .; Thiran, JP (2006). "Hacer coincidir la representación y el reconocimiento de formas basadas en la búsqueda utilizando el espacio de escala" . Revista internacional de sistemas y tecnología de imágenes . 16 (5): 162–180. doi : 10.1002 / ima.20078 .
- ^ Tosic, I .; Frossard, P .; Vandergheynst, P. (2005). "Codificación progresiva de objetos 3D basada en descomposiciones sobrecompletas" . Transacciones IEEE sobre circuitos y sistemas para tecnología de video . 16 (11): 1338-1349. doi : 10.1109 / tcsvt.2006.883502 .
- ^ Chakraborty, Debejyo; Kovvali, Narayan; Wei, Jun; Papandreou-Suppappola, Antonia; Cochran, Douglas; Chattopadhyay, Aditi (2009). "Monitoreo de salud estructural de clasificación de daños en estructuras atornilladas utilizando técnicas de tiempo-frecuencia". Revista de estructuras y sistemas de materiales inteligentes . 20 (11): 1289–1305. doi : 10.1177 / 1045389X08100044 .
- ^ Perrinet, LU; Samuelides, M .; Thorpe, S. (2002). "Codificación de picos dispersos en una red neuronal multicapa de alimentación directa asincrónica utilizando Matching Pursuit" . Neurocomputación . 57C : 125–34. doi : 10.1016 / j.neucom.2004.01.010 .[ enlace muerto permanente ]
- ^ Lin, Jian-Liang; Hwang, Wen-Liang; Pei, Soo-Chang (2007). "Codificación de video de búsqueda de coincidencia rápida combinando aproximación de diccionario y extracción de átomo". Transacciones IEEE sobre circuitos y sistemas para tecnología de video . 17 (12): 1679-1689. CiteSeerX 10.1.1.671.9670 . doi : 10.1109 / tcsvt.2007.903120 .
- ^ Wu, Yinghua; Batista, Víctor S. (2003). "Búsqueda de coincidencias para simulaciones de procesos cuánticos" . J. Chem. Phys . 118 (15): 6720–6724. Código Bibliográfico : 2003JChPh.118.6720W . doi : 10.1063 / 1.1560636 .
- ^ Perrinet, LP (2010). "Papel de la homeostasis en el aprendizaje de representaciones dispersas" . Computación neuronal . 22 (7): 1812–1836. arXiv : 0706.3177 . doi : 10.1162 / neco.2010.05-08-795 . PMC 2929690 . PMID 20235818 .
- ^ Aharon, M .; Elad, M .; Bruckstein, AM (2006). "El K-SVD: un algoritmo para el diseño de diccionarios sobrecompletos para representación escasa". Transacciones IEEE sobre procesamiento de señales . 54 (11): 4311–4322. Código Bibliográfico : 2006ITSP ... 54.4311A . doi : 10.1109 / tsp.2006.881199 .
- ^ Pati, Y .; Rezaifar, R .; Krishnaprasad, P. (1993). "Búsqueda de correspondencia ortogonal: aproximación de función recursiva con aplicación a la descomposición de ondículas". Asilomar Conf. Sobre señales, sistemas y computación : 40–44. CiteSeerX 10.1.1.348.5735 . doi : 10.1109 / acssc.1993.342465 . ISBN 978-0-8186-4120-6.
- ^ Davis, G .; Mallat, S .; Zhang, Z. (1994). "Descomposiciones de tiempo-frecuencia adaptativas con búsquedas coincidentes". Ingeniería óptica . 33 (7): 2183. Bibcode : 1994OptEn..33.2183D . doi : 10.1117 / 12.173207 .
- ^ Ding, J .; Chen, L .; Gu, Y. (2013). "Análisis de perturbación de la búsqueda de emparejamiento ortogonal" . Transacciones IEEE sobre procesamiento de señales . 61 (2): 398–410. arXiv : 1106.3373 . doi : 10.1109 / TSP.2012.2222377 . ISSN 1941-0476 .
- ^ "Separación de fuente lineal por partes", R. Gribonval, Proc. SPIE '03, 2003
- ^ Tropp, Joel ; Gilbert, A .; Strauss, M. (2006). "Algoritmos para aproximaciones dispersas simultáneas; Parte I: búsqueda codiciosa". Señal Proc. - Aproximaciones escasas en el procesamiento de señales e imágenes . 86 (3): 572–588. doi : 10.1016 / j.sigpro.2005.05.030 .
- ^ Perrinet, Laurent U. (2015). "Modelos dispersos para visión artificial". Visión por computadora de inspiración biológica . págs. 319–346. arXiv : 1701.06859 . doi : 10.1002 / 9783527680863.ch14 . ISBN 9783527680863.
- ^ Tropp, Joel A .; Gilbert, Anna C. (2007). "Recuperación de señal de mediciones aleatorias a través de búsqueda de correspondencia ortogonal" (PDF) . Transacciones IEEE sobre teoría de la información . 53 (12): 4655–4666. doi : 10.1109 / tit.2007.909108 .
- ^ Donoho, David L .; Tsaig, Yaakov; Drori, Iddo; Jean-luc, Starck (2006). "Solución escasa de ecuaciones lineales indeterminadas por búsqueda de coincidencia ortogonal por etapas" . Transacciones IEEE sobre teoría de la información . 58 (2): 1094-1121. doi : 10.1109 / tit.2011.2173241 .
- ^ Needell, D .; Tropp, JA (2009). "CoSaMP: recuperación de señal iterativa de muestras incompletas e inexactas". Análisis Armónico Computacional y Aplicado . 26 (3): 301–321. arXiv : 0803.2392 . doi : 10.1016 / j.acha.2008.07.002 .
- ^ Wang, J .; Kwon, S .; Shim, B. (2012). "Persecución de emparejamiento ortogonal generalizada". Transacciones IEEE sobre procesamiento de señales . 60 (12): 6202–6216. arXiv : 1111.6664 . Código bibliográfico : 2012ITSP ... 60.6202J . doi : 10.1109 / TSP.2012.2218810 .
- ^ Kwon, S .; Wang, J .; Shim, B. (2014). "Persecución de emparejamiento por múltiples rutas". Transacciones IEEE sobre teoría de la información . 60 (5): 2986–3001. arXiv : 1308.4791 . doi : 10.1109 / TIT.2014.2310482 .