Invertibility of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$?
$begingroup$
I'm given a problem:
$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.
I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible
But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.
Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?
linear-algebra inverse
$endgroup$
add a comment |
$begingroup$
I'm given a problem:
$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.
I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible
But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.
Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?
linear-algebra inverse
$endgroup$
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59
add a comment |
$begingroup$
I'm given a problem:
$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.
I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible
But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.
Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?
linear-algebra inverse
$endgroup$
I'm given a problem:
$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.
I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible
But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.
Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?
linear-algebra inverse
linear-algebra inverse
edited Dec 6 '18 at 8:20
Tommi Brander
956922
956922
asked Dec 5 '18 at 21:24
W. MacTurkW. MacTurk
135
135
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59
add a comment |
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Write out $A$ in its SVD, $A=USigma V^T$. Then we have
$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.
$endgroup$
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
add a comment |
$begingroup$
You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).
[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]
Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?
$endgroup$
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
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%2f3027674%2finvertibility-of-textbfat-textbfa-epsilon-textbfi%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
$begingroup$
Write out $A$ in its SVD, $A=USigma V^T$. Then we have
$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.
$endgroup$
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
add a comment |
$begingroup$
Write out $A$ in its SVD, $A=USigma V^T$. Then we have
$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.
$endgroup$
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
add a comment |
$begingroup$
Write out $A$ in its SVD, $A=USigma V^T$. Then we have
$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.
$endgroup$
Write out $A$ in its SVD, $A=USigma V^T$. Then we have
$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.
edited Dec 5 '18 at 21:51
answered Dec 5 '18 at 21:47
whpowell96whpowell96
56615
56615
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
add a comment |
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58
add a comment |
$begingroup$
You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).
[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]
Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?
$endgroup$
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
add a comment |
$begingroup$
You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).
[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]
Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?
$endgroup$
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
add a comment |
$begingroup$
You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).
[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]
Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?
$endgroup$
You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).
[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]
Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?
answered Dec 5 '18 at 21:45
angryavianangryavian
40.6k23380
40.6k23380
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
add a comment |
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24
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%2f3027674%2finvertibility-of-textbfat-textbfa-epsilon-textbfi%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
$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59