spark (mathematics)

Formally, the spark of a matrix $A$ is defined as follows:

{{Equation box 1

|indent =

|title=

|equation = {{NumBlk|:|$\backslash mathrm\{spark\}(A)\; =\; \backslash min\_\{d\; \backslash ne\; 0\}\; \backslash |d\backslash |\_0\; \backslash text\{\; s.t.\; \}\; A\; d\; =\; 0$|{{EquationRef|Eq.1}}}}

|cellpadding= 6

|border

|border colour = #0073CF

|background colour=#F5FFFA}}

where $d$ is a nonzero vector and $\backslash |d\backslash |\_0$ denotes its number of nonzero coefficients ($\backslash |d\backslash |\_0$ is also referred to as the size of the support of a vector). Equivalently, the spark of a matrix $A$ is the size of its smallest circuit $C$ (a subset of column indices such that $A\_C\; x\; =\; 0$ has a nonzero solution, but every subset of it does not).

If all the columns are linearly independent, $\backslash mathrm\{spark\}(A)$ is usually defined to be $m+1$ (if $A$ has m rows).{{Cite book|last1=Higham|first1=Nicholas J.|url=https://books.google.com/books?id=MvI8CgAAQBAJ&dq=%22spark%22+%22mathematics%22+%22matrix%22&pg=PA824|title=The Princeton Companion to Applied Mathematics|last2=Dennis|first2=Mark R.|last3=Glendinning|first3=Paul|last4=Martin|first4=Paul A.|last5=Santosa|first5=Fadil|last6=Tanner|first6=Jared|date=2015-09-15|publisher=Princeton University Press|isbn=978-1-4008-7447-7|language=en}}{{Cite book|last1=Manchanda|first1=Pammy|url=https://books.google.com/books?id=Cr06DwAAQBAJ&dq=%22spark%22+%22mathematics%22+%22matrix%22&pg=PA35|title=Industrial Mathematics and Complex Systems: Emerging Mathematical Models, Methods and Algorithms|last2=Lozi|first2=René|last3=Siddiqi|first3=Abul Hasan|date=2017-10-18|publisher=Springer|isbn=978-981-10-3758-0|language=en}}{{Dubious|date=May 2024|Definition in case of full column rank}}

By contrast, the rank of a matrix is the largest number $k$ such that some set of $k$ columns of $A$ is linearly independent.

Consider the following matrix $A$.

$$

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 $A$ which are linearly dependent.
• There is no set of 2 columns of $A$ which are linearly dependent.
• But there is a set of 3 columns of $A$ which are linearly dependent. The first three columns are linearly dependent because $\backslash begin\{pmatrix\}1\backslash \backslash 1\backslash \backslash 1\backslash \backslash 1\backslash end\{pmatrix\}\; -\; \backslash frac\{1\}\{2\}\backslash begin\{pmatrix\}2\backslash \backslash 2\backslash \backslash 2\backslash \backslash 0\backslash end\{pmatrix\}\; +\; \backslash frac\{1\}\{3\}\backslash begin\{pmatrix\}0\backslash \backslash 0\backslash \backslash 0\backslash \backslash -3\backslash end\{pmatrix\}\; =\; \backslash begin\{pmatrix\}0\backslash \backslash 0\backslash \backslash 0\backslash \backslash 0\backslash end\{pmatrix\}$.

If $n\backslash geq\; m$, the following simple properties hold for the spark of a $m\; \backslash times\; n$ matrix $A$:

• $\backslash mathrm\{spark\}(A)\; =\; m+1\; \backslash Rightarrow\; \backslash mathrm\{rank\}(A)\; =\; m$ (If the spark equals $m+1$, then the matrix has full rank.)
• $\backslash mathrm\{spark\}(A)\; =\; 1$ if and only if the matrix has a zero column.
• $\backslash mathrm\{spark\}(A)\; \backslash le\; \backslash mathrm\{rank\}(A)\; +\; 1$.

The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.{{cite book

| last = Elad

| first = Michael

| title = Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing

| url = https://archive.org/details/sparseredundantr00elad_246

| url-access = limited

| pages = [https://archive.org/details/sparseredundantr00elad_246/page/n44 24]

| year = 2010}}

Given a linear equation system $A\backslash mathbf\{x\}=\backslash mathbf\{b\}$. If this system has a solution $\backslash mathbf\{x\}$ that satisfies , then this solution is the sparsest possible solution. Here $\backslash |\backslash mathbf\{x\}\backslash |\_\{0\}$ denotes the number of nonzero entries of the vector $\backslash mathbf\{x\}$.

If the columns of the matrix $A$ are normalized to unit norm, we can lower bound its spark in terms of its dictionary coherence:{{cite book

| last = Elad

| first = Michael

| title = Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing

| url = https://archive.org/details/sparseredundantr00elad_246

| url-access = limited

| pages = [https://archive.org/details/sparseredundantr00elad_246/page/n46 26]

| year = 2010}}

:$\backslash mathrm\{spark\}(A)\; \backslash ge\; 1+\backslash frac\{1\}\{\backslash mu(A)\}$.

Here, the dictionary coherence $\backslash mu(A)$ is defined as the maximum correlation between any two columns:

:$\backslash mu(A)=\backslash max\_\{m\; \backslash neq\; n\}\; |\backslash langle\; a\_m,a\_n\; \backslash rangle|\; =\; \backslash max\_\{m\backslash neq\; n\}\backslash frac$

a_m^{\intercal} a_n

{||a_m||_2||a_n||_2} .

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.{{Citation

| last1 = Donoho

| first1 = David L.

| author-link = David Donoho

| last2 = Elad

| first2 = Michael

| author2-link =

| title = Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ¹ minimization

| journal = Proc. Natl. Acad. Sci.

| volume = 100

| issue = 5

| pages = 2197–2202

| date = March 4, 2003

| doi = 10.1073/pnas.0437847100

| id =

| pmid = 16576749

| pmc = 153464 | bibcode = 2003PNAS..100.2197D

| doi-access = free

}} 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.{{cite journal|last=Tillmann|first=Andreas M.|author2=Pfetsch, Marc E. |title=The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing|journal=IEEE Transactions on Information Theory|date=November 8, 2013|volume=60|issue=2|page=1248–1259|doi=10.1109/TIT.2013.2290112|arxiv=1205.2081|s2cid=2788088}}

{{reflist|30em}}

Category:Signal processing

Category:Matrix theory