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?



Given $M$, minimize $|Mx|_0$
The key phrase to google is "sparsest vector".


