1
$\begingroup$

Assume a graph $G=(V,E)$ where the vertices $V$ are points in ${{R}^{D}}$ with $\left| V \right|=n$. The edges $E$ are represented by a $n\times n$ affinity matrix $W$. Consider the graph Laplacian $L=D-W$ where $D$ is the diagonal degree matrix (${{D}_{ii}}=\underset{j}{\mathop \sum }\,{{W}_{ij}}$).

Assume I want to minimize the objective function $J$ defined as $J\left( f \right)={{f}^{T}}Lf+{{\left( f-y \right)}^{T}}\text{ }\!\!\Lambda\!\!\text{ }(f-y)$ where $y\in {{R}^{D}}$ and $\text{ }\!\!\Lambda\!\!\text{ }$ is some arbitrary diagonal matrix. The solution ${{f}^{*}}$ that minimizes $J$ is said to be solved by the following system of linear equations $\left( L+\text{ }\!\!\Lambda\!\!\text{ } \right)f=\text{ }\!\!\Lambda\!\!\text{ }y$. However I cannot see why solving this system of linear equations gives me the minimizing solution. Can anyone help me out?

$\endgroup$

1 Answer 1

2
$\begingroup$

I don't know if you were still looking for an answer here, but you can show that your function $J(f)$ has a solution $f^*$ that minimizes $J$ from solving the subsequent system of linear equations.

As in almost any closed-form optimization problem, you find the minimum of an objective function by taking its derivative. In this case,

$$ \frac{dJ}{df} = Lf + (f - y)\Lambda $$

Set $\frac{dJ}{df} = 0$, rearrange, and you get

$$ (L + \Lambda)f = \Lambda y $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .