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 de espacio nulo" proviene de Cohen, Dahmen y DeVore. ^[1] La propiedad de espacio nulo es a menudo difícil de verificar 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 la relajación.${\displaystyle \ell _{1}}$

El problema de la 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-dura en general. ^[2] Como tal, la técnica de -relajación se emplea a veces para sortear las dificultades de la reconstrucción de señales usando la -norm. 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. Tenga en cuenta que esta relajación es convexa y, por lo tanto, compatible con las técnicas estándar de programación lineal , una característica deseable desde el punto de vista computacional. Naturalmente, deseamos saber cuándo la relajación dará la misma respuesta que el problema. La propiedad nullspace es una forma de garantizar el acuerdo.${\displaystyle \ell _{0}}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{0}}$

Definición

Una matriz compleja tiene la propiedad de orden de espacio nulo , si para todos los conjuntos de índices con tenemos eso: para todos .${\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\}}$

Condición de recuperación

El siguiente teorema da una condición necesaria y suficiente sobre la recuperabilidad de un vector disperso dado en . La demostración del teorema es estándar, y la demostración proporcionada aquí se resume a partir de Holger Rauhut. ^[3]${\displaystyle s}$${\displaystyle \mathbb {C} ^{n}}$

${\displaystyle {\textbf {Theorem:}}}$Sea una matriz compleja. Entonces, cada señal -sparse es la única solución al problema de -relaxation con 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 adelante, observe que y son vectores distintos con la linealidad de , y por lo tanto, la unicidad que debemos tener como se desea. Para la dirección hacia atrás, sea -sparse y otro vector (no necesario -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 luego el resultado se sigue de una aplicación elemental de la desigualdad del triángulo :, estableciendo la minimidad 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 la mejor aproximación de 𝑘-término" . Revista de la Sociedad Matemática Estadounidense . 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 escasas para sistemas lineales". SIAM J. Comput . 24 (2): 227–234. doi : 10.1137 / S0097539792240406 . ISSN 0097-5397 . 
3. Rauhut, Holger (2011). Detección compresiva y matrices aleatorias estructuradas . CiteSeerX 10.1.1.185.3754 . 

enlaces externos