Binary solution to least squares linear regression

Question

I am looking for a closed form solution $x^*$, binary vector, to

$$\arg\min_{x}(\|M x + b\|_2),$$

restricted to $x \in \{ 0,1 \}^n$. Here $b \in \mathbb{R}^{m}, M \in \mathbb{R}^{m \times n}$ are known.

This is a simpler instance of the problem I am really interested in, but I am already struggling. Does a closed form solution even exist?

Answer 1

You are solving a least squares problem (see https://en.wikipedia.org/wiki/Least_squares), with the additional constraint that $x$ should be binary.

This additional constraint makes the problem very hard to solve. The formal term for that is NP-hard, see

Tsakonas, E., Jaldén, J., & Ottersten, B. (2011, May). Robust binary least squares: Relaxations and algorithms. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 3780-3783). IEEE.

In particular, a closed form does not exist.