# Given $M$, minimize $|Mx|_0$

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?

## 1 Answer

The key phrase to google is "sparsest vector".

• That set me on the right path. Thanks for the direction! – redfly10 May 12 '15 at 18:44
• You're welcome! – Noah Stein May 12 '15 at 18:59