# Regularized Least Squares by Laplacian Operator - Optimal Value of the Regularization Factor (Lagrangian Multiplier)

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

• 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.
– Peter K.
Feb 25 '15 at 12:50
• 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? Feb 26 '15 at 2:50
– Royi
May 2 at 20:38

Let me rewrite the problem:

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

In order ot 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).