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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 8, 2012 at 23:04
  • $\begingroup$ @Noah, you are right, $L^1$ is th right thing... $\endgroup$
    – Igor Rivin
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .