Consider the cost function

$$f(X,\lambda) = \|AX-b\|_2^2 + \alpha \|LX\|_2^2$$

$A:$Measurement matrix($R_{m\times n}$,$m \ll n$), $b:$observation vector($R_m$), $L:$Laplacian operator($R_{n \times n}$), $X:$vector form of an image($R_n$)

(The above cost function can be read, non-mathematically as minimize

$AX=b+error$ subject to $LX=0$)

$$\frac{\partial f}{dX} = 0 \implies 2X^T(A^TA) - 2X^T(A^Tb)+\lambda(L^TL) = 0.........(1)$$

$$\frac{\partial f}{d\lambda} = 0 \implies \|LX\|_2^2=0.........(2)$$

From $(1)$ $X_s = (A^TA+\lambda L^TL)^{-1}A^Tb.........(3)$

$(3)$ in $(2) \implies \|LX_s\|^2_2 = 0..........(4)$

It is very clear from $(3),$ $\lambda$ plays a very crucial role in solving for $X$ because changing the value of $\lambda$ gives a different estimate for $X$.

using $(4),$ is it not possible to auto compute the optimal value of $\lambda$?

If it is possible to auto compute optimal $\lambda,$ why is it in many image de-noising problems we specify the optimal lambda $\lambda$ as an input to the algorithm?

It it is not possible to auto compute $\lambda,$ why is it so?

Thanks for reading my question with patience..

  • 1
    $\begingroup$ Most Lagrangian multiplier problems I've looked at do not allow a priori selection of $\lambda$. As you see from (3), the solution depends upon it. Also, shouldn't $\alpha$ in your first equation be $\lambda$? Otherwise (2) makes no sense. $\endgroup$
    – Peter K.
    Feb 25 '15 at 12:50
  • $\begingroup$ Thanks Peter... $\alpha$ in my first equation is $\lambda$, sorry for that. Can you please help me with few pointers where $\lambda$ is auto computed? $\endgroup$ Feb 26 '15 at 2:50
  • $\begingroup$ @PavanManojJ, Could you please mark my answer? $\endgroup$
    – Royi
    Nov 11 at 3:41

Let me rewrite the problem as following:

$$ \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| L x \right\|}_{2}^{2} $$

In order to say something intelligent about the optimal value of $ \lambda $ one must set an optimization criteria.
Since you don't have one there is no well defined answer.

What might assist you is reformulating the problem in an equivalent form:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| L x \right\|}_{2}^{2} \leq \alpha & \end{align*}$$

Both forms are equivalent in the sense that for any $ \alpha $ of the 2nd form there exists $ \lambda $ such that both solutions are the same.

Now if you can say something about the smoothness level of the image which will let you set $ \alpha $ intelligently than you'll be able to extract $ \lambda $ to match it.

Pay attention that the connection isn't trivial and depends on the data itself among other things (See my answer to Significance of λ in Basis Pursuit).


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.