Chispa (matemáticas)

Menos columnas dependientes en una matriz

En matemáticas , más específicamente en álgebra lineal , la chispa de una matriz es el número entero más pequeño tal que existe un conjunto de columnas en las que son linealmente dependientes . Si todas las columnas son linealmente independientes, se define generalmente como 1 más que el número de filas. El concepto de chispa matricial encuentra aplicaciones en códigos de corrección de errores , detección compresiva y teoría de matroides , y proporciona un criterio simple para la escasez máxima de soluciones para un sistema de ecuaciones lineales . ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle \mathrm {spark} (A)}$

La chispa de una matriz es NP-difícil de calcular.

Definición

Formalmente, la chispa de una matriz se define de la siguiente manera: ${\displaystyle A}$

donde es un vector distinto de cero y denota su número de coeficientes distintos de cero ^[1] ( también se denomina tamaño del soporte de un vector). De manera equivalente, la chispa de una matriz es el tamaño de su circuito más pequeño (un subconjunto de índices de columna tal que tiene una solución distinta de cero, pero cada subconjunto de él no la tiene ^[1] ). ${\displaystyle d}$ ${\displaystyle \|d\|_{0}}$ ${\displaystyle \|d\|_{0}}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle A_{C}x=0}$

Si todas las columnas son linealmente independientes, generalmente se define como (si tiene m filas). ^{[2] [3] [ dudoso – discutir ]} ${\displaystyle \mathrm {spark} (A)}$ ${\displaystyle m+1}$ ${\displaystyle A}$

Por el contrario, el rango de una matriz es el número más grande tal que un conjunto de columnas es linealmente independiente. ^[4] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle A}$

Ejemplo

Considere la siguiente matriz . ${\displaystyle A}$

${\displaystyle A={\begin{bmatrix}1&2&0&1\\1&2&0&2\\1&2&0&3\\1&0&-3&4\end{bmatrix}}}$

La chispa de esta matriz es igual a 3 porque:

• No existe ningún conjunto de 1 columna que sean linealmente dependientes. ${\displaystyle A}$
• No existe ningún conjunto de 2 columnas que sean linealmente dependientes. ${\displaystyle A}$
• Pero hay un conjunto de 3 columnas que son linealmente dependientes. Las primeras tres columnas son linealmente dependientes porque . ${\displaystyle A}$ ${\displaystyle {\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}-{\frac {1}{2}}{\begin{pmatrix}2\\2\\2\\0\end{pmatrix}}+{\frac {1}{3}}{\begin{pmatrix}0\\0\\0\\-3\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\0\end{pmatrix}}}$

Propiedades

Si , las siguientes propiedades simples se cumplen para la chispa de una matriz : ${\displaystyle n\geq m}$ ${\displaystyle m\times n}$ ${\displaystyle A}$

• ${\displaystyle \mathrm {spark} (A)=m+1\Rightarrow \mathrm {rank} (A)=m}$(Si la chispa es igual a , entonces la matriz tiene rango completo.) ${\displaystyle m+1}$
• ${\displaystyle \mathrm {spark} (A)=1}$si y solo si la matriz tiene una columna cero.
• ${\displaystyle \mathrm {spark} (A)\leq \mathrm {rank} (A)+1}$. ^[4]

Criterio de unicidad de soluciones dispersas

La chispa produce un criterio simple para la unicidad de soluciones dispersas de sistemas de ecuaciones lineales . ^[5] 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 dispersa posible. Aquí denota el número de entradas distintas de cero del vector . ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \|\mathbf {x} \|_{0}<{\frac {\mathrm {spark} (A)}{2}}}$ ${\displaystyle \|\mathbf {x} \|_{0}}$ ${\displaystyle \mathbf {x} }$

Límite inferior en términos de coherencia del diccionario

Si las columnas de la matriz se normalizan a la norma unitaria , podemos limitar inferiormente su chispa en términos de su coherencia de diccionario: ^{[6] [2]} ${\displaystyle A}$

${\displaystyle \mathrm {spark} (A)\geq 1+{\frac {1}{\mu (A)}}}$.

Aquí, la coherencia del diccionario se define como la correlación máxima entre dos columnas: ${\displaystyle \mu (A)}$

${\displaystyle \mu (A)=\max _{m\neq n}|\langle a_{m},a_{n}\rangle |=\max _{m\neq n}{\frac {|a_{m}^{\intercal }a_{n}|}{||a_{m}||_{2}||a_{n}||_{2}}}}$.

Aplicaciones

La distancia mínima de un código lineal es igual a la chispa de su matriz de comprobación de paridad .

El concepto de chispa también se utiliza en la teoría de detección compresiva , donde los requisitos de la chispa de la matriz de medición se utilizan para garantizar la estabilidad y la consistencia de varias técnicas de estimación. ^[4] También se conoce en la teoría de matroides como la circunferencia del matroide vectorial asociado con las columnas de la matriz. La chispa de una matriz es NP-difícil de calcular. ^[1]

Referencias

1. Tillmann, Andreas M.; Pfetsch, Marc E. (8 de noviembre de 2013). "La complejidad computacional de la propiedad de isometría restringida, la propiedad del espacio nulo y conceptos relacionados en la detección comprimida". IEEE Transactions on Information Theory . 60 (2): 1248–1259. arXiv : 1205.2081 . doi :10.1109/TIT.2013.2290112. S2CID  2788088.
2. Higham, Nicholas J.; Dennis, Mark R.; Glendinning, Paul; Martin, Paul A.; Santosa, Fadil; Tanner, Jared (15 de septiembre de 2015). The Princeton Companion to Applied Mathematics. Princeton University Press. ISBN 978-1-4008-7447-7.
3. Manchanda, Pammy; Lozi, René; Siddiqi, Abul Hasan (18 de octubre de 2017). Matemáticas industriales y sistemas complejos: modelos matemáticos emergentes, métodos y algoritmos. Springer. ISBN 978-981-10-3758-0.
4. Donoho, David L. ; Elad, Michael (4 de marzo de 2003), "Representación óptimamente dispersa en diccionarios generales (no ortogonales) mediante la 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 
5. Elad, Michael (2010). Representaciones dispersas y redundantes: de la teoría a las aplicaciones en el procesamiento de señales e imágenes . pp. 24.
6. Elad, Michael (2010). Representaciones dispersas y redundantes: de la teoría a las aplicaciones en el procesamiento de señales e imágenes . pp. 26.