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, 2015 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, 2015 at 2:50
• @PavanManojJ, Could you please review my answer? If something missing let me know. Else, could you please mark it?
– Royi
Nov 2, 2022 at 12:58

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