Minimize Energy using Gauss-Seidel method with successive over- relaxation.

Question

I have an energy function to minimize

$$E = \sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 + \lambda\sum_{i,j}\|\mathbf N_i - \mathbf N_j\|^2$$

where $I$ is a known scalar, $N$ is an unknown $n\times3$ vector, $L$ is a known $3\times 1$ vector and $\lambda$ is some scalar. To figure out the optimum value of $N$ iteratively , I am trying to convert the following into a form of $\mathbf A\mathbf x = \mathbf b$, but have not been successful yet.Can some one help me with it.

Answer 1

Lets get this done.

First, to simplify the probem, let me introduce the following vector notations. I will assume that we have to find $n$ vectors $\mathbf N_i, i = 1,\dots, n.$ We stack all the $\mathbf N_i$'s together in one single vector $\mathbf N$. Moreover, we introduce $\mathbf L^\star $ which is the vector $2 I_i \mathbf L $ stacked multiple times together. We introduce the matrix $\mathbf M$ which is a blockdiagonal matrix which has the matrix $\mathbf L \mathbf L^T$ on its main diagonal. Then, we can rewrite

• $\sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 = \sum (I_i^2 -2 I_i \mathbf N_i^T\mathbf L + (\mathbf N_i^T\mathbf L)^2) = \sum_i I_i^2 - \mathbf N^T \mathbf L^\star + \mathbf N^T \mathbf M \mathbf N $

To simplify the second part of your function, we exploit that $ \sum_{i,j} \|\mathbf N_i - \mathbf N_j\|^2 = 2n \sum_i \|\mathbf N_i\|^2 - 2 \sum_{i,j} \mathbf N_i^T \mathbf N_j = 2n \| \mathbf{ N }\|^2 - 2 \sum_{i,j} \mathbf N_i^T \mathbf N_j $. Note that $2n \| \mathbf{ N }\|^2 = 2n \mathbf N^T \mathbf I_{3n} \mathbf N$, where $\mathbf I_{3n}$ is the identity matrix. Using $ \mathbf P = - \mathbf 1 \otimes \mathbf I_{3}$, where $\mathbf 1$ is the $n \times n$ matrix with 1's as its entries and $\otimes$ as the Kronecker product we have $- 2 \sum_{i,j} \mathbf N_i^T \mathbf N_j = 2\mathbf N^T \mathbf P \mathbf N$. (Actually $ \mathbf P$ is band matrix with 1's at every 3rd diagonal and zeros elsewhere). Then, we have

• $ \sum_{i,j} \|\mathbf N_i - \mathbf N_j\|^2 = 2 \mathbf N^T (n \mathbf I_{3n}+\mathbf P) \mathbf N$.

Let us define $\mathbf{A} = 2n \lambda \mathbf I_{3n}+2 \lambda \mathbf P + \mathbf M $ we finally have the following quadratic form

$$ E = \sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 + \lambda\sum_{i,j}\|\mathbf N_i - \mathbf N_j\|^2 = \mathbf{N}^T\mathbf{A} \mathbf{N}-\mathbf N^T \mathbf L^\star + \lambda \sum_i I_i^2$$ This quadratic form is minimized by $$ \mathbf{N} = 2\mathbf{A}^{-1} \mathbf L^\star, $$

see for example Unconstrained quadratic programming problem with positive semidefinite matrix.