Propiedad de espacio nulo

En la detección comprimida , la propiedad del espacio nulo proporciona las condiciones necesarias y suficientes para la reconstrucción de señales dispersas utilizando las técnicas de relajación . El término "propiedad del espacio nulo" tiene su origen en Cohen, Dahmen y DeVore. ^[1] La propiedad del espacio nulo suele ser difícil de comprobar en la práctica, y la propiedad de isometría restringida es una condición más moderna en el campo de la detección comprimida. ${\displaystyle \ell _{1}}$

La técnica de ℓ 1 {\displaystyle \ell _{1}} -relajación

El problema de minimización no convexa , ${\displaystyle \ell _{0}}$

${\displaystyle \min \limits _{x}\|x\|_{0}}$ sujeto a , ${\displaystyle Ax=b}$

es un problema estándar en la detección comprimida. Sin embargo, se sabe que la -minimización es NP-hard en general. ^[2] Como tal, la técnica de -relajación se emplea a veces para sortear las dificultades de reconstrucción de señales utilizando la -norma. En la -relajación, el problema, ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{1}}$

${\displaystyle \min \limits _{x}\|x\|_{1}}$ sujeto a , ${\displaystyle Ax=b}$

se resuelve en lugar del problema. Nótese que esta relajación es convexa y, por lo tanto, susceptible a las técnicas estándar de programación lineal , una característica computacionalmente deseable. Naturalmente, deseamos saber cuándo la relajación dará la misma respuesta que el problema. La propiedad del espacio nulo es una forma de garantizar la concordancia. ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$

Definición

Una matriz compleja tiene la propiedad de espacio nulo de orden , si para todos los conjuntos de índices con tenemos que: para todos los . ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s=|S|\leq n}$ ${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$ ${\displaystyle \eta \in \ker {A}\setminus \left\{0\right\}}$

Estado de recuperación

El siguiente teorema proporciona una condición necesaria y suficiente para la recuperabilidad de un vector disperso dado en . La prueba del teorema es estándar y la prueba proporcionada aquí es un resumen de Holger Rauhut. ^[3] ${\displaystyle s}$ ${\displaystyle \mathbb {C} ^{n}}$

${\displaystyle {\textbf {Theorem:}}}$Sea una matriz compleja. Entonces, cada señal dispersa es la solución única al problema de relajación si y solo si satisface la propiedad de espacio nulo con orden . ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle s}$ ${\displaystyle x\in \mathbb {C} ^{n}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle b=Ax}$ ${\displaystyle A}$ ${\displaystyle s}$

${\displaystyle {\textit {Proof:}}}$Para la dirección hacia delante, observe que y son vectores distintos con por la linealidad de , y por lo tanto, por unicidad debemos tener como se desea. Para la dirección hacia atrás, sea -sparse y otro vector (no necesariamente -sparse) tal que y . Defina el vector (distinto de cero) y observe que se encuentra en el espacio nulo de . Llame al soporte de , y entonces el resultado se sigue de una aplicación elemental de la desigualdad triangular : , estableciendo la minimalidad de . ${\displaystyle \eta _{S}}$ ${\displaystyle -\eta _{S^{C}}}$ ${\displaystyle A(-\eta _{S^{C}})=A(\eta _{S})}$ ${\displaystyle A}$ ${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle z}$ ${\displaystyle s}$ ${\displaystyle z\neq x}$ ${\displaystyle Az=Ax}$ ${\displaystyle \eta =x-z}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle \|x\|_{1}\leq \|x-z_{S}\|_{1}+\|z_{S}\|_{1}=\|\eta _{S}\|_{1}+\|z_{S}\|_{1}<\|\eta _{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|-z_{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|z\|_{1}}$ ${\displaystyle x}$ ${\displaystyle \square }$

Referencias

1. Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald (1 de enero de 2009). "Detección comprimida y mejor aproximación de 𝑘-término". Revista de la Sociedad Americana de Matemáticas . 22 (1): 211–231. doi : 10.1090/S0894-0347-08-00610-3 . ISSN  0894-0347.
2. Natarajan, BK (1 de abril de 1995). "Soluciones aproximadas dispersas para sistemas lineales". SIAM J. Comput . 24 (2): 227–234. doi :10.1137/S0097539792240406. ISSN  0097-5397. S2CID  2072045.
3. Rauhut, Holger (2011). Detección compresiva y matrices aleatorias estructuradas . CiteSeerX 10.1.1.185.3754 .