Generic Cospark of a Matrix Can Be Computed in Polynomial Time

Sichen Zhong, Yue Zhao

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…