1
$\begingroup$

Given a $d$ dimensional vector $\bar{x} = [x_0,...,x_d]^t$,

how do I minimize $||\bar{x}-\bar{y}||_p$ such that $A\bar{y}=0$, for $p= 0$ i.e.,Minimize $L_0$ norm.

I also have the constraints that $\bar{x},\bar{y} \in Z^d$ (and not in $R^d$). and the components of the vectors are bounded. $-N \le y_i \le N$.

The exhaustive search is too complex for me to evaluate since it is exponential complexity. The matrix $A$ contains only entries -1,0,1.

Thanks in advance for any help.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is $A$ a square matrix? If not, do you have some condition on the number of rows of $A$? $\endgroup$
    – Gerry Myerson
    Mar 8, 2012 at 22:01
  • $\begingroup$ What is the $L_0$ norm? The number of nonzero components? This is not standard notation. $\endgroup$
    – Igor Rivin
    Mar 8, 2012 at 22:28
  • $\begingroup$ @Gerry $A$ is not a square matrix. But it is very sparse. each row contains three non zero elements that are +1 or -1. @Igor Yes i meant nonzero components. $\endgroup$
    – Deepu
    Mar 9, 2012 at 5:45

2 Answers 2

Reset to default
0
$\begingroup$

The problem is NP-hard, however minimizing $L^2$ or $L^1$ norm generally gives a good approximation.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ My understanding is that $L^1$ is a common convex surrogate for $L^0$ which works well in many cases, but I have heard $L^2$ referred to as "the enemy of sparsity". Intuitively this makes some kind of sense because $L^2$ gives a preference to spreading mass equally over all elements of the residual vector whereas $L^1$ does not. From this perspective I suppose the real enemy of sparsity should be $L^{\infty}$. $\endgroup$
    – Noah Stein
    Mar 8, 2012 at 23:04
  • $\begingroup$ @Noah, you are right, $L^1$ is th right thing... $\endgroup$
    – Igor Rivin
    Mar 9, 2012 at 0:13
  • $\begingroup$ @Igor : Could you please tell me if there is an efficient algorithm for minimizing $L^1$ ? (Considering the fact that i need to look for only integer values ) $\endgroup$
    – Deepu
    Mar 9, 2012 at 5:46
  • $\begingroup$ @Deepu: there is a huge literature, see, for example, dsp.ucsd.edu/~dwipf/paper819.pdf (or the literature on compressed sensing...) $\endgroup$
    – Igor Rivin
    Mar 9, 2012 at 13:11
0
$\begingroup$

Here is one paper that deals with minimizing $L_0$ by creating an equivalent matrix of zeros and ones. Not sure how applicable it would be to your case.

"Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation" http://arxiv.org/pdf/1109.0882.pdf

Section III is where they turn their $L_0$ problem into an equivalent $L_1$ minimization.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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