Búsqueda de coincidencias

Algoritmo de datos multidimensionales

Una señal y su representación en forma de ondícula. Cada píxel del 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 indica el producto interno del átomo de ondícula correspondiente con la señal (abajo). La búsqueda de coincidencias debería representar la señal con solo unos pocos átomos, como los tres que se encuentran en los centros de las elipses claramente visibles.

Matching Pursuit (MP) es un algoritmo de aproximación dispersa que encuentra las proyecciones de "mejor coincidencia" de datos multidimensionales en el lapso de un diccionario sobrecompleto (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 columna n de la matriz y es el factor de ponderación escalar (amplitud) para el átomo . Normalmente, no todos los átomos de 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 (suponiendo que los átomos están normalizados), restando de la señal una aproximación que utiliza solo ese átomo y repitiendo el proceso hasta que la señal se descomponga satisfactoriamente, es decir, la norma del residuo sea pequeña, donde el residuo después de calcular 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 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 escasez que la búsqueda de coincidencias pretende resolver aproximadamente es ${\displaystyle R_{n}}$ ${\displaystyle f}$

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

donde es la pseudonorma (es decir, el número de elementos distintos de cero de ). En la notación anterior, las entradas distintas de cero de son . Resolver el problema de escasez exactamente es NP-hard , por lo que 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, consideremos la representación de una señal mediante la transformada de Fourier ; esta puede describirse utilizando 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 . ${\displaystyle f}$ ${\displaystyle f}$

El algoritmo

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

Si contiene una gran cantidad de vectores, la búsqueda de la representación más dispersa de es computacionalmente inaceptable para aplicaciones prácticas. En 1993, Mallat y Zhang ^[1] propusieron una solución voraz que llamaron "Matching Pursuit". Para cualquier señal y cualquier diccionario , el algoritmo genera iterativamente 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 de señales dispersas. ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$

Búsqueda de coincidencias 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: Encuentra con máximo producto interno ; ; ; ; ${\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 condición de parada (por ejemplo: ) ${\displaystyle \|R_{n}\|<\mathrm {threshold} }$ devolver

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

En el procesamiento de señales, el concepto de búsqueda coincidente está relacionado con la búsqueda de proyección estadística , en la que se encuentran proyecciones "interesantes"; aquellas 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 abarcado por el diccionario. ${\displaystyle R_{n}\to 0}$ ${\displaystyle f}$
• El error disminuye monótonamente. ${\displaystyle \|R_{n}\|}$
• Como en cada paso el residuo 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 ser redundantes, entonces MP es una forma de análisis de componentes principales. ${\displaystyle D}$

Aplicaciones

El match-busking se ha aplicado a la codificación de señales, imágenes ^[2] y vídeo, ^{[3] [4]} la representación y reconocimiento de formas ^[5] , la codificación de objetos 3D ^[6] y en aplicaciones interdisciplinarias como la monitorización de la salud estructural. ^[7] Se ha demostrado que funciona mejor que la codificación basada en DCT para tasas de bits bajas, tanto en eficiencia de codificación como en calidad de imagen. ^[8] El principal problema con el match-busking 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 aproximadas del diccionario y formas subóptimas de elegir la mejor coincidencia en cada iteración (extracción de átomos). ^[9] El algoritmo de match-busking se utiliza en MP/SOFT, un método de simulación de 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 la 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 sobre 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 computación. Se demostró que OMP tiene garantías de estabilidad y rendimiento bajo ciertas condiciones de isometría restringidas . ^[16] El algoritmo multiparamétrico incremental (IMP), publicado tres años antes de MP, funciona de la misma manera que OMP. ^[17]

Las 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, ampliando el diccionario para que sea el de una base wavelet. 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 la búsqueda de coincidencias ortogonales (OMP), ^[21] la búsqueda de coincidencias por etapas (StOMP), ^[22] la búsqueda de coincidencias por muestreo compresivo (CoSaMP), ^[23] la búsqueda de coincidencias generalizada (gOMP), ^[24] y la búsqueda de coincidencias por trayectos múltiples (MMP). ^[25]

Véase también

• Algoritmo CLEAN
• Procesamiento de imágenes
• Análisis espectral de mínimos cuadrados
• Análisis de componentes principales (PCA)
• Persecución de proyecciones
• Procesamiento de señales
• Aproximación dispersa
• Regresión por pasos

Referencias

1. Mallat, SG; Zhang, Z. (1993). "Coincidencia de búsquedas con diccionarios de tiempo-frecuencia". IEEE Transactions on Signal Processing . 1993 (12): 3397–3415. Bibcode :1993ITSP...41.3397M. doi :10.1109/78.258082. S2CID  14427335.
2. Perrinet, L. (2015). "Modelos dispersos para visión artificial". Visión artificial inspirada en la biología . 14 : 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN . 9783527680863.S2CID2085413  .​
3. Bergeaud, F.; Mallat, S. (1995). "Matching persecution of images". Actas de la 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. Número de identificación del sujeto  721789.
4. Neff, R.; Zakhor, A. (1997). "Codificación de vídeo de muy baja tasa de bits basada en búsquedas coincidentes". IEEE Transactions on Circuits and Systems for Video Technology . 7 (1): 158–171. doi :10.1109/76.554427. S2CID  15317511.
5. Mendels, F.; Vandergheynst, P.; Thiran, JP (2006). "Representación y reconocimiento de formas basado en búsqueda de correspondencias utilizando el espacio de escala". Revista internacional de sistemas y tecnología de imágenes . 16 (5): 162–180. doi :10.1002/ima.20078. S2CID  5132416.
6. Tosic, I.; Frossard, P.; Vandergheynst, P. (2005). "Codificación progresiva de objetos 3D basada en descomposiciones sobrecompletas". IEEE Transactions on Circuits and Systems for Video Technology . 16 (11): 1338–1349. doi :10.1109/tcsvt.2006.883502. S2CID  3031513.
7. Chakraborty, Debejyo; Kovvali, Narayan; Wei, Jun; Papandreou-Suppappola, Antonia; Cochran, Douglas; Chattopadhyay, Aditi (2009). "Monitoreo de la salud estructural mediante clasificación de daños en estructuras atornilladas utilizando técnicas de tiempo-frecuencia". Revista de sistemas y estructuras 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 avance asincrónico utilizando Matching Pursuit". Neurocomputing . 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 video de búsqueda de coincidencia rápida mediante la combinación de aproximación de diccionario y extracción de átomos". IEEE Transactions on Circuits and Systems for Video Technology . 17 (12): 1679–1689. CiteSeerX 10.1.1.671.9670 . doi :10.1109/tcsvt.2007.903120. S2CID  8315216. 
10. Wu, Yinghua; Batista, Victor S. (2003). "Matching-pursuit para simulaciones de procesos cuánticos". J. Chem. Phys . 118 (15): 6720–6724. Bibcode :2003JChPh.118.6720W. doi :10.1063/1.1560636. S2CID  37544146.
11. Perrinet, LP (2010). "El 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. Aharon, M. ; Elad, M.; Bruckstein, AM (2006). "El K-SVD: un algoritmo para el diseño de diccionarios sobrecompletos para representación dispersa". IEEE Transactions on Signal Processing . 54 (11): 4311–4322. Bibcode :2006ITSP...54.4311A. doi :10.1109/tsp.2006.881199. S2CID  7477309.
13. Müller, Ralf R.; Gäde, Bernhard; Bereyhi, Ali (2021). "Codificación computacional lineal". arXiv : 2102.00398 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
14. Pati, Y.; Rezaiifar, R.; Krishnaprasad, P. (1993). "Búsqueda de correspondencia ortogonal: aproximación de función recursiva con aplicaciones a la descomposición wavelet". Actas de la 27.ª Conferencia de Asilomar sobre señales, sistemas y ordenadores . págs. 40–44. CiteSeerX 10.1.1.348.5735 . doi :10.1109/acssc.1993.342465. ISBN .  978-0-8186-4120-6. Número de identificación del sujeto  16513805. {{cite book}}: |journal=ignorado ( ayuda )
15. Davis, G.; Mallat, S.; Zhang, Z. (1994). "Descomposiciones adaptativas de tiempo-frecuencia con búsquedas coincidentes". Ingeniería óptica . 33 (7): 2183. Bibcode :1994OptEn..33.2183D. doi :10.1117/12.173207.
16. Ding, J.; Chen, L.; Gu, Y. (2013). "Análisis de perturbación de búsqueda de coincidencia ortogonal". IEEE Transactions on Signal Processing . 61 (2): 398–410. arXiv : 1106.3373 . Bibcode :2013ITSP...61..398D. doi :10.1109/TSP.2012.2222377. ISSN  1941-0476. S2CID  17166658.
17. Mather, John (1990). "El algoritmo incremental multiparamétrico". 1990 Conference Record Twenty-Fourth Asilomar Conference on Signals, Systems and Computers, 1990. Vol. 1. p. 368. doi :10.1109/ACSSC.1990.523362. ISBN 0-8186-2180-X. ISSN  1058-6393. S2CID  61327933.
18. "Separación lineal de fuentes por partes", R. Gribonval, Proc. SPIE '03, 2003
19. Tropp, Joel ; Gilbert, A. ; Strauss, M. (2006). "Algoritmos para aproximaciones dispersas simultáneas; Parte I: Búsqueda voraz". Signal Proc. – Aproximaciones dispersas en procesamiento de señales e imágenes . 86 (3): 572–588. Bibcode :2006SigPr..86..572T. doi :10.1016/j.sigpro.2005.05.030.
20. Perrinet, Laurent U. (2015). "Modelos dispersos para visión artificial". Visión artificial inspirada en la biología . pp. 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN 9783527680863.S2CID2085413  .​
21. Tropp, Joel A.; Gilbert, Anna C. (2007). "Recuperación de señales a partir de mediciones aleatorias mediante búsqueda de correspondencia ortogonal" (PDF) . IEEE Transactions on Information Theory . 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 dispersa de ecuaciones lineales subdeterminadas mediante búsqueda de correspondencia ortogonal por etapas". IEEE Transactions on Information Theory . 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 a partir 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. S2CID  1642637.
24. Wang, J.; Kwon, S.; Shim, B. (2012). "Búsqueda generalizada de coincidencias ortogonales". IEEE Transactions on Signal Processing . 60 (12): 6202–6216. arXiv : 1111.6664 . Código Bibliográfico :2012ITSP...60.6202J. doi :10.1109/TSP.2012.2218810. S2CID  2585677.
25. Kwon, S.; Wang, J.; Shim, B. (2014). "Búsqueda de coincidencias por trayectorias múltiples". IEEE Transactions on Information Theory . 60 (5): 2986–3001. arXiv : 1308.4791 . doi :10.1109/TIT.2014.2310482. S2CID  15134308.