Definición
En matemáticas , específicamente en álgebra lineal , la chispa de un matriz es el número más pequeño tal que existe un conjunto de columnas en que son linealmente dependientes . Formalmente,
( Ecuación 1 )
dónde es un vector distinto de cero y denota su número de coeficientes distintos de cero.
Si todas las columnas son linealmente independientes, generalmente se define como .
Por el contrario, el rango de una matriz es el número más grande tal que algún conjunto de columnas de es linealmente independiente.
Ejemplo
Considere la siguiente matriz .
La chispa de esta matriz es igual a 3 porque:
- No hay un conjunto de 1 columna de que son linealmente dependientes.
- No hay un conjunto de 2 columnas de que son linealmente dependientes.
- Pero hay un conjunto de 3 columnas de que son linealmente dependientes.
Las primeras tres columnas son linealmente dependientes porque .
Propiedades
Si , las siguientes propiedades simples son válidas para la chispa de un matriz :
- (Si la chispa es igual a , entonces la matriz tiene rango completo).
- si y solo si la matriz tiene una columna cero.
- .
Criterio de singularidad de soluciones escasas
La chispa produce un criterio simple de unicidad de soluciones escasas de sistemas de ecuaciones lineales . [1] Dado un sistema de ecuaciones lineales. Si este sistema tiene una solución que satisface , entonces esta solución es la solución más escasa posible. Aquí denota el número de entradas distintas de cero del vector .
Límite inferior en términos de coherencia del diccionario
Si las columnas de la matriz están normalizados a la norma unitaria , podemos limitar la chispa de la matriz en términos de coherencia del diccionario: [2]
La coherencia del diccionario se define como la correlación máxima entre dos columnas cualesquiera, es decir
- .
Aplicaciones
La distancia mínima de un código lineal es igual a la chispa de su matriz de verificación de paridad .
El concepto de chispa también se utiliza en la teoría de la detección por compresión , donde los requisitos sobre la chispa de la matriz de medición se utilizan para garantizar la estabilidad y consistencia de varias técnicas de estimación. [3] También se conoce en la teoría matroide como la circunferencia del vector matroide asociado con las columnas de la matriz. La chispa de una matriz es NP-difícil de calcular. [4]
Referencias
- ^ Elad, Michael (2010). Representaciones dispersas y redundantes desde la teoría hasta las aplicaciones en el procesamiento de señales e imágenes . págs. 24 .
- ^ Elad, Michael (2010). Representaciones dispersas y redundantes desde la teoría hasta las aplicaciones en el procesamiento de señales e imágenes . págs. 26 .
- ^ Donoho, David L .; Elad, Michael (4 de marzo de 2003), "Representación óptimamente dispersa en diccionarios generales (no ortogonales) mediante minimización de 1 ", Proc. Natl. Acad. Sci. , 100 (5): 2197–2202, Bibcode : 2003PNAS..100.2197D , doi : 10.1073 / pnas.0437847100 , PMC 153464 , PMID 16576749
- ^ Tillmann, Andreas M .; Pfetsch, Marc E. (8 de noviembre de 2013). "La complejidad computacional de la propiedad de isometría restringida, la propiedad de espacio nulo y conceptos relacionados en la detección comprimida". Transacciones IEEE sobre teoría de la información . 60 (2): 1248-1259. arXiv : 1205.2081 . doi : 10.1109 / TIT.2013.2290112 .