En álgebra lineal , la propiedad de isometría restringida ( RIP ) caracteriza las matrices que son casi ortonormales, al menos cuando operan en vectores dispersos. El concepto fue introducido por Emmanuel Candès y Terence Tao [1] y se utiliza para probar muchos teoremas en el campo de la detección comprimida . [2] No se conocen matrices grandes con constantes de isometría restringidas acotadas (calcular 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 limitadas. En particular, se ha demostrado que con una probabilidad exponencialmente alta, las matrices gaussianas aleatorias, de Bernoulli y de Fourier parciales satisfacen el RIP con un número de mediciones casi lineal en el nivel de dispersión. [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 del conjunto gaussiano están disponibles en la página RIC de detección comprimida de Edimburgo. [7]
Definición
Sea A una matriz de m × p y sea 1 ≤ s ≤ p un número entero. Supongamos que existe una constantetal que, para cada submatriz A s de m × s de A y para cada vector s -dimensional y ,
Entonces, se dice que la matriz A satisface la propiedad de isometría restringida por s con constante de isometría restringida.
Esto es equivalente a
dónde es la matriz de identidad y es la norma del operador . Ver por ejemplo [8] para una prueba.
Finalmente, esto equivale a afirmar que todos los valores propios de están en el intervalo .
Constante isométrica restringida (RIC)
La constante RIC se define como el mínimo de todos los posibles para una dada .
Se denota como .
Autovalores
Para cualquier matriz que satisfaga la propiedad RIP con un RIC de , se cumple la siguiente condición: [1]
- .
El límite superior más ajustado en el 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.
Ver 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 de espacio nulo , otra condición suficiente para una recuperación escasa
- Propiedad de isometría restringida generalizada, [10] una condición suficiente generalizada para una recuperación escasa, donde la coherencia mutua y la propiedad de isometría restringida son sus dos formas especiales.
Referencias
- ^ a b E. J. Candes y T. Tao, "Decodificación por programación lineal", IEEE Trans. Inf. Th., 51 (12): 4203–4215 (2005).
- ^ EJ Candes, JK Romberg y T. Tao, "Recuperación de señal estable de mediciones incompletas e inexactas", Comunicaciones sobre matemáticas puras y aplicadas, vol. LIX, 1207-1223 (2006).
- ^ AM Tillmann y ME Pfetsch, " La complejidad computacional de la propiedad de isometría restringida, la propiedad de espacio nulo y conceptos relacionados en la detección comprimida ", IEEE Trans. Inf. Th., 60 (2): 1248-1259 (2014)
- ^ Abhiram Natarajan y Yi Wu, " Complejidad computacional de la certificación de propiedad de isometría restringida ", Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas (APPROX / RANDOM 2014) (2014)
- ^ F. Yang, S. Wang y C. Deng, " Detección por compresión de la reconstrucción de imágenes mediante la transformación de ondas múltiples ", IEEE 2010
- ^ B. Bah y J. Tanner "Límites mejorados en constantes de isometría restringida para matrices gaussianas"
- ^ "Copia archivada" . Archivado desde el original el 27 de abril de 2010 . Consultado el 31 de marzo de 2010 .CS1 maint: copia archivada como título ( enlace )
- ^ "Una introducción matemática a la detección compresiva" (PDF) . Cis.pku.edu.cn . Consultado el 15 de mayo de 2018 .
- ^ "Detección comprimida" . Math.ucla.edu . Consultado el 15 de mayo de 2018 .
- ^ 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". Transacciones IEEE sobre procesamiento de señales . 63 (11): 2957–2971. arXiv : 1408,6890 . doi : 10.1109 / TSP.2015.2412915 . S2CID 10734058 .CS1 maint: varios nombres: lista de autores ( enlace )