1
$\begingroup$

Question

I need to prove that:

$$ \text{arg min}_{\mathbf{x}} \dfrac{1}{2\sigma} \| \mathbf{x} - \mathbf{z} \|^2 + \lambda \| W \mathbf{x} \|_1 = W^{-1} \text{arg min}_{\mathbf{w}} \dfrac{1}{2\sigma} \| \mathbf{w} - W \mathbf{z} \|^2 + \lambda \| \mathbf{w} \|_1 $$

where $W$ is an orthogonal wavelet transform and $W \mathbf{x} = \mathbf{w}$.

Proof

My idea proceeds as follows: because $W$ is orthogonal, it is norm-preserving, so $\lambda \| W \mathbf{x} \|_1 = \lambda \| \mathbf{w} \|_1$. In addition, because $W$ is orthogonal, its inverse is equal to its transpose: $W^{-1} = W^T$. Therefore, $W^{-1}W = I$.

As a result, we have:

$$ \begin{align*} \text{arg min}_{\mathbf{x}} \dfrac{1}{2\sigma} \| \mathbf{x} - \mathbf{z} \|^2 &= \text{arg min}_{\mathbf{x}} \dfrac{1}{2\sigma} \| W^{-1} W \mathbf{x} - W^{-1} W \mathbf{z} \|^2\\ &= \text{arg min}_{\mathbf{w}} \dfrac{1}{2\sigma} \| W^{-1} \mathbf{w} - W^{-1} W \mathbf{z} \|^2\\ &= \text{arg min}_{\mathbf{w}} \dfrac{1}{2\sigma} \| W^{-1} \left( \mathbf{w} - W \mathbf{z} \right) \|^2\\ \end{align*} $$

But I am stuck on the last step on how to get the $W^{-1}$ out of the norm expression and show that

$$ \text{arg min}_{\mathbf{w}} \dfrac{1}{2\sigma} \| W^{-1} \left( \mathbf{w} - W \mathbf{z} \right) \|^2 = W^{-1} \text{arg min}_{\mathbf{w}} \dfrac{1}{2\sigma} \| \mathbf{w} - W \mathbf{z} \|^2 $$

Is there some rule about (orthogonal) matrices and norms that I can use here?

$\endgroup$
2
+100
$\begingroup$

$\| Wx \|_1 = \|w\|_1$ is true not because $W$ is norm-preserving, but because $Wx = w$ by definition. $W$ only preserves the $\| \cdot \|_2$-norm, not the $\| \cdot \|_1$-norm.

Other than this, the only error in your calculation is that you convert from argmin over $x$ to argmin over $w$. Remember that argmin outputs the minimizing input of the expression, not the minimum itself, so it doesn't make sense to do variable substitution directly. So starting from the first line, the calculation should be:

\begin{align} \arg \min_x \| W^{-1} Wx - z \|_2^2 & = \arg \min_x \| Wx - Wz \|_2^2 \\ & = \arg \min_{x: \, w = Wx} \| w - Wz \|_2^2 \\ & = W^{-1} \arg \min_w \| w - Wz \|_2^2 \\ \end{align}

In the last line, we introduce $W^{-1}$ because the original argmin gives us a value of $x$. The new argmin gives us a value of $w$, and since $Wx = w$, we apply the inverse map to get back to the same domain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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