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

Question

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?

Answer 1

The claim in the paper is false.

Since the problem is not convex, the claim does not follow from general results. However, there are some results in this direction in quite general cases:

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$.