búsqueda coincidente

Algoritmo de datos multidimensionales

Una señal y su representación en ondas. Cada píxel en el mapa de calor (arriba) representa un átomo (una ondícula centrada en el tiempo según la posición horizontal y con una frecuencia correspondiente a la altura). El color del píxel proporciona el producto interno del átomo wavelet correspondiente con la señal (abajo). La búsqueda de correspondencia debería representar la señal mediante unos pocos átomos, como por ejemplo los tres en el centro de las elipses claramente visibles.

La búsqueda de coincidencias (MP) es un algoritmo de aproximación escasa que encuentra las proyecciones "mejor coincidentes" de datos multidimensionales en el lapso de un diccionario demasiado completo (es decir, redundante) . La idea básica es representar aproximadamente una señal del espacio de Hilbert como una suma ponderada de un número finito de funciones (llamadas átomos) tomadas de . Una aproximación con átomos tiene la forma ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle H}$ ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle D}$ ${\displaystyle N}$

${\displaystyle f(t)\approx {\hat {f}}_{N}(t):=\sum _{n=1}^{N}a_{n}g_{\gamma _{n}}(t)}$

donde es la enésima columna de la matriz y es el factor de ponderación escalar (amplitud) del átomo . Normalmente, no todos los átomos se utilizarán en esta suma. En cambio, la búsqueda de coincidencias elige los átomos uno a la vez 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 descomponga satisfactoriamente, es decir, la norma del residual es pequeña, donde el residual después del cálculo y se denota por ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle D}$ ${\displaystyle a_{n}}$ ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle D}$ ${\displaystyle \gamma _{N}}$ ${\displaystyle a_{N}}$

${\displaystyle R_{N+1}=f-{\hat {f}}_{N}}$.

Si converge rápidamente a cero, entonces sólo se necesitan unos pocos átomos para obtener una buena aproximación a . Estas representaciones escasas son deseables para la codificación y compresión de señales. Más precisamente, el problema de escasez que la búsqueda de emparejamiento pretende resolver aproximadamente es ${\displaystyle R_{n}}$ ${\displaystyle f}$

${\displaystyle \min _{x}\|f-Dx\|_{2}^{2}\ {\text{ subject to }}\ \|x\|_{0}\leq N,}$

¿Dónde está la pseudonorma (es decir, el número de elementos distintos de cero de )? En la notación anterior, las entradas distintas de cero son . Resolver exactamente el problema de escasez es NP-difícil , razón por la cual se utilizan métodos de aproximación como MP. ${\displaystyle \|x\|_{0}}$ ${\displaystyle L_{0}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{\gamma _{n}}=a_{n}}$

A modo de comparación, considere la representación de una señal mediante transformada de Fourier ; esto se puede describir utilizando los términos indicados 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 sólo 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 coincidan con una señal . ${\displaystyle f}$ ${\displaystyle f}$

el algoritmo

Ejemplo de recuperación de una señal desconocida (línea gris) a partir de algunas mediciones (puntos negros) utilizando un algoritmo de búsqueda de coincidencia ortogonal (los puntos morados muestran los coeficientes recuperados).

Si contiene una gran cantidad de vectores, buscar la representación más escasa es computacionalmente inaceptable para aplicaciones prácticas. En 1993, Mallat y Zhang ^[1] propusieron una solución codiciosa a la que llamaron "Matching Pursuit". Para cualquier señal y cualquier diccionario , el algoritmo genera de forma iterativa una lista ordenada de índices atómicos y escalares de ponderación, que forman la solución subóptima al problema de la representación escasa de señales. ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$

Búsqueda de coincidencia de algoritmos Entrada: Señal:, diccionario con columnas normalizadas . ${\displaystyle f(t)}$ ${\displaystyle D}$ ${\displaystyle g_{i}}$ Salida: Lista de coeficientes e índices para los átomos correspondientes . ${\displaystyle (a_{n})_{n=1}^{N}}$ ${\displaystyle (\gamma _{n})_{n=1}^{N}}$ Inicialización:  ${\displaystyle R_{1}\,\leftarrow \,f(t)}$; ; ${\displaystyle n\,\leftarrow \,1}$ Repetir: Encuentre con producto interno máximo ; ; ; ; ${\displaystyle g_{\gamma _{n}}\in D}$ ${\displaystyle |\langle R_{n},g_{\gamma _{n}}\rangle |}$ ${\displaystyle a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle }$ ${\displaystyle R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}}$ ${\displaystyle n\,\leftarrow \,n+1}$ Hasta la condición de parada (por ejemplo :) ${\displaystyle \|R_{n}\|<\mathrm {threshold} }$ devolver

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " return " finaliza 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 la que se encuentran proyecciones "interesantes"; aquellos que se desvían más de una distribución normal se consideran más interesantes.

Propiedades

• El algoritmo converge (es decir ) para cualquiera que esté en el espacio abarcado por el diccionario. ${\displaystyle R_{n}\to 0}$ ${\displaystyle f}$
• El error disminuye monótonamente. ${\displaystyle \|R_{n}\|}$
• Como en cada paso, el residual es ortogonal al filtro seleccionado, la ecuación de conservación de energía se satisface para cada uno : ${\displaystyle N}$

${\displaystyle \|f\|^{2}=\|R_{N+1}\|^{2}+\sum _{n=1}^{N}{|a_{n}|^{2}}}$.

• En el caso de que los vectores sean ortonormales, en lugar de redundantes, entonces MP es una forma de análisis de componentes principales. ${\displaystyle D}$

Aplicaciones

La búsqueda de coincidencias se ha aplicado a la codificación de señales, imágenes ^[2] y videos, ^{[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.

Una aplicación muy reciente de MP es su uso en codificación de cálculo lineal ^[13] para acelerar el cálculo de productos matriz-vector.

Extensiones

Una extensión popular de Matching Pursuit (MP) es su versión ortogonal: Orthogonal Matching Pursuit ^{[14] [15]} (OMP). La principal diferencia con MP es que después de cada paso, todos los coeficientes extraídos hasta el momento se actualizan, calculando la proyección ortogonal de la señal en el subespacio abarcado por el conjunto de átomos seleccionados hasta el momento. Esto puede conducir a resultados mejores que el MP estándar, pero requiere más cálculo. Se demostró que OMP tiene garantías de estabilidad y rendimiento bajo ciertas condiciones de isometría restringida . ^[16] El algoritmo incremental multiparamétrico (IMP), publicado tres años antes que MP, funciona de la misma manera que OMP. ^[17]

Extensiones como Multichannel MP ^[18] y Multichannel OMP ^[19] permiten procesar señales multicomponente. Una extensión obvia de Matching Pursuit es sobre múltiples posiciones y escalas, al aumentar el diccionario para que sea uno basado en wavelets. Esto se puede hacer de manera eficiente utilizando el operador de convolución sin cambiar el algoritmo central. ^[20]

La búsqueda de coincidencias está relacionada con el campo de la detección comprimida y ha sido ampliada por investigadores de esa comunidad. Las extensiones notables son Orthogonal Matching Pursuit (OMP), ^[21] Stagewise OMP (StOMP), ^[22] Compressive Sample Matching Search (CoSaMP), ^[23] Generalized OMP (gOMP), ^[24] y Multipath Matching Pursuit (MMP). ^[25]

Ver también

• Algoritmo LIMPIO
• Procesamiento de imágenes
• Análisis espectral de mínimos cuadrados
• Análisis de componentes principales (PCA)
• Seguimiento de proyección
• Procesamiento de la señal
• Aproximación escasa
• Regresión paso a paso

Referencias

1. Mallat, SG; Zhang, Z. (1993). "Emparejar actividades con diccionarios de tiempo-frecuencia". Transacciones IEEE sobre procesamiento de señales . 1993 (12): 3397–3415. Código bibliográfico : 1993ITSP...41.3397M. doi : 10.1109/78.258082. S2CID  14427335.
2. Perrinet, L. (2015). "Modelos dispersos para visión por computadora". Visión por computadora inspirada biológicamente . 14 : 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN 9783527680863. S2CID  2085413.
3. Bergeaud, F.; Mallat, S. (1995). "Búsqueda coincidente de imágenes". Actas., Conferencia internacional sobre procesamiento de imágenes . vol. 1. págs. 53–56. doi :10.1109/ICIP.1995.529037. ISBN 978-0-7803-3122-8. S2CID  721789.
4. Neff, R.; Zakhor, A. (1997). "Codificación de vídeo con una tasa de bits muy baja basada en objetivos coincidentes". Transacciones IEEE sobre circuitos y sistemas para tecnología de vídeo . 7 (1): 158-171. doi : 10.1109/76.554427. S2CID  15317511.
5. Mendels, F.; Vandergheynst, P.; Tiran, JP (2006). "Reconocimiento y representación de formas basadas en la búsqueda coincidente utilizando el espacio de escala". Revista internacional de tecnología y sistemas de imágenes . 16 (5): 162–180. doi :10.1002/ima.20078. S2CID  5132416.
6. Tósico, yo; 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 vídeo . 16 (11): 1338-1349. doi : 10.1109/tcsvt.2006.883502. S2CID  3031513.
7. Chakraborty, Debejyo; Kovvali, Narayan; Wei, junio; Papandreou-Suppappola, Antonia; Cochran, Douglas; Chattopadhyay, Aditi (2009). "Clasificación de daños Monitoreo de la salud estructural 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. S2CID  109511712.
8. Perrinet, LU; Samuelides, M.; Thorpe, S. (2002). "Codificación de picos dispersos en una red neuronal multicapa de retroalimentación asincrónica utilizando Matching Pursuit". Neurocomputación . 57C : 125–34. doi : 10.1016/j.neucom.2004.01.010.^{[ enlace muerto permanente ]}
9. Lin, Jian-Liang; Hwang, Wen-Liang; Pei, Soo-Chang (2007). "Codificación de vídeo de búsqueda de coincidencia rápida mediante la combinación de aproximación de diccionario y extracción de átomos". Transacciones IEEE sobre circuitos y sistemas para tecnología de vídeo . 17 (12): 1679–1689. CiteSeerX 10.1.1.671.9670 . doi :10.1109/tcsvt.2007.903120. S2CID  8315216. 
10. Wu, Yinghua; Batista, Víctor S. (2003). "Búsqueda de emparejamiento para simulaciones de procesos cuánticos". J. química. Física . 118 (15): 6720–6724. Código Bib : 2003JChPh.118.6720W. doi : 10.1063/1.1560636. S2CID  37544146.
11. 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. 
12. Aarón, M .; Elad, M.; Bruckstein, AM (2006). "El K-SVD: un algoritmo para el diseño de diccionarios supercompletos para una representación escasa". Transacciones IEEE sobre procesamiento de señales . 54 (11): 4311–4322. Código Bib : 2006ITSP...54.4311A. doi :10.1109/tsp.2006.881199. S2CID  7477309.
13. Müller, Ralf R.; Gäde, Bernhard; Bereyhi, Ali (2021). "Codificación de cálculo lineal". arXiv : 2102.00398 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
14. Pati, Y.; Rezaífar, R.; Krishnaprasad, P. (1993). "Búsqueda de coincidencia ortogonal: aproximación de funciones recursivas con aplicaciones a la descomposición de ondas". Actas de la 27ª Conferencia de Asilomar sobre señales, sistemas y computadoras . págs. 40–44. CiteSeerX 10.1.1.348.5735 . doi :10.1109/acssc.1993.342465. ISBN  978-0-8186-4120-6. S2CID  16513805. {{cite book}}: |journal=ignorado ( ayuda )
15. Davis, G.; Mallat, S.; Zhang, Z. (1994). "Descomposiciones adaptativas tiempo-frecuencia con búsquedas coincidentes". Ingeniería Óptica . 33 (7): 2183. Código bibliográfico : 1994OptEn..33.2183D. doi :10.1117/12.173207.
16. Ding, J.; Chen, L.; Gu, Y. (2013). "Análisis de perturbaciones de la búsqueda de emparejamiento ortogonal". Transacciones IEEE sobre procesamiento de señales . 61 (2): 398–410. arXiv : 1106.3373 . Código Bib : 2013ITSP...61..398D. doi :10.1109/TSP.2012.2222377. ISSN  1941-0476. S2CID  17166658.
17. Mather, John (1990). "El algoritmo incremental multiparamétrico". 1990 Registro de la conferencia Vigésima Cuarta Conferencia de Asilomar sobre Señales, Sistemas y Computadoras, 1990 . vol. 1. pág. 368. doi : 10.1109/ACSSC.1990.523362. ISBN 0-8186-2180-X. ISSN  1058-6393. S2CID  61327933.
18. "Separación de fuentes lineales por partes", R. Gribonval, Proc. ESPÍA '03, 2003
19. Tropp, Joel ; Gilbert, A .; Strauss, M. (2006). "Algoritmos para aproximaciones dispersas simultáneas; Parte I: Búsqueda codiciosa". Procesamiento de señal. – Aproximaciones dispersas en el procesamiento de señales e imágenes . 86 (3): 572–588. Código Bib : 2006SigPr..86..572T. doi :10.1016/j.sigpro.2005.05.030.
20. Perrinet, Laurent U. (2015). "Modelos dispersos para visión por computadora". Visión por computadora inspirada biológicamente . págs. 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN 9783527680863. S2CID  2085413.
21. Tropp, Joel A.; Gilbert, Anna C. (2007). "Recuperación de señal de mediciones aleatorias mediante búsqueda de coincidencia ortogonal" (PDF) . Transacciones IEEE sobre teoría de la información . 53 (12): 4655–4666. doi :10.1109/tit.2007.909108. S2CID  6261304.
22. Donoho, David L.; Tsaig, Yaakov; Drori, Iddo; Jean-luc, Starck (2006). "Solución escasa de ecuaciones lineales indeterminadas mediante 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. S2CID  7923170.
23. Needell, D.; Tropp, JA (2009). "CoSaMP: recuperación iterativa de señales de muestras incompletas e inexactas". Análisis Armónico Aplicado y Computacional . 26 (3): 301–321. arXiv : 0803.2392 . doi :10.1016/j.acha.2008.07.002. S2CID  1642637.
24. Wang, J.; Kwon, S.; Calza, B. (2012). "Búsqueda de coincidencia ortogonal generalizada". Transacciones IEEE sobre procesamiento de señales . 60 (12): 6202–6216. arXiv : 1111.6664 . Código Bib : 2012ITSP...60.6202J. doi :10.1109/TSP.2012.2218810. S2CID  2585677.
25. Kwon, S.; Wang, J.; Calza, B. (2014). "Búsqueda de coincidencias de rutas múltiples". Transacciones IEEE sobre teoría de la información . 60 (5): 2986–3001. arXiv : 1308.4791 . doi :10.1109/TIT.2014.2310482. S2CID  15134308.