Spark (mathematics)

In mathematics, more specifically in linear algebra, the spark of a ${\displaystyle m\times n}$ matrix ${\displaystyle A}$ is the smallest integer ${\displaystyle k}$ such that there exists a set of ${\displaystyle k}$ columns in ${\displaystyle A}$ which are linearly dependent. If all the columns are linearly independent, ${\displaystyle \mathrm {spark} (A)}$ is usually defined to be 1 more than the number of rows. The concept of matrix spark finds applications in error-correction codes, compressive sensing, and matroid theory, and provides a simple criterion for maximal sparsity of solutions to a system of linear equations.

The spark of a matrix is NP-hard to compute.

Definition

Formally, the spark of a matrix ${\displaystyle A}$ is defined as follows:

${\displaystyle \mathrm {spark} (A)=\min _{d\neq 0}\|d\|_{0}{\text{ s.t. }}Ad=0}$

Eq.1

where ${\displaystyle d}$ is a nonzero vector and ${\displaystyle \|d\|_{0}}$ denotes its number of nonzero coefficients^[1] (${\displaystyle \|d\|_{0}}$ is also referred to as the size of the support of a vector). Equivalently, the spark of a matrix ${\displaystyle A}$ is the size of its smallest circuit ${\displaystyle C}$ (a subset of column indices such that ${\displaystyle A_{C}x=0}$ has a nonzero solution, but every subset of it does not^[1]).

If all the columns are linearly independent, ${\displaystyle \mathrm {spark} (A)}$ is usually defined to be ${\displaystyle m+1}$ (if ${\displaystyle A}$ has m rows).^{[2][3][dubious – discuss]}

By contrast, the rank of a matrix is the largest number ${\displaystyle k}$ such that some set of ${\displaystyle k}$ columns of ${\displaystyle A}$ is linearly independent.^[4]

Example

Consider the following matrix ${\displaystyle A}$.

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

The spark of this matrix equals 3 because:

• There is no set of 1 column of ${\displaystyle A}$ which are linearly dependent.
• There is no set of 2 columns of ${\displaystyle A}$ which are linearly dependent.
• But there is a set of 3 columns of ${\displaystyle A}$ which are linearly dependent. The first three columns are linearly dependent because ${\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}}}$.

Properties

If ${\displaystyle n\geq m}$, the following simple properties hold for the spark of a ${\displaystyle m\times n}$ matrix ${\displaystyle A}$:

• ${\displaystyle \mathrm {spark} (A)=m+1\Rightarrow \mathrm {rank} (A)=m}$ (If the spark equals ${\displaystyle m+1}$, then the matrix has full rank.)
• ${\displaystyle \mathrm {spark} (A)=1}$ if and only if the matrix has a zero column.
• ${\displaystyle \mathrm {spark} (A)\leq \mathrm {rank} (A)+1}$.^[4]

Criterion for uniqueness of sparse solutions

The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.^[5] Given a linear equation system ${\displaystyle A\mathbf {x} =\mathbf {b} }$. If this system has a solution ${\displaystyle \mathbf {x} }$ that satisfies ${\displaystyle \|\mathbf {x} \|_{0}<{\frac {\mathrm {spark} (A)}{2}}}$, then this solution is the sparsest possible solution. Here ${\displaystyle \|\mathbf {x} \|_{0}}$ denotes the number of nonzero entries of the vector ${\displaystyle \mathbf {x} }$.

Lower bound in terms of dictionary coherence

If the columns of the matrix ${\displaystyle A}$ are normalized to unit norm, we can lower bound its spark in terms of its dictionary coherence:^[6][2]

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

Here, the dictionary coherence ${\displaystyle \mu (A)}$ is defined as the maximum correlation between any two columns:

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

Applications

The minimum distance of a linear code equals the spark of its parity-check matrix.

The concept of the spark is also of use in the theory of compressive sensing, where requirements on the spark of the measurement matrix are used to ensure stability and consistency of various estimation techniques.^[4] It is also known in matroid theory as the girth of the vector matroid associated with the columns of the matrix. The spark of a matrix is NP-hard to compute.^[1]

References

1. Tillmann, Andreas M.; Pfetsch, Marc E. (November 8, 2013). "The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing". 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 (2015-09-15). The Princeton Companion to Applied Mathematics. Princeton University Press. ISBN 978-1-4008-7447-7.
3. Manchanda, Pammy; Lozi, René; Siddiqi, Abul Hasan (2017-10-18). Industrial Mathematics and Complex Systems: Emerging Mathematical Models, Methods and Algorithms. Springer. ISBN 978-981-10-3758-0.
4. Donoho, David L.; Elad, Michael (March 4, 2003), "Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ¹ minimization", 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). Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing. pp. 24.
6. Elad, Michael (2010). Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing. pp. 26.