Spark

In mathematics, more specifically in linear algebra, the spark of a matrix is the smallest integer such that there exists a set of columns in which are linearly dependent. If all the columns are linearly independent, is usually defined to be 1 more than the number of rows. The concept of matrix spark finds applications in error-correction codes, compressive sensing, and matroid theory, and provides a simple criterion for maximal sparsity of solutions to a system of linear equations. The spark of a matrix is NP-hard to compute. Definition Formally, the spark of a matrix is defined as follows: where is a nonzero vector and denotes its number of nonzero coefficients ( is also referred to as the size of the support of a vector). Equivalently, the spark of a matrix is the size of its smallest circuit (a subset of column indices such that has a nonzero solution, but every subset of it does not).