I have the following optimization problem:
$$ \begin{aligned} & \text{min} && \mathop{\textrm{card}}(x_+)\\ & \text{s.t.} && Ax = b \end{aligned} $$
where $\mathop{\textrm{card}}(\cdot)$ is the $\ell_0$-norm (cardinality) and $x_+$ is element-wise positive ($x_+ = \max\{0, x\}$). $A \in \mathbb R^{m\times n}$ where $m < n$.
I know this is a cardinality optimization and in general it's hard to solve.
I searched for heuristics for solving cardinality optimization and found this lecture slides. From page 9 I see that we can apply $\ell_1$-norm heuristic to this kind of problem, but I don't understand how exactly should I do that for my specific problem.
Because $x_+$ is nonnegative, the $\ell_1$ approximation to cardinality just reduces to the straight elementwise sum. So you need: \begin{array}{ll} \text{minimize} & \sum_i \max\{x_i,0\} \\ \text{subject to} & A x = b \end{array} This is easily converted to a linear program by introducing a new variable $y\in\mathbb{R}^n$: \begin{array}{ll} \text{minimize} & \sum_i y_i \\ \text{subject to} & A x = b \\ & y \succeq x \\ & y \succeq 0 \end{array} Of course, this is a heuristic, so do not expect it to reliably produce the minimum cardinality solution without some sort of a priori knowledge about $A$ (e.g., the RIP property).