spark(A)?

Spark of matrices

学过线性代数的你，一定知道矩阵的秩，rank(A), 但是你是否知道矩阵A的另外一个类似的概念：spark(A)?

1)你一定知道，rank(A)=A的列向量组的极大线性无关组所含向量的个数（=A的列秩）；
2）而 spark(A)=A的列向量组的极小线性相关组所含向量个数；

看看它们的定义，就知道它们的关系是多么的亲密。遗憾的是，我们对spark(A)知之甚少；

3）对于矩阵的rank,我们有很多结论，这些结论主要来自于矩阵rank的本质：rank(A)反映了矩阵A的整体不变量，它在初等变换下不变；
而spark(A)等价于求解下列的最优化问题：

\[ min ||x||_0 s.t. Ax=0， A\in R^{nxm}, 0\neq x\in R^m (1) \]

4) 问题是：矩阵的任何一种变换都不能用来求解矩阵的spark!!!
5) Furthermore, 上述优化问题为一个NP-hard问题！
6）如何求解(1)? Do you have any idea?