Title: Generic Cospark of a Matrix Can Be Computed in Polynomial Time,
Abstract: The cospark of a matrix is the cardinality of the sparsest vector in the
column space of the matrix. Computing the cospark of a matrix is well known to
be an NP hard problem. Given the sparsity pattern (i.e., the locations of the
non-zero entries) of a matrix, if the non-zero entries are drawn from
independently distributed continuous probability distributions, we prove that
the cospark of the matrix equals, with probability one, to a particular number
termed the generic cospark of the matrix. The generic cospark also equals to
the maximum cospark of matrices consistent with the given sparsity pattern. We
prove that the generic cospark of a matrix can be computed in polynomial time,
and offer an algorithm that achieves this.