Spark (mathematics)

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]

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

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]

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