# $\ell_0$ penalised and $K$ sparse problems

Consider the $\ell_0$ penalized problem: $$\min_{x\in \mathbb{R}^n} \frac{1}{2}\|Ax-b\|_2^2+\lambda\|x\|_0 \qquad \qquad \qquad \qquad \qquad \qquad (1)$$ and $K$-sparse problem $$\min\frac{1}{2}\|Ax-b\|_2^2 \qquad \mbox{ s.t. } \qquad \|x\|_0\leq K \qquad \qquad \qquad (2)$$ 1. Since $\ell_0$ is a discontinuous function or the set $\{x:\; \|x\|_0\leq K\}$ is not bounded, does (1) or (2) always admit a solution?

1. What is the relationship between solution sets of the two problems depending on $\lambda$, i.e., is there any $\lambda$ such that these solution set sare equal? Assume that we have found a solution $x^*$ of (1), can we find a solution of (2) from $x^*$?

1) Yes. Both forms always admit a solution, but it's not necessarily unique.

The constrained form (your second formulation) is a bit easier to analyze.

As you note, the constraint set $\mathcal{C} = \{x : \|x\|_0 \leq K\}$ is not bounded, so it's not entirely obvious that there will be a minimum. (More precisely, it's not compact so we don't get the usual "easy" guarantees that a minimum exists and is obtained.)

However, in this case, we can guarantee that a solution exists just by considering the problem directly. The 'trick' is in the structure of the constraint set. Note that it can be written as the union of simpler sets - for example, if $K = 4$, then

\begin{aligned}\{x: \|x\|_0 \leq K\} =&\phantom{\cup+}\{x: (x_1, x_2, x_3, x_4) \in \mathbb{R}, (x_5, \dots, x_n) = 0 \} \\ &\cup \{x: (x_1, x_2, x_3, x_5) \in \mathbb{R}, (x_4, x_6, \dots, x_n) = 0 \} \\ &\cup \{x: (x_1, x_2, x_3, x_6) \in \mathbb{R}, (x_4, x_5, x_7, \dots, x_n) = 0 \} \\ &\cup \dots\ \\ =&\bigcup_{S \text{ is a set of 4 integers\leq N}} \underbrace{\{x: x_i = 0 \quad \forall i \notin S\}}_{\mathcal{C}_S}\end{aligned}

This is a union over a finite set of convex sets, so we can solve the original problem by simply solving $\min_{x \in \mathcal{C}_i} \|Ax - b\|_2^2$ and then taking the minimum over all the solutions and using that as our global solution.

In symbols:

\begin{aligned} \min_{x \in \mathcal{C}} \|Ax-b\|_2^2 = \min_{S \in \mathcal{S}} \min_{x \in S} \|Ax-b\|_2^2\end{aligned} where $\mathcal{S}$ is the set of (distinct) $K$-tuples.

A bit less formally, we can always solve the $K$-sparse problem, by finding the best possible solution for every sets of at most $K$ columns of $A$ and then just taking the 'best of the best' as our global solution.

This 'brute force' approach is slow when $K$ is bigger than 2 or 3 (since we have to solve $\sum_{i=0}^K \binom{n}{i}$ OLS problems), but if you're clever and have a big computer and some time to burn, it's doable up to $n \approx 1000$. [1] gives the gory details and [2] provides an R package implementing the approach in [1].

If $K$ is large or if there is redundancy among columns of $A$ (the formal condition is $\text{rank}(A) < K$), two of these sub-problems may give the same value, so you aren't guaranteed a unique $\text{arg min}$ solution, but you always have a unique $\text{min}$ because it's just the minimum over a finite set.

2) No. They aren't quite equivalent, but it is true that if you have a solution to (1) for a given $\lambda$, you can pick a $K$ such that it is a solution to (2). You can't always find $K$ such that a solution to (1) that matches a given solution to (2) however. This phenomenon is noted in Section 1.3 of [3], but it's not discussed at length.

[1] D. Bertsimas, A. King, R. Mazumder. "Best subset selection via a modern optimization lens." Annals of Statistics 44(2), p.813-852, 2016. https://projecteuclid.org/euclid.aos/1458245736

[3] R.J. Tibshirani. "Degrees of Freedom and Model Search." Statistica Sinica 25, p.1265-1296, 2015.