How to do L1 regularization with constraint?

Question

In $L_1$ regularization we minimize the function $||Ax-b||_2+||x||_1$. In this function $A$ is a matrix, $b$ is a vector and $x$ is the vector variable we want to find by minimizing the function. This is useful in many application. I want my variable $x$ to be either $0$ or $1$.This constraint is not convex and I cannot do exhaustive search for $x$ if $b$ is long or higher dimension. Can anyone suggest how to solve this problem?

Answer 1

First, $||x||_1$ is simply $\sum x_i$ when $x$ is binary.

$||Ax-b||_2^2 + \sum x_i$ is a quadratic function, so you simply have a binary quadratic program, which typically is solved using branch-and-bound variants (which is brute force enumeration in the worst-case, as the problem is theoretically intractable and has exponential complexity)