In the paper [*Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries* (page 2)](https://www.egr.msu.edu/~aviyente/elad06.pdf), 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?



Adding constraints as penalty with $\| \cdot \|_0$ norm
**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](http://iopscience.iop.org/article/10.1088/0266-5611/29/7/075016/meta), 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$.


