Can $| left( X'X + lambda I right) ^{-1} X'y | = t$ be solved for $lambda$?












1












$begingroup$


In this post I suggested that the expression



$$
| left( X'X + lambda I right) ^{-1} X'y | = t
$$



couldn't be easily solved for $lambda$, because you need to "invert" the norm. But in general my knowledge of advanced arithmetic tricks is poor.



Can this expression be solved for $lambda$? If so, how would you do it?










share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    In this post I suggested that the expression



    $$
    | left( X'X + lambda I right) ^{-1} X'y | = t
    $$



    couldn't be easily solved for $lambda$, because you need to "invert" the norm. But in general my knowledge of advanced arithmetic tricks is poor.



    Can this expression be solved for $lambda$? If so, how would you do it?










    share|cite|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      In this post I suggested that the expression



      $$
      | left( X'X + lambda I right) ^{-1} X'y | = t
      $$



      couldn't be easily solved for $lambda$, because you need to "invert" the norm. But in general my knowledge of advanced arithmetic tricks is poor.



      Can this expression be solved for $lambda$? If so, how would you do it?










      share|cite|improve this question









      $endgroup$




      In this post I suggested that the expression



      $$
      | left( X'X + lambda I right) ^{-1} X'y | = t
      $$



      couldn't be easily solved for $lambda$, because you need to "invert" the norm. But in general my knowledge of advanced arithmetic tricks is poor.



      Can this expression be solved for $lambda$? If so, how would you do it?







      linear-algebra matrices vectors norm






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Jan 16 at 20:02









      shadowtalkershadowtalker

      16811




      16811






















          2 Answers
          2






          active

          oldest

          votes


















          1












          $begingroup$

          You can start by writing a singular value decomposition (SVD) for matrix $X$. For any matrix $X$ (not necessarily square), the SVD is
          $$ X = U S V', $$
          where $U$, $V$ are orthogonal matrices, and $S$ is a diagonal matrix with entries $sigma_i geq 0$. (Quick test: in Matlab, SVD is computed in a couple of seconds for $X$ a random matrix of size $2000 times 3000$. Don't know how huge your actual problem is.)



          Then, plugging the SVD in your formula, you get
          $$
          | left( X'X + lambda I right) ^{-1} X'y |^2 = ... = y' U D_lambda D_lambda U' y = z_lambda' z_lambda = | z_lambda |^2,
          $$

          where $D_lambda$ is a diagonal matrix with entries
          $$ d_i = frac{sigma_i}{(sigma_i^2 + lambda)}, $$
          and $z_lambda = D_lambda U' y$. It can be seen that $ | z_lambda |^2 $ gets its largest value when $lambda = 0$:
          $$ | z_0 |^2 = sum_{i=1}^r frac{(u_i' y)^2}{sigma_i^2},$$
          where $u_i$ is the $i$th column of $U$, and $i = 1, ..., r$ denotes the sum over all $sigma_i > 0$ (i.e., positive singular values). This value can be computed explicitly, if you can compute the SVD. Then it can be seen that if $t^2 > | z_0 |^2$, your equation surely has no solution for any $lambda > 0$.



          How to solve $lambda$ in the original equation? Again, if you can compute the SVD, you have the equation for $lambda$
          $$ f(lambda) = | z_lambda |^2 = sum_{i=1}^r frac{sigma_i^2 (u_i' y)^2}{(sigma_i^2 + lambda)^2} = t^2,$$
          where $sigma_i$ and $u_i' y$ can be "precomputed", as they do not depend on $lambda$. (Expanding by $Pi_i (sigma_i^2 + lambda)^2$ gives a large polynomial, so you are not going to get an exact solution). Using the above equation, $f'(lambda)$ is computable and you can use e.g. Newton's method to solve $f(lambda) = t^2$. Assuming that the above calculation is correct, you should get the same method as in the other answer...






          share|cite|improve this answer











          $endgroup$





















            2












            $begingroup$

            In principle, the left side of the equation $y' X (X'X + lambda I)^{-2} X' y = t^2$ is a rational function of $lambda$. However, if your matrices are large you won't want to evaluate this explicitly. I would suggest using Newton's method. Note that
            $$ dfrac{d}{dlambda} (X'X + lambda I)^{-2} = - 2 (X'X + lambda I)^{-3}$$
            so the iteration is
            $$lambda_{n+1} = lambda_n - frac{|(X'X + lambda_n I)^{-1} X' y|^2 - t^2}{-2 y' X (X' X + lambda_n I)^{-3} X' y} $$
            Of course, you needn't compute any inverse matrices, rather $(X' X + lambda_n I)^{-1} X' y$ is a solution of $(X' X + lambda_n I) x = X' y$ etc.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
              $endgroup$
              – shadowtalker
              Jan 17 at 23:52












            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%2f3076222%2fcan-left-xx-lambda-i-right-1-xy-t-be-solved-for-lambda%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$

            You can start by writing a singular value decomposition (SVD) for matrix $X$. For any matrix $X$ (not necessarily square), the SVD is
            $$ X = U S V', $$
            where $U$, $V$ are orthogonal matrices, and $S$ is a diagonal matrix with entries $sigma_i geq 0$. (Quick test: in Matlab, SVD is computed in a couple of seconds for $X$ a random matrix of size $2000 times 3000$. Don't know how huge your actual problem is.)



            Then, plugging the SVD in your formula, you get
            $$
            | left( X'X + lambda I right) ^{-1} X'y |^2 = ... = y' U D_lambda D_lambda U' y = z_lambda' z_lambda = | z_lambda |^2,
            $$

            where $D_lambda$ is a diagonal matrix with entries
            $$ d_i = frac{sigma_i}{(sigma_i^2 + lambda)}, $$
            and $z_lambda = D_lambda U' y$. It can be seen that $ | z_lambda |^2 $ gets its largest value when $lambda = 0$:
            $$ | z_0 |^2 = sum_{i=1}^r frac{(u_i' y)^2}{sigma_i^2},$$
            where $u_i$ is the $i$th column of $U$, and $i = 1, ..., r$ denotes the sum over all $sigma_i > 0$ (i.e., positive singular values). This value can be computed explicitly, if you can compute the SVD. Then it can be seen that if $t^2 > | z_0 |^2$, your equation surely has no solution for any $lambda > 0$.



            How to solve $lambda$ in the original equation? Again, if you can compute the SVD, you have the equation for $lambda$
            $$ f(lambda) = | z_lambda |^2 = sum_{i=1}^r frac{sigma_i^2 (u_i' y)^2}{(sigma_i^2 + lambda)^2} = t^2,$$
            where $sigma_i$ and $u_i' y$ can be "precomputed", as they do not depend on $lambda$. (Expanding by $Pi_i (sigma_i^2 + lambda)^2$ gives a large polynomial, so you are not going to get an exact solution). Using the above equation, $f'(lambda)$ is computable and you can use e.g. Newton's method to solve $f(lambda) = t^2$. Assuming that the above calculation is correct, you should get the same method as in the other answer...






            share|cite|improve this answer











            $endgroup$


















              1












              $begingroup$

              You can start by writing a singular value decomposition (SVD) for matrix $X$. For any matrix $X$ (not necessarily square), the SVD is
              $$ X = U S V', $$
              where $U$, $V$ are orthogonal matrices, and $S$ is a diagonal matrix with entries $sigma_i geq 0$. (Quick test: in Matlab, SVD is computed in a couple of seconds for $X$ a random matrix of size $2000 times 3000$. Don't know how huge your actual problem is.)



              Then, plugging the SVD in your formula, you get
              $$
              | left( X'X + lambda I right) ^{-1} X'y |^2 = ... = y' U D_lambda D_lambda U' y = z_lambda' z_lambda = | z_lambda |^2,
              $$

              where $D_lambda$ is a diagonal matrix with entries
              $$ d_i = frac{sigma_i}{(sigma_i^2 + lambda)}, $$
              and $z_lambda = D_lambda U' y$. It can be seen that $ | z_lambda |^2 $ gets its largest value when $lambda = 0$:
              $$ | z_0 |^2 = sum_{i=1}^r frac{(u_i' y)^2}{sigma_i^2},$$
              where $u_i$ is the $i$th column of $U$, and $i = 1, ..., r$ denotes the sum over all $sigma_i > 0$ (i.e., positive singular values). This value can be computed explicitly, if you can compute the SVD. Then it can be seen that if $t^2 > | z_0 |^2$, your equation surely has no solution for any $lambda > 0$.



              How to solve $lambda$ in the original equation? Again, if you can compute the SVD, you have the equation for $lambda$
              $$ f(lambda) = | z_lambda |^2 = sum_{i=1}^r frac{sigma_i^2 (u_i' y)^2}{(sigma_i^2 + lambda)^2} = t^2,$$
              where $sigma_i$ and $u_i' y$ can be "precomputed", as they do not depend on $lambda$. (Expanding by $Pi_i (sigma_i^2 + lambda)^2$ gives a large polynomial, so you are not going to get an exact solution). Using the above equation, $f'(lambda)$ is computable and you can use e.g. Newton's method to solve $f(lambda) = t^2$. Assuming that the above calculation is correct, you should get the same method as in the other answer...






              share|cite|improve this answer











              $endgroup$
















                1












                1








                1





                $begingroup$

                You can start by writing a singular value decomposition (SVD) for matrix $X$. For any matrix $X$ (not necessarily square), the SVD is
                $$ X = U S V', $$
                where $U$, $V$ are orthogonal matrices, and $S$ is a diagonal matrix with entries $sigma_i geq 0$. (Quick test: in Matlab, SVD is computed in a couple of seconds for $X$ a random matrix of size $2000 times 3000$. Don't know how huge your actual problem is.)



                Then, plugging the SVD in your formula, you get
                $$
                | left( X'X + lambda I right) ^{-1} X'y |^2 = ... = y' U D_lambda D_lambda U' y = z_lambda' z_lambda = | z_lambda |^2,
                $$

                where $D_lambda$ is a diagonal matrix with entries
                $$ d_i = frac{sigma_i}{(sigma_i^2 + lambda)}, $$
                and $z_lambda = D_lambda U' y$. It can be seen that $ | z_lambda |^2 $ gets its largest value when $lambda = 0$:
                $$ | z_0 |^2 = sum_{i=1}^r frac{(u_i' y)^2}{sigma_i^2},$$
                where $u_i$ is the $i$th column of $U$, and $i = 1, ..., r$ denotes the sum over all $sigma_i > 0$ (i.e., positive singular values). This value can be computed explicitly, if you can compute the SVD. Then it can be seen that if $t^2 > | z_0 |^2$, your equation surely has no solution for any $lambda > 0$.



                How to solve $lambda$ in the original equation? Again, if you can compute the SVD, you have the equation for $lambda$
                $$ f(lambda) = | z_lambda |^2 = sum_{i=1}^r frac{sigma_i^2 (u_i' y)^2}{(sigma_i^2 + lambda)^2} = t^2,$$
                where $sigma_i$ and $u_i' y$ can be "precomputed", as they do not depend on $lambda$. (Expanding by $Pi_i (sigma_i^2 + lambda)^2$ gives a large polynomial, so you are not going to get an exact solution). Using the above equation, $f'(lambda)$ is computable and you can use e.g. Newton's method to solve $f(lambda) = t^2$. Assuming that the above calculation is correct, you should get the same method as in the other answer...






                share|cite|improve this answer











                $endgroup$



                You can start by writing a singular value decomposition (SVD) for matrix $X$. For any matrix $X$ (not necessarily square), the SVD is
                $$ X = U S V', $$
                where $U$, $V$ are orthogonal matrices, and $S$ is a diagonal matrix with entries $sigma_i geq 0$. (Quick test: in Matlab, SVD is computed in a couple of seconds for $X$ a random matrix of size $2000 times 3000$. Don't know how huge your actual problem is.)



                Then, plugging the SVD in your formula, you get
                $$
                | left( X'X + lambda I right) ^{-1} X'y |^2 = ... = y' U D_lambda D_lambda U' y = z_lambda' z_lambda = | z_lambda |^2,
                $$

                where $D_lambda$ is a diagonal matrix with entries
                $$ d_i = frac{sigma_i}{(sigma_i^2 + lambda)}, $$
                and $z_lambda = D_lambda U' y$. It can be seen that $ | z_lambda |^2 $ gets its largest value when $lambda = 0$:
                $$ | z_0 |^2 = sum_{i=1}^r frac{(u_i' y)^2}{sigma_i^2},$$
                where $u_i$ is the $i$th column of $U$, and $i = 1, ..., r$ denotes the sum over all $sigma_i > 0$ (i.e., positive singular values). This value can be computed explicitly, if you can compute the SVD. Then it can be seen that if $t^2 > | z_0 |^2$, your equation surely has no solution for any $lambda > 0$.



                How to solve $lambda$ in the original equation? Again, if you can compute the SVD, you have the equation for $lambda$
                $$ f(lambda) = | z_lambda |^2 = sum_{i=1}^r frac{sigma_i^2 (u_i' y)^2}{(sigma_i^2 + lambda)^2} = t^2,$$
                where $sigma_i$ and $u_i' y$ can be "precomputed", as they do not depend on $lambda$. (Expanding by $Pi_i (sigma_i^2 + lambda)^2$ gives a large polynomial, so you are not going to get an exact solution). Using the above equation, $f'(lambda)$ is computable and you can use e.g. Newton's method to solve $f(lambda) = t^2$. Assuming that the above calculation is correct, you should get the same method as in the other answer...







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Jan 17 at 22:21

























                answered Jan 17 at 21:18









                user635750user635750

                363




                363























                    2












                    $begingroup$

                    In principle, the left side of the equation $y' X (X'X + lambda I)^{-2} X' y = t^2$ is a rational function of $lambda$. However, if your matrices are large you won't want to evaluate this explicitly. I would suggest using Newton's method. Note that
                    $$ dfrac{d}{dlambda} (X'X + lambda I)^{-2} = - 2 (X'X + lambda I)^{-3}$$
                    so the iteration is
                    $$lambda_{n+1} = lambda_n - frac{|(X'X + lambda_n I)^{-1} X' y|^2 - t^2}{-2 y' X (X' X + lambda_n I)^{-3} X' y} $$
                    Of course, you needn't compute any inverse matrices, rather $(X' X + lambda_n I)^{-1} X' y$ is a solution of $(X' X + lambda_n I) x = X' y$ etc.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                      $endgroup$
                      – shadowtalker
                      Jan 17 at 23:52
















                    2












                    $begingroup$

                    In principle, the left side of the equation $y' X (X'X + lambda I)^{-2} X' y = t^2$ is a rational function of $lambda$. However, if your matrices are large you won't want to evaluate this explicitly. I would suggest using Newton's method. Note that
                    $$ dfrac{d}{dlambda} (X'X + lambda I)^{-2} = - 2 (X'X + lambda I)^{-3}$$
                    so the iteration is
                    $$lambda_{n+1} = lambda_n - frac{|(X'X + lambda_n I)^{-1} X' y|^2 - t^2}{-2 y' X (X' X + lambda_n I)^{-3} X' y} $$
                    Of course, you needn't compute any inverse matrices, rather $(X' X + lambda_n I)^{-1} X' y$ is a solution of $(X' X + lambda_n I) x = X' y$ etc.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                      $endgroup$
                      – shadowtalker
                      Jan 17 at 23:52














                    2












                    2








                    2





                    $begingroup$

                    In principle, the left side of the equation $y' X (X'X + lambda I)^{-2} X' y = t^2$ is a rational function of $lambda$. However, if your matrices are large you won't want to evaluate this explicitly. I would suggest using Newton's method. Note that
                    $$ dfrac{d}{dlambda} (X'X + lambda I)^{-2} = - 2 (X'X + lambda I)^{-3}$$
                    so the iteration is
                    $$lambda_{n+1} = lambda_n - frac{|(X'X + lambda_n I)^{-1} X' y|^2 - t^2}{-2 y' X (X' X + lambda_n I)^{-3} X' y} $$
                    Of course, you needn't compute any inverse matrices, rather $(X' X + lambda_n I)^{-1} X' y$ is a solution of $(X' X + lambda_n I) x = X' y$ etc.






                    share|cite|improve this answer









                    $endgroup$



                    In principle, the left side of the equation $y' X (X'X + lambda I)^{-2} X' y = t^2$ is a rational function of $lambda$. However, if your matrices are large you won't want to evaluate this explicitly. I would suggest using Newton's method. Note that
                    $$ dfrac{d}{dlambda} (X'X + lambda I)^{-2} = - 2 (X'X + lambda I)^{-3}$$
                    so the iteration is
                    $$lambda_{n+1} = lambda_n - frac{|(X'X + lambda_n I)^{-1} X' y|^2 - t^2}{-2 y' X (X' X + lambda_n I)^{-3} X' y} $$
                    Of course, you needn't compute any inverse matrices, rather $(X' X + lambda_n I)^{-1} X' y$ is a solution of $(X' X + lambda_n I) x = X' y$ etc.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Jan 16 at 20:28









                    Robert IsraelRobert Israel

                    331k23221477




                    331k23221477












                    • $begingroup$
                      I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                      $endgroup$
                      – shadowtalker
                      Jan 17 at 23:52


















                    • $begingroup$
                      I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                      $endgroup$
                      – shadowtalker
                      Jan 17 at 23:52
















                    $begingroup$
                    I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                    $endgroup$
                    – shadowtalker
                    Jan 17 at 23:52




                    $begingroup$
                    I'm switching my acceptance to the other answer just because the expression is simpler and easier to wrap my head around (and to describe to other people)
                    $endgroup$
                    – shadowtalker
                    Jan 17 at 23:52


















                    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%2f3076222%2fcan-left-xx-lambda-i-right-1-xy-t-be-solved-for-lambda%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

                    Human spaceflight

                    Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

                    張江高科駅