Spark (mathematics)

Definition.
In mathematics, specifically in linear algebra, the spark of a formula_1 matrix formula_2 is the smallest number formula_3 such that there exists a set of formula_3 columns in formula_2 which are linearly dependent. Formally,
where formula_6 is a nonzero vector and formula_7 denotes its number of nonzero coefficients.
If all the columns are linearly independent, formula_8 is usually defined to be formula_9.
By contrast, the rank of a matrix is the largest number formula_3 such that some set of formula_3 columns of formula_2 is linearly independent.
Example.
Consider the following matrix formula_2.
formula_14
The spark of this matrix equals 3 because:
The first three columns are linearly dependent because formula_18.
Properties.
If formula_19, the following simple properties hold for the spark of a formula_1 matrix formula_2:
Criterion for uniqueness of sparse solutions.
The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.
Given a linear equation system formula_26. If this system has a solution formula_27 that satisfies formula_28, then this solution is the sparsest possible solution. Here formula_29 denotes the number of nonzero entries of the vector formula_27.
Lower bound in terms of dictionary coherence.
If the columns of the matrix formula_2 are normalized to unit norm, we can lower bound the spark of the matrix in terms of the dictionary coherence:
The dictionary coherence formula_33 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.