Adding constraints as penalty with $\| \cdot \|_0$ norm

In the paper Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries (page 2), the authors rewrite the minimization problem

\begin{align} \min_{\alpha \in \mathbb R^k} \| \alpha \|_0 && s.t. && \|D \alpha - y \|_2^2 \leq T, \end{align}

where $$D \in \mathbb R^{n \times k}$$ and $$y \in \mathbb R^n$$, into

\begin{align} \min_{\alpha \in \mathbb R^k} \| D \alpha - y \|_2^2 + \mu \| \alpha \|_0 \end{align}

and state that

for a proper choice of $$\mu$$, the two problems are equivalent.

There is no reference in the paper that explains why this would be true and in fact, I don't believe it is true, since $$\| \cdot \|_0$$ is not even convex. Does such a $$\mu$$ really exist?

I don't know if this is important, but the following assumptions were made: $$y$$ is a noisy version of $$x$$ with zero mean white noise of variance $$\sigma^2$$, and that there exists $$x$$ so that $$\| D \alpha - x \|_2 \leq \epsilon$$ with $$\| \alpha \|_0 \leq L \ll n$$. The $$T$$ from the first equation above is dictated by $$\varepsilon$$ and $$\sigma$$.

I already asked two professors who also don't believe the statement is true. However, it has to come from somewhere. Does it maybe work with $$\| \cdot \|_1$$? Or is this just an "analytic application" of a penalty method?

• What does the zero norm do? Count the number of nonzero entries of a vector? – Tommi Oct 19 '18 at 7:55
• Yes, it counts the non-zeros, i.e. $\|x\|_0 = \#\{ x_i : x_i \neq 0\}$ – TheWaveLad Oct 19 '18 at 8:58

If $$x^*$$ is the unique minimizer of $$\min_x F(x) + G(x)$$, then it is a solution of the constrained problem $$\min_x F(x)\qquad\text{s.t.}\qquad G(x) \leq T$$ for $$T = G(x^*)$$. The converse direction (even with uniqueness) is false in general (I guess that this is folklore, but I typed up a result and counterexample in "Necessary conditions for variational regularization schemes, D Lorenz, N Worliczek, Inverse Problems 29 (7), 075016", Theorem 2.3 and Example 2.4).
In this special case you can consider the 2d problem $$\min_x \|x\|_0\qquad\text{s.t.}\qquad \| x - \begin{bmatrix}2\\2\end{bmatrix}\|_2^2\leq 1$$ which gives you the optimal value $$2$$ and the solutions are the whole feasible set. As far as I see, you can't realize this optimal set for $$\min_x \mu\|x\|_0 + \| x - \begin{bmatrix}2\\2\end{bmatrix}\|_2^2$$ for any $$\mu$$.