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. 



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


