spark of a matrix

Let $\mathbb{F}$ be a field, and let $m,n\in\mathbb{N}\setminus\{0\}.$ Consider an $m\times n$ matrix $A$ whose entries belong to $\mathbb{F}.$ Let $\displaystyle C_{1},\ldots,C_{n}\in\mathbb{F}^{m}$ be the columns of $A .$

Definition 1

The spark of the matrix $A$ is defined to be the infimum of the set of all positive integers $k$ with the property that

\exists\,j_{1},\ldots,j_{k}\in\{1,\ldots,n\}:\,\left\{\begin{array}[]{l}j_{1}<% \ldots<j_{k},\\ $\displaystyle C_{j_{1}}, \ldots, C_{j_{k}}$arelinearlydependent(over$\mathbb{% F}$).\end{array}\right.

The notion of spark of a matrix was introduced by Donoho and Elad in [1]. It is strictly related to Compressed Sensing. The word “spark” comes from a verbal fusion of “sparse” and “rank”.

Remark 2

The following properties hold true:
(i) ${\rm spark}(A)\in\{1,\ldots,n\}\cup\{+\infty\},$ (ii) ${\rm spark}(A)=+\infty\,\Leftrightarrow\,{\rm rank}(A)=n,$ (iii) ${\rm spark}(A)=1$ if and only if the matrix $A$ has a zero column, (iv) if ${\rm spark}(A)\neq+\infty,$ then ${\rm spark}(A)\leq{\rm rank}(A)+1.$
Moreover, ${\rm spark}(A)$ coincides with the infimum of the set $\displaystyle\left\{\left\|x\right\|_{0}:\,x\in\mathbb{F}^{n}\setminus\{{\bf 0% }\},\,Ax={\bf 0}\right\}$ , where $\displaystyle\left\|x\right\|_{0}$ is the Hamming weight of $x$ and ${\bf 0}$ stands for the appropriate zero vectors.

References

1 D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^{1}$ minimization, Proc. Natl. Acad. Sci. USA 100, No. 5: 2197 – 2202 (2003).

Title	spark of a matrix
Canonical name	SparkOfAMatrix
Date of creation	2013-03-22 19:36:23
Last modified on	2013-03-22 19:36:23
Owner	kammerer (26336)
Last modified by	kammerer (26336)
Numerical id	21
Author	kammerer (26336)
Entry type	Definition
Classification	msc 15A03
Related topic	RankOfAMatrix