Propiedad de isometría restringida (RIP) en detección de compresión

La propiedad de isometría restringida establece que:

(1 - δ_{S}) | | x | |_{2}^{2} \leq | | A x | |_{2}^{2} \leq (1 + δ_{S}) | | x | |_{2}^{2}

$\begin{equation} (1-\delta_S)||x||_2^2 \le ||A x||_2^2 \le (1+\delta_S)||x||_2^2 \end{equation}$ para cualquier

S

$S$ vector disperso

x

$x$ . La constante de isometría restringida es

δ_{S}

$\delta_S$ ,

0 < δ_{S} < 1

$0 < \delta_S < 1$ .

Esto significa que la matriz $A$ se garantiza que solo cambiará la longitud de cualquier vector $x$ "muy poco" mientras el vector $x$ Por lo menos $S$ -sparse (tiene como máximo $S$ coeficientes distintos de cero).

Supongamos que tenemos arbitrario $\frac{S}{2}$ vectores dispersos $x$ . Para poder reconstruir dichos vectores en general, a partir de mediciones tomadas como $y = A x$ , debemos asegurarnos de que sea posible distinguir entre mediciones $y_1 = A x_1$ y $y_2 = A x_2$ de cualquiera de estos dos vectores. Si $y_1 = y_2$ para cualquiera de estos dos vectores $x_1$ y $x_2$ , no podríamos distinguirlos y reconstruirlos sin ambigüedades. Por lo tanto, debemos asegurarnos de que las medidas de dos $\frac{S}{2}$ -los vectores dispersos son "suficientemente diferentes".

Si calculamos la diferencia entre dos $\frac{S}{2}$ vectores dispersos, su diferencia puede ser como máximo $S$ -escaso. Entonces, para reconstruir cualquier $\frac{S}{2}$ - dispersa el vector correctamente de las medidas tomadas con $A$ , la propiedad de isometría restringida cuantifica qué tan bien $A$ vamos a hacer eso (cuanto más pequeño $\delta_S$ , el mejor).

Para una introducción temprana a la detección comprimida y la propiedad de isometría restringida (y otros conceptos), vea Candès y Wakin, 2008 .

Thomas Arildsen
fuente

Tengamos en cuenta también que la constante

δ_{S}

$\delta_{S}$ no necesita ser el mismo en ambos lados, por ejemplo, matriz de detección gaussiana. Por favor vea el artículo reciente. arxiv.org/abs/1410.1956

Oliver

Si la propiedad dada se cumple para cualquier submatriz de

A

$A$ ?

Dilawar

¿Se puede verificar la propiedad RIP para una matriz concreta en la práctica con un algoritmo?

Charlie Parker el

@CharlieParker no, lamentablemente no. Implica calcular el SVD de todos los posibles

S

$S$ sub-matrices de columna de

A

$A$ . Esto se convierte rápidamente en un número poco realista de combinaciones para calcular, incluso para las de tamaño modesto.

A

$A$ . Y recuerde que la detección de compresión funciona mejor cuanto más grandes sean los tamaños de

A

$A$ y

x

$x$ .

Thomas Arildsen

Propiedad de isometría restringida (RIP) en detección de compresión

Respuestas: