# Finding a vector in the subspace

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.

• Is $A$ a square matrix? If not, do you have some condition on the number of rows of $A$? Commented Mar 8, 2012 at 22:01
• What is the $L_0$ norm? The number of nonzero components? This is not standard notation. Commented Mar 8, 2012 at 22:28
• @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. Commented Mar 9, 2012 at 5:45

The problem is NP-hard, however minimizing $L^2$ or $L^1$ norm generally gives a good approximation.
• 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}$. Commented Mar 8, 2012 at 23:04
• @Noah, you are right, $L^1$ is th right thing... Commented Mar 9, 2012 at 0:13
• @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 ) Commented Mar 9, 2012 at 5:46
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.
Section III is where they turn their $L_0$ problem into an equivalent $L_1$ minimization.