Propiedad de espacio nulo

En la detección comprimida , la propiedad del espacio nulo proporciona condiciones necesarias y suficientes para la reconstrucción de señales dispersas utilizando las técnicas de${\displaystyle \ell _{1}}$-relajación . El término "propiedad del espacio nulo" proviene de 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.

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

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

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

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

se resuelve en lugar de la${\displaystyle \ell _{0}}$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${\displaystyle \ell _{1}}$-la relajación dará la misma respuesta que la${\displaystyle \ell _{0}}$Problema. La propiedad de espacio nulo es una forma de garantizar la concordancia.

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

El siguiente teorema proporciona condiciones necesarias y suficientes sobre la recuperabilidad de un dado${\displaystyle s}$-vector disperso en${\displaystyle \mathbb {C} ^{n}}$La demostración del teorema es estándar, y la demostración que se proporciona aquí es un resumen de la de Holger Rauhut. ^{[ 3 ]}

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

${\displaystyle {\textit {Prueba:}}}$Para la dirección hacia adelante, tenga en cuenta que${\displaystyle \eta _{S}}$y${\displaystyle -\eta _{S^{C}}}$son vectores distintos con${\displaystyle A(-\eta _{S^{C}})=A(\eta _{S})}$por la linealidad de${\displaystyle A}$y por lo tanto, por unicidad debemos tener${\displaystyle \|\eta _ {S}\|_{1}<\|\eta _ {S^{C}}\|_{1}}$como se desee. Para la dirección inversa, deje${\displaystyle x}$ser${\displaystyle s}$-escaso y${\displaystyle z}$otro (no es necesario)${\displaystyle s}$-disperso) vector tal que${\displaystyle z\neq x}$y${\displaystyle Az=Ax}$. Defina el vector (distinto de cero)${\displaystyle \eta =xz}$y observe que se encuentra en el espacio nulo de${\displaystyle A}$. Llamar${\displaystyle S}$el apoyo de${\displaystyle x}$y entonces el resultado se deduce de una aplicación elemental de la desigualdad triangular :${\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}}$, estableciendo la minimalidad de${\displaystyle x}$.${\displaystyle \square }$