# sparse data fitting problem [closed]

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.

## closed as off-topic by j.c., Jan-Christoph Schlage-Puchta, Ben McKay, Pace Nielsen, Piotr HajlaszSep 27 at 21:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question does not appear to be about research level mathematics within the scope defined in the help center." – j.c., Piotr Hajlasz
If this question can be reworded to fit the rules in the help center, please edit the question.

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$.