Un algoritmo voraz iterativo para aproximación dispersa que construye una representación k-dispersa de una señal seleccionando repetidamente el átomo del diccionario más correlacionado con el residual actual, proyectando ortogonalmente la señal sobre el espacio generado por los átomos seleccionados para actualizar coeficientes y actualizando el residual hasta que se cumple un criterio de parada.

Principio

En cada iteración elegir el elemento del diccionario con mayor producto interno absoluto con el residual (selección voraz), luego recalcular coeficientes resolviendo un problema de mínimos cuadrados sobre los átomos seleccionados (proyección ortogonal) para evitar reponderaciones inconsistentes de átomos previamente elegidos y asegurar la reducción monótona de la norma del residual.

Demostración

Aproximar una señal y con una base redundante (diccionario): inicializar r=y, seleccionar el átomo con mayor correlación , añadirlo al conjunto activo, resolver el problema de mínimos cuadrados para los coeficientes activos, actualizar r=y - D_active c_active y repetir hasta alcanzar la norma de residual o el objetivo de sparsidad, produciendo un código disperso interpretable.

Aplicación incorrecta

Parar OMP demasiado pronto cuando quedan átomos esenciales sin seleccionar, produciendo aproximaciones sesgadas, o aplicar OMP con columnas de diccionario muy coherentes sin modificaciones (p. ej., regularización), lo que puede causar selección incorrecta de átomos y mala recuperación.

Consecuencia

Cuando se cumplen condiciones como nivel de sparsidad e incoherencia/Restricte Isometry, OMP recupera representaciones dispersas rápidamente con soportes interpretables y costo computacional inferior al de la búsqueda exhaustiva; ofrece un intercambio claro entre sparsidad y error de aproximación.

Inversión

Ajuste denso de mínimos cuadrados sobre todo el diccionario: resolver una minimización L2 global usando todos los átomos, obteniendo un residual menor para una norma dada pero produciendo coeficientes densos sin sparsidad impuesta ni interpretabilidad del soporte seleccionado.

Límite

Ámbito: problemas lineales de aproximación dispersa con matriz diccionario explícita y coherencia moderada donde la selección voraz es significativa; excluye problemas que exigen minimización exacta l0 en diccionarios muy coherentes, o señales que se modelan mejor con sparsidad estructurada (agrupada o jerárquica) sin adaptar el algoritmo.

Tensión semántica

Tensión entre voracidad y optimalidad global: las decisiones locales y voraces de OMP son rápidas e interpretables pero pueden perder soportes dispersos globalmente óptimos; esto contrasta con enfoques de relajación convexa (minimización L1) que ofrecen otras compensaciones entre robustez y coste computacional.

Síntesis

La Búsqueda Por Emparejamiento Ortogonal es un algoritmo voraz de codificación dispersa que selecciona iterativamente el átomo más correlacionado con el residual y recalcula coeficientes por proyección ortogonal para construir una representación dispersa con reducción monótona del residual y soporte interpretable.