# sparse data fitting problem

I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?)

Given a sparse data fitting problem:

$minimize \quad \| Ax-b \|^{2}_{2}$

$s.t. \qquad \|x\|_{0} \le K,$

$x \in R^{n}$

Suppose we are given a constant $M > 0$ such that $\|x^{*}\|_{\infty} \le M$ for some optimal solution $x^{*}$ to this problem. How can we paraphrase this problem with only linear and binary constraints?

Thanks for any help.

Introduce zero one binary variables $y_i, i=1,..,n$
Replace the constraint $\qquad \|x\|_{0} \le K,$ with the following constraints:
$$\Sigma_{i=1}^n y_i \le K$$ $$-x_i \le My_i, i=1,..,n$$ $$x_i \le My_i, i=1,..,n$$
As can be seen, when $y_i = 0$, then $x_i$ must equal $0$. When $y_i = 1$, $|x_i|$ is constrained to be $\le M$, and $y_i$won't sub-optimally "waste" being $1$ when $x_i = 0$.