Given a matrix $M \in \mathbb{R}^{n \times m}$, I would like to find
$\min_{x \in \mathbb{R}^m} \|Mx\|_0$ such that $x \neq 0^m$,
where the $\ell_0$ "norm" is measured by simply counting the number of nonzero entries in the vector. In my application, $n$ is typically $10^7$, $m$ is typically $10^4$, and $M$ is a binary matrix made up of approximately 1% ones, 99% zeroes. Note that I don't care about the $\arg\min$ (the value of $x$ that gives the minimum). I'm only interested in knowing the minimum value that $\|Mx\|_0$ can achieve for nonzero $x$.
The most closely related problem I know of comes from compressive sensing, where we wish to find $\min_x \|x\|_0$ such that $y = Mx$ for some known $y$. In general, this problem is NP-hard, but there are many interesting approximation techniques (such as replacing the $\ell_0$ "norm" with the $\ell_1$ norm). Perhaps some tools from that area could be borrowed?
