Spark (mathematics)


Definition
In mathematics, specifically in linear algebra, the spark of a matrix is the smallest number such that there exists a set of columns in which are linearly dependent. Formally,
where is a nonzero vector and denotes its number of nonzero coefficients.
If all the columns are linearly independent, is usually defined to be.
By contrast, the rank of a matrix is the largest number such that some set of columns of is linearly independent.

Example

Consider the following matrix.
The spark of this matrix equals 3 because:
The first three columns are linearly dependent because.

Properties

If, the following simple properties hold for the spark of a matrix :
The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.
Given a linear equation system. If this system has a solution that satisfies, then this solution is the sparsest possible solution. Here denotes the number of nonzero entries of the vector.

Lower bound in terms of dictionary coherence

If the columns of the matrix are normalized to unit norm, we can lower bound the spark of the matrix in terms of the dictionary coherence:
The dictionary coherence is defined as the maximum correlation between any two columns, i.e.

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. 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.