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-hard , ^[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 escasez. ^[5] Los límites superiores más pequeños actuales para cualquier matriz rectangular grande son los de las matrices gaussianas. ^[6] Los formularios web para evaluar los límites para el conjunto gaussiano están disponibles en la página RIC de detección comprimida de Edimburgo. ^[7]

Definición

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

${\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},}$

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

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

Constante isométrica restringida (RIC)

La constante RIC se define como el mínimo de todos los posibles para un dado . ${\displaystyle \delta }$ ${\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}}$

Valores propios

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

${\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 estricto del RIC se puede calcular para matrices gaussianas. Esto se puede lograr calculando la probabilidad exacta de que todos los valores propios de las matrices de Wishart se encuentren dentro de un intervalo.

Véase también

• 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 del 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

Referencias

1. EJ Candes y T. Tao, "Decodificación mediante programación lineal", IEEE Trans. Inf. Th., 51(12): 4203–4215 (2005).
2. EJ Candes, JK Romberg y T. Tao, "Recuperación de señales estables a partir de mediciones incompletas e inexactas", Communications on Pure and Applied Mathematics, vol. LIX, 1207–1223 (2006).
3. AM Tillmann y ME Pfetsch, "La complejidad computacional de la propiedad de isometría restringida, la propiedad del espacio nulo y conceptos relacionados en la detección comprimida", IEEE Trans. Inf. Th., 60(2): 1248–1259 (2014)
4. Abhiram Natarajan y Yi Wu, "Complejidad computacional de la certificación de la propiedad de isometría restringida", Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas (APPROX/RANDOM 2014) (2014)
5. F. Yang, S. Wang y C. Deng, " Detección compresiva de reconstrucción de imágenes mediante transformada multi-wavelet ", IEEE 2010
6. B. Bah y J. Tanner "Límites mejorados en constantes de isometría restringida para matrices gaussianas"
7. "Universidad de Edimburgo - Facultad de Matemáticas - Grupo de detección comprimida - Constantes de isometría restringida". Archivado desde el original el 27 de abril de 2010. Consultado el 31 de marzo de 2010 .
8. "Introducción matemática a la detección por compresión" (PDF) . Cis.pku.edu.cn . Consultado el 15 de mayo de 2018 .
9. "Detección comprimida". Math.ucla.edu . Consultado el 15 de mayo de 2018 .
10. Yu Wang, Jinshan Zeng, Zhimin Peng, Xiangyu Chang y Zongben Xu (2015). "Sobre la convergencia lineal de algoritmos de umbralización iterativos adaptativos para detección comprimida". IEEE Transactions on Signal Processing . 63 (11): 2957–2971. arXiv : 1408.6890 . Bibcode :2015ITSP...63.2957W. doi :10.1109/TSP.2015.2412915. S2CID  10734058.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )