Minimize Energy using Gauss-Seidel method with successive over- relaxation.
$begingroup$
I have an energy function to minimize
$$E = sum_i |I_i - mathbf N_i^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2$$
where $I$ is a known scalar, $N$ is an unknown $ntimes3$ vector, $L$ is a known $3times 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 Amathbf x = mathbf b$, but have not been successful yet.Can some one help me with it.
linear-algebra optimization
$endgroup$
add a comment |
$begingroup$
I have an energy function to minimize
$$E = sum_i |I_i - mathbf N_i^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2$$
where $I$ is a known scalar, $N$ is an unknown $ntimes3$ vector, $L$ is a known $3times 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 Amathbf x = mathbf b$, but have not been successful yet.Can some one help me with it.
linear-algebra optimization
$endgroup$
add a comment |
$begingroup$
I have an energy function to minimize
$$E = sum_i |I_i - mathbf N_i^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2$$
where $I$ is a known scalar, $N$ is an unknown $ntimes3$ vector, $L$ is a known $3times 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 Amathbf x = mathbf b$, but have not been successful yet.Can some one help me with it.
linear-algebra optimization
$endgroup$
I have an energy function to minimize
$$E = sum_i |I_i - mathbf N_i^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2$$
where $I$ is a known scalar, $N$ is an unknown $ntimes3$ vector, $L$ is a known $3times 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 Amathbf x = mathbf b$, but have not been successful yet.Can some one help me with it.
linear-algebra optimization
linear-algebra optimization
edited Jun 13 '14 at 12:19
Michael Hardy
1
1
asked Jun 12 '14 at 15:57
noddynoddy
363311
363311
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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^Tmathbf L|^2 = sum (I_i^2 -2 I_i mathbf N_i^Tmathbf L + (mathbf N_i^Tmathbf 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 = 2mathbf 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^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2 = mathbf{N}^Tmathbf{A} mathbf{N}-mathbf N^T mathbf L^star + lambda sum_i I_i^2$$
This quadratic form is minimized by
$$ mathbf{N} = 2mathbf{A}^{-1} mathbf L^star, $$
see for example Unconstrained quadratic programming problem with positive semidefinite matrix.
$endgroup$
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f831900%2fminimize-energy-using-gauss-seidel-method-with-successive-over-relaxation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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^Tmathbf L|^2 = sum (I_i^2 -2 I_i mathbf N_i^Tmathbf L + (mathbf N_i^Tmathbf 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 = 2mathbf 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^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2 = mathbf{N}^Tmathbf{A} mathbf{N}-mathbf N^T mathbf L^star + lambda sum_i I_i^2$$
This quadratic form is minimized by
$$ mathbf{N} = 2mathbf{A}^{-1} mathbf L^star, $$
see for example Unconstrained quadratic programming problem with positive semidefinite matrix.
$endgroup$
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
add a comment |
$begingroup$
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^Tmathbf L|^2 = sum (I_i^2 -2 I_i mathbf N_i^Tmathbf L + (mathbf N_i^Tmathbf 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 = 2mathbf 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^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2 = mathbf{N}^Tmathbf{A} mathbf{N}-mathbf N^T mathbf L^star + lambda sum_i I_i^2$$
This quadratic form is minimized by
$$ mathbf{N} = 2mathbf{A}^{-1} mathbf L^star, $$
see for example Unconstrained quadratic programming problem with positive semidefinite matrix.
$endgroup$
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
add a comment |
$begingroup$
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^Tmathbf L|^2 = sum (I_i^2 -2 I_i mathbf N_i^Tmathbf L + (mathbf N_i^Tmathbf 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 = 2mathbf 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^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2 = mathbf{N}^Tmathbf{A} mathbf{N}-mathbf N^T mathbf L^star + lambda sum_i I_i^2$$
This quadratic form is minimized by
$$ mathbf{N} = 2mathbf{A}^{-1} mathbf L^star, $$
see for example Unconstrained quadratic programming problem with positive semidefinite matrix.
$endgroup$
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^Tmathbf L|^2 = sum (I_i^2 -2 I_i mathbf N_i^Tmathbf L + (mathbf N_i^Tmathbf 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 = 2mathbf 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^Tmathbf L|^2 + lambdasum_{i,j}|mathbf N_i - mathbf N_j|^2 = mathbf{N}^Tmathbf{A} mathbf{N}-mathbf N^T mathbf L^star + lambda sum_i I_i^2$$
This quadratic form is minimized by
$$ mathbf{N} = 2mathbf{A}^{-1} mathbf L^star, $$
see for example Unconstrained quadratic programming problem with positive semidefinite matrix.
edited Dec 12 '18 at 15:15
answered Jun 13 '14 at 11:50
The Pheromone KidThe Pheromone Kid
718410
718410
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
add a comment |
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Hi, I know this is an old question, but I'm wondering if you could elaborate on the final step, how did you get the final form? For reference, the question comes from this paper: dl.acm.org/citation.cfm?id=2024180 "Interactive Normal reconstruction from a single image". My best guess is that you differentiated the new form of E, with respect to N, which drops the sum of I, and you treat NT as a constant?
$endgroup$
– nitronoid
Dec 3 '18 at 16:58
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
$begingroup$
Dear nitronoid, see my answer in math.stackexchange.com/questions/1839030/…
$endgroup$
– The Pheromone Kid
Dec 12 '18 at 15:14
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f831900%2fminimize-energy-using-gauss-seidel-method-with-successive-over-relaxation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown