TY - GEN
T1 - Generic cospark of a matrix can be computed in polynomial time
AU - Zhong, Sichen
AU - Zhao, Yue
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/8/9
Y1 - 2017/8/9
N2 - 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, it is shown that the cospark equals, with probability one, to a particular number we term the generic cospark of the matrix. It is proven that, unlike the cospark, the generic cospark of a matrix can be computed in polynomial time. An efficient algorithm that achieves this is offered.
AB - 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, it is shown that the cospark equals, with probability one, to a particular number we term the generic cospark of the matrix. It is proven that, unlike the cospark, the generic cospark of a matrix can be computed in polynomial time. An efficient algorithm that achieves this is offered.
UR - https://www.scopus.com/pages/publications/85034095351
U2 - 10.1109/ISIT.2017.8006527
DO - 10.1109/ISIT.2017.8006527
M3 - Conference contribution
AN - SCOPUS:85034095351
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 246
EP - 250
BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017
Y2 - 25 June 2017 through 30 June 2017
ER -