1
$\begingroup$

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?

$\endgroup$
1
1
$\begingroup$

The key phrase to google is "sparsest vector".

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.