Propiedad de isometría restringida

En álgebra lineal , la propiedad de isometría restringida ( RIP ) caracteriza a las matrices que son casi ortonormales, al menos cuando operan sobre vectores dispersos. El concepto fue introducido por Emmanuel Candès y Terence Tao ^{[ 1 ]} y se utiliza para demostrar muchos teoremas en el campo de la detección comprimida . ^{[ 2 ]} No se conocen matrices grandes con constantes de isometría restringida acotadas (el cálculo de estas constantes es fuertemente NP-difícil , ^{[ 3 ]} y también es difícil de aproximar ^{[ 4 ]} ), pero se ha demostrado que muchas matrices aleatorias permanecen acotadas. En particular, se ha demostrado que con una probabilidad exponencialmente alta, las matrices aleatorias gaussianas, de Bernoulli y de Fourier parcial satisfacen la RIP con un número de mediciones casi lineal en el nivel de dispersión. ^{[ 5 ]} Las cotas superiores más pequeñas actuales para cualquier matriz rectangular grande son las de las matrices gaussianas. ^{[ 6 ]} Los formularios web para evaluar los límites del conjunto gaussiano están disponibles en la página de Edinburgh Compressed Sensing RIC. ^{[ 7 ]}

Sea A una matriz m × p y sea 1 ≤ s ≤ p un número entero. Supongamos que existe una constante      ${\displaystyle \delta _{s}\in (0,1)}$de tal manera que, para cada submatriz m × s A _s de A y para cada vector s -dimensional y ,   

${\displaystyle (1-\delta _{s})\|y\|_{2}^{2}\leq \|A_{s}y\|_{2}^{2}\leq (1+\delta _{s})\|y\|_{2}^{2}.\,}$

Entonces, se dice que la matriz A satisface la propiedad de isometría restringida s con constante de isometría restringida${\displaystyle \delta _{s}}$.

Esta condición es equivalente a la afirmación de que para cada submatriz m × s A _s de A tenemos  

${\displaystyle \|A_{s}^{*}A_{s}-I_{s\times s}\|_{2\to 2}\leq \delta _{s},}$

dónde${\displaystyle I_{s\times s}}$es el${\displaystyle s\times s}$matriz identidad y${\displaystyle \|X\|_{2\to 2}}$es la norma del operador . Véase, por ejemplo ^{, [ 8 ]} para una demostración.

Finalmente, esto equivale a afirmar que todos los autovalores de${\displaystyle A_{s}^{*}A_{s}}$están en el intervalo${\displaystyle [1-\delta _{s},1+\delta _{s}]}$.

La constante RIC se define como el ínfimo de todos los posibles${\displaystyle \delta }$para un dado${\displaystyle A\in \mathbb {R} ^{n\times m}}$.

${\displaystyle \delta _{K}=\inf \left[\delta$ :(1-\delta )\|y\|_{2}^{2}\leq \|A_{s}y\|_{2}^{2}\leq (1+\delta )\|y\|_{2}^{2}\right],\ \forall |s|\leq K,\forall y\in R^{|s|}}

Se denota como${\displaystyle \delta _{K}}$.

Para cualquier matriz que satisfaga la propiedad RIP con un RIC de${\displaystyle \delta _{K}}$, se cumple la siguiente condición: ^{[ 1 ]}

${\displaystyle 1-\delta _{K}\leq \lambda _{min}(A_{\tau }^{*}A_{\tau })\leq \lambda _{max}(A_{\tau }^{*}A_{\tau })\leq 1+\delta _{K}}$.

El límite superior más ajustado del RIC se puede calcular para matrices gaussianas. Esto se logra calculando la probabilidad exacta de que todos los valores propios de las matrices de Wishart se encuentren dentro de un intervalo.

• Detección comprimida
• Coherencia mutua (álgebra lineal)
• El sitio web de Terence Tao sobre detección comprimida enumera varias condiciones relacionadas, como el "Principio de reconstrucción exacta" (ERP) y el "Principio de incertidumbre uniforme" (UUP) ^{[ 9 ].}
• Propiedad de espacio nulo , otra condición suficiente para la recuperación dispersa.
• Propiedad de isometría restringida generalizada, ^{[ 10 ]} una condición suficiente generalizada para la recuperación dispersa, donde la coherencia mutua y la propiedad de isometría restringida son ambas sus formas especiales.
• Lema de Johnson-Lindenstrauss