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












2












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










share|cite|improve this question











$endgroup$

















    2












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










    share|cite|improve this question











    $endgroup$















      2












      2








      2





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










      share|cite|improve this question











      $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






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jun 13 '14 at 12:19









      Michael Hardy

      1




      1










      asked Jun 12 '14 at 15:57









      noddynoddy

      363311




      363311






















          1 Answer
          1






          active

          oldest

          votes


















          1












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






          share|cite|improve this answer











          $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











          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
          });


          }
          });














          draft saved

          draft discarded


















          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









          1












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






          share|cite|improve this answer











          $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
















          1












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






          share|cite|improve this answer











          $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














          1












          1








          1





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






          share|cite|improve this answer











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







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          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


















          • $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


















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          Tonle Sap (See)

          I get strange results when I access the Sqlitedatabase with Unity C# via XAMPP

          Guatemaltekische Davis-Cup-Mannschaft