Chispa (matemáticas)

Menos columnas dependientes en una matriz

En matemáticas , más concretamente en álgebra lineal , la chispa de una matriz es el número entero más pequeño tal que exista un conjunto de columnas en las que son linealmente dependientes . Si todas las columnas son linealmente independientes, generalmente se define 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 de compresión y teoría matroide , y proporciona un criterio simple para la máxima escasez de soluciones a 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 conoce como el 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 que tiene una solución distinta de cero, pero cada subconjunto 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 algún conjunto de columnas sea 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 hay un conjunto de 1 columna de las cuales sean linealmente dependientes. ${\displaystyle A}$
• No hay un conjunto de 2 columnas que sean linealmente dependientes. ${\displaystyle A}$
• Pero hay un conjunto de 3 columnas de las cuales 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 sólo 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 escasa 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 están normalizadas a la norma unitaria , podemos limitar 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 cualesquiera: ${\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 verificación de paridad .

El concepto de chispa también se utiliza en la teoría de la detección de compresión , donde los requisitos sobre la chispa de la matriz de medición se utilizan para garantizar la estabilidad y coherencia de varias técnicas de estimación. ^[4] 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. ^[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". Transacciones IEEE sobre teoría de la información . 60 (2): 1248-1259. arXiv : 1205.2081 . doi :10.1109/TIT.2013.2290112. S2CID  2788088.
2. Higham, Nicholas J.; Dennis, Mark R.; Glendinning, Paul; Martín, Pablo A.; Santosa, Fadil; Tanner, Jared (15 de septiembre de 2015). El compañero de Princeton para las matemáticas aplicadas. Prensa de la Universidad de Princeton. 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, métodos y algoritmos matemáticos emergentes. Saltador. ISBN 978-981-10-3758-0.
4. Donoho, David L .; Elad, Michael (4 de marzo de 2003), "Representación óptimamente escasa en diccionarios generales (no ortogonales) mediante minimización ℓ ^{1 ",} Proc. Nacional. Acad. Ciencia. , 100 (5): 2197–2202, Bibcode : 2003PNAS..100.2197D, doi : 10.1073/pnas.0437847100 , PMC 153464 , PMID  16576749 
5. Elad, Michael (2010). Representaciones escasas y redundantes desde la teoría hasta las aplicaciones en el procesamiento de señales e imágenes . págs.24.
6. Elad, Michael (2010). Representaciones escasas y redundantes desde la teoría hasta las aplicaciones en el procesamiento de señales e imágenes . págs.26.