Cuando los investigadores comenzaron primero a la búsqueda de soluciones dispersas a $Ax = b$, se utiliza codiciosos de métodos tales como la ortogonales coincidencia de búsqueda (OMP). En OMP, activamos los componentes de $x$ uno por uno, y en cada etapa se selecciona el componente $i$ de manera tal que el $i$ésima columna de a $A$ está más correlacionada con la residual $Ax - b$.
Luego, los investigadores desarrollaron métodos, tales como la Base de la Búsqueda y el Lazo, que se basa en la resolución de problemas de optimización con dispersión de inducción de regularizers. La Base de la Búsqueda del problema es \begin{align} \underset{x}{\text{minimize}} & \quad \| x \|_1 \\ \text{subject to} & \quad Ax = b. \end{align} El Lazo problema es $$ \underset{x}{\text{minimizar}} \quad \frac12 \| Ax - b \|_2^2 + \lambda \| x \|_1. $$ Esta nueva estrategia fue posible gracias a nuevos algoritmos de optimización (métodos de punto interior), que fueron capaces de resolver estos a gran escala de la optimización de problemas de forma eficiente.
Pregunta: Son codiciosos métodos tales como ortogonal de coincidencia de búsqueda y sus variantes, que ahora se considera obsoleto? Hay un consenso de que no funcionan tan bien como los enfoques basados en la optimización con la dispersión de inducción de regularizers? Ha OMP sido abandonado?
Aquí está una de 1994 papel por Chen y Donoho que da una breve descripción de los primeros intentos para encontrar soluciones dispersas a $Ax = b$, que conduce hasta la Base de la Búsqueda y el Lazo: https://statweb.stanford.edu/~donoho/Informes/1994/asilomar.pdf
