# Convex optimization with $\ell_0$ “norm”

I have an optimization problem of the form

\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&||x||_0 \le t,\end{align*}

where $t$ is a given constant and $f:\mathbb{R}^d \to \mathbb{R}$ is a convex, differential function and $x$ ranges over $\mathbb{R}^d$. Or, roughly equivalently, I'd like to solve

$$\text{minimize }\; f(x) + \lambda \cdot ||x||_0.$$

What techniques are available for this?

Techniques I've found in my reading so far:

• $L_1$ norm optimization: Replace the $L_0$ norm with a $L_1$ norm, and then solve the resulting problem. In other words, solve

$$\text{minimize }\; f(x) + \lambda \cdot ||x||_1.$$

Optionally, follow this with iterative re-weighting: given a candidate solution $\hat{x}$, solve

$$\text{minimize }\; f(x) + \lambda \sum_{i=1}^d \frac{1}{|\hat{x}_i|} |x_i|,$$

and then replace $\hat{x}$ with the resulting solution; iterate until convergence. Apparently, the $L_1$ norm encourages sparse solutions. (I guess this is the idea behind Lasso and compressed sensing?)

• Approximate the $L_0$ norm: Replace the $L_0$ norm with $L_{1/2}$ norm, or with $L_p$ norm for $p \in (0,1)$, or with a function $g(x)$ defined by an approximation such as

$$g(x) = \sum_{i=1}^d \log(1 + |x_i|/\alpha).$$

Also, two other techniques that I haven't seen described anywhere, but seem like natural algorithms:

• Forward greedy selection. Start by finding a one-element set $S_1$ that makes the following as small as possible:

\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&x_j = 0 \text{ for all } j \notin S_1;\end{align*}

Then find a two-element $S_2$ such that $S_1 \subset S_2$ and that makes the following as small as possible:

\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&x_j = 0 \text{ for all } j \notin S_2;\end{align*}

Iterate, adding one coefficient to the set at each stage. This minimization step can be solved efficiently by trying all possibilities for the one index you add to $S$ in each step.

• Backward greedy selection. Similar to above, but you start with $S_0=\{1,2,\dots,d\}$. In the $i$th iteration you look for $S_i$ such that $S_i \subset S_{i-1}$ and $|S_i|=|S_{i-1}|-1$ and that makes the following as small as possible:

\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&x_j = 0 \text{ for all } j \notin S_i;\end{align*}

Are there any other techniques worth knowing about? Are there any "dominance" relationships between these (e.g., method X usually beats method Y, so don't bother with method Y)?

I know that the L0 norm $||\cdot||_0$ isn't convex, and in fact, isn't even a norm. I know the optimization problem I'm trying to solve is NP-hard in the worst case, so we can't expect efficient solutions that always produce the optimal answer, but I'm interested in pragmatic heuristics that will often work well when $f(x)$ is nice (smooth, etc.).

• The $\ell_1$-norm approach is extremely popular and should work well. I'd guess it would give much better results than the greedy approaches. – littleO Jul 18 '16 at 3:42
• Do you know whether the problem you're "trying to solve is" W-hard "in the worst case"? ​ ​ – user57159 Jul 20 '16 at 22:28
• @RickyDemer, great question! No, I don't know; alas, I'm woefully ignorant of parametrized complexity. If you like, we can focus on the special case where $f$ is quadratic, i.e., $f(x) = x^\top A x + b^\top x$ where $A$ is positive semi-definite.Is this expressive enough to make it W-hard? Perhaps we can encode an instance of independent set in this way? I gather that if the answer is yes, then there exists no FPTAS nor EPTAS for the problem. Does it tend to suggest there's no PTAS, either? (That said, I'm more interested in heuristics that work well in practice than in complexity theory.) – D.W. Jul 20 '16 at 23:09
• The relevance to approximation would be when you're approximating $t$, not when you're given a $t$. ​ I think I can show that the opposite parameterization (by number of coordinates that must be zero, rather than number of coordinates that may be non-zero) is enough for the quadratic case to be strongly W-hard, by reduction from independent set as you suggested. ​ By composing with a diagonal translation, it suffices to show that for ​ ​ ​ (continued ...) ​ ​ ​ ​ ​ ​ ​ ​ – user57159 Jul 21 '16 at 0:26
• (... continued) ​ ​ ​ "number of coordinates that must be one", rather than "number of coordinates that must be zero". ​ Let A be [adjacency matrix plus [number_of_vertices times identity_matrix]], and let b be the zero vector. ​ I believe that and the [indicator operator and the indicator operator's inverse] is a strongly parsimonious reduction to the "number of coordinates that must be one" version; should I explain why? ​ However, that doesn't address the parameterization by $t$. ​ ​ ​ ​ ​ ​ ​ ​ – user57159 Jul 21 '16 at 0:27

You should have a look at a nice package called Smoothed ${L}_{0}$ (Smoothed L0 / Smoothed L Zero).
They approximate the ${L}_{0}$ "Pseudo Norm" (Which isn't convex) by a Gaussian Kernel.