“Spark (mathematics)”的意思、由来-开放百科全书

In mathematics, specifically in linear algebra, the spark of a

matrix

is the smallest number

such that there exists a set of

columns in

which are linearly dependent. Formally,

By contrast, the rank of a matrix is the largest number

such that some set of

columns of

is linearly independent.

Example

Properties

Criterion for uniqueness of sparse solutions

The spark yields a simple criterion for uniqueness of sparse solutions of linear equation systems.^[1]

Given a linear equation system

. If this system has a solution

that satisfies

, then this solution is the sparsest possible solution. Here

denotes the number of nonzero entries of the vector

Lower bound in terms of dictionary coherence

If the columns of the matrix

are normalized to unit norm, we can lower bound the spark of the matrix in terms of the dictionary coherence:^[2]

The dictionary coherence

is defined as the maximum correlation between any two columns, i.e.

Applications

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.^[3] 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.^[4]

References

1. ^{{cite book | last = Elad | first = Michael | title = Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing | pages = 24 | year = 2010}}
2. ^{{cite book | last = Elad | first = Michael | title = Sparse and Redundant Representations From Theory to Applications in Signal and Image Processing | pages = 26 | year = 2010}}
3. ^{{Citation | last = Donoho | first = 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 }}
4. ^{{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}}

Definition

Example

Properties

Criterion for uniqueness of sparse solutions

Lower bound in terms of dictionary coherence

Applications

References