La minimización de L1 no siempre le brinda la solución más escasa. El problema de encontrar la solución más escasa es NP-complete en general y la minimización de L1 es el tiempo polinómico, por lo que no puede funcionar en general.
Sin embargo, la minimización de L1 es generalmente una buena idea y si no le da la solución más escasa, entonces le da una buena aproximación y es relativamente barata de usar. Además, hay varios casos en los que la minimización de L1 le dará la mejor solución: propiedad de isometría restringida y hay muchas otras variantes.
Sin embargo, un algoritmo más rápido que la optimización L1 son los algoritmos de paso de mensajes para la detección comprimida. En el documento tiene algunas líneas de transición de fase (consulte para obtener más información Transición de fase de Donoho-Tanner para recuperación dispersa). Debajo de las líneas, el paso aproximado de mensajes funciona y ofrece la solución más escasa. Por encima de esas líneas, debe utilizar la búsqueda combinatoria, es decir, se encuentra en territorio NP.
- ¿Por qué la raíz cúbica de 64 es igual a 4.000000000000001 en mi calculadora cuando 4 ^ 3 = 64 en la misma calculadora?
- ¿Cuál es el descubrimiento matemático reciente más influyente?
- ¿Es la notación matemática innecesariamente compleja?
- ¿Cuál es el isomorfismo preciso entre conexiones y transporte paralelo?
- ¿Qué tienen los espacios topológicos que los hace tan frecuentes en varios campos diferentes de las matemáticas?
