Búsqueda de bases

Problema de optimización

La búsqueda básica es el problema de optimización matemática de la forma

${\displaystyle \min _{x}\|x\|_{1}\quad {\text{subject to}}\quad y=Ax,}$

donde x es un vector de solución N -dimensional (señal), y es un vector M -dimensional de observaciones ( mediciones), A es una matriz de transformación M  ×  N (normalmente una matriz de medición) y M  <  N.

Generalmente se aplica en casos donde existe un sistema subdeterminado de ecuaciones lineales y  =  Ax que deben satisfacerse exactamente y se desea la solución más dispersa en el sentido L _{1 .}

Cuando es deseable intercambiar la igualdad exacta de Ax e y a cambio de un x más disperso , se prefiere la eliminación de ruido mediante búsqueda de base .

Los problemas de búsqueda de base se pueden convertir en problemas de programación lineal en tiempo polinomial y viceversa, lo que hace que los dos tipos de problemas sean polinomialmente equivalentes. ^[1]

Equivalencia con la programación lineal

Un problema de búsqueda de base se puede convertir en un problema de programación lineal observando primero que

${\displaystyle {\begin{aligned}\|x\|_{1}&=|x_{1}|+|x_{2}|+\ldots +|x_{n}|\\&=(x_{1}^{+}+x_{1}^{-})+(x_{2}^{+}+x_{2}^{-})+\ldots +(x_{n}^{+}+x_{n}^{-})\end{aligned}}}$

donde . Esta construcción se deriva de la restricción , donde el valor de se pretende almacenar en o dependiendo de si es mayor o menor que cero, respectivamente. Aunque un rango de valores y puede potencialmente satisfacer esta restricción, los solucionadores que utilicen el algoritmo simplex encontrarán soluciones donde uno o ambos de o sean cero, lo que da como resultado la relación . ${\displaystyle x_{i}^{+},x_{i}^{-}\geq 0}$ ${\displaystyle x_{i}=x_{i}^{+}-x_{i}^{-}}$ ${\displaystyle |x_{i}|}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle |x_{i}|=(x_{i}^{+}+x_{i}^{-})}$

A partir de esta expansión, el problema puede reformularse en forma canónica como: ^[1]

${\displaystyle {\begin{aligned}&{\text{Find a vector}}&&(\mathbf {x^{+}} ,\mathbf {x^{-}} )\\&{\text{that minimizes}}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{subject to}}&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\mathbf {x^{+}} ,\mathbf {x^{-}} \geq \mathbf {0} .\end{aligned}}}$

Véase también

• Búsqueda básica de eliminación de ruido
• Detección comprimida
• Espectro de frecuencia
• Pruebas grupales
• Lasso (estadísticas)
• Análisis espectral de mínimos cuadrados
• Búsqueda de coincidencias
• Aproximación dispersa

Notas

1. AM Tillmann Equivalencia de programación lineal y búsqueda de bases , PAMM (Proceedings in Applied Mathematics and Mechanics) Volumen 15, 2015, págs. 735-738, DOI: 10.1002/PAMM.201510351

Referencias y lecturas adicionales

• Stephen Boyd, Lieven Vandenbergh: Optimización convexa , Cambridge University Press, 2004, ISBN  9780521833783 , págs. 337–337
• Simon Foucart, Holger Rauhut: Introducción matemática a la detección por compresión . Springer, 2013, ISBN 9780817649487 , págs. 77–110 

Enlaces externos

• Shaobing Chen, David Donoho: Búsqueda de fundamentos
• Terence Tao : Compressed Sensing. Serie de conferencias Mahler (diapositivas)