2
$\begingroup$

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^*$?
$\endgroup$

1 Answer 1

1
$\begingroup$

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

[2] https://github.com/ryantibs/best-subset

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.