In mathematics, more specifically in linear algebra, the spark of a
is the smallest integer
If all the columns are linearly independent,
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.
Formally, the spark of a matrix
is a nonzero vector and
denotes its number of nonzero coefficients[1] (
is also referred to as the size of the support of a vector).
Equivalently, the spark of a matrix
is the size of its smallest circuit
(a subset of column indices such that
has a nonzero solution, but every subset of it does not[1]).
If all the columns are linearly independent,
[2][3][dubious – discuss] By contrast, the rank of a matrix is the largest number
The spark of this matrix equals 3 because: If
, the following simple properties hold for the spark of a
: The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.
[5] Given a linear equation system
If this system has a solution
denotes the number of nonzero entries of the vector
If the columns of the matrix
are normalized to unit norm, we can lower bound its spark in terms of its dictionary coherence:[6][2] Here, the dictionary coherence
is defined as the maximum correlation between any two columns: 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.