spark of a matrix

Let 𝔽 be a field, and let m,nβˆˆβ„•βˆ–{0}. Consider an mΓ—n matrix A whose entries belong to 𝔽. Let C1,…,Cnβˆˆπ”½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

βˆƒj1,…,jk∈{1,…,n}:{j1<…<jk,𝐢𝑗1⁒, …, Cπ‘—π‘˜β’a⁒r⁒e⁒l⁒i⁒n⁒e⁒a⁒r⁒l⁒y⁒d⁒e⁒p⁒e⁒n⁒d⁒e⁒n⁒t⁒(o⁒v⁒e⁒r⁒𝔽).

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) spark⁒(A)∈{1,…,n}βˆͺ{+∞}, (ii) spark⁒(A)=+βˆžβ‡”rank⁒(A)=n, (iii) spark⁒(A)=1 if and only if the matrix A has a zero column, (iv) if spark⁒(A)β‰ +∞, then spark⁒(A)≀rank⁒(A)+1.
Moreover, spark⁒(A) coincides with the infimum of the set {βˆ₯xβˆ₯0:x∈Fnβˆ–{0},A⁒x=0}, where βˆ₯xβˆ₯0 is the Hamming weight of x and 0 stands for the appropriate zero vectorsMathworldPlanetmath.


  • 1 D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via β„“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