Fast way to Invert ADA' when D is a diagonal matrix that changes each iteration?












6












$begingroup$


So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up being a .9 million by .9 million sized matrix.



A is m by n with m < n.



My thoughts have been drawn to doing an economic SVD on A to get A=SVU' (and V ends up being a square diagonal matrix) at which point I only need to worry about inverting the inner U'DU term and U'*U=I, I feel like there should be something possible but I can't figure it out.



Any ideas?



some additional notes: A is fairly sparse, preprocessing things like the SVD of A can take as long as necessary...etc



MATLAB code that i've tested to show that the suggested approach doesn't work (unsure how to format this):



rows=90;
cols=120;
G=rand(rows,cols);
[X,Y,Z]=svd(G,'econ');
A=Z'; %the above was just to generate A s.t. A'A=I, as in second paragraph above
d=rand(1,cols);
D=diag(d);
M=A*D*A';
Minv=M^(-1) %something to compare with
%[U,E,V]=svd(A); %also tried this, it didn't work either
[U,E,V]=svd(A,'econ');
Einv=E';
Einv(1:rows,1:rows)=diag(1./diag(E)); %calculate inverse of E
Ap=V*Einv*U';
Minv2=Ap'*D^(-1)*Ap;
max(max((Minv-Minv2).^2)) %did it work? (no)






matrices inverse sparse-matrices







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
    $endgroup$
    – Brian Borchers
    Jan 16 at 22:29










  • $begingroup$
    @BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
    $endgroup$
    – Charles Hernandez
    Jan 16 at 23:07












  • $begingroup$
    If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
    $endgroup$
    – Brian Borchers
    Jan 16 at 23:18










  • $begingroup$
    Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 9:36










  • $begingroup$
    @IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 15:51


















6












$begingroup$


So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up being a .9 million by .9 million sized matrix.



A is m by n with m < n.



My thoughts have been drawn to doing an economic SVD on A to get A=SVU' (and V ends up being a square diagonal matrix) at which point I only need to worry about inverting the inner U'DU term and U'*U=I, I feel like there should be something possible but I can't figure it out.



Any ideas?



some additional notes: A is fairly sparse, preprocessing things like the SVD of A can take as long as necessary...etc



MATLAB code that i've tested to show that the suggested approach doesn't work (unsure how to format this):



rows=90;
cols=120;
G=rand(rows,cols);
[X,Y,Z]=svd(G,'econ');
A=Z'; %the above was just to generate A s.t. A'A=I, as in second paragraph above
d=rand(1,cols);
D=diag(d);
M=A*D*A';
Minv=M^(-1) %something to compare with
%[U,E,V]=svd(A); %also tried this, it didn't work either
[U,E,V]=svd(A,'econ');
Einv=E';
Einv(1:rows,1:rows)=diag(1./diag(E)); %calculate inverse of E
Ap=V*Einv*U';
Minv2=Ap'*D^(-1)*Ap;
max(max((Minv-Minv2).^2)) %did it work? (no)






matrices inverse sparse-matrices







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
    $endgroup$
    – Brian Borchers
    Jan 16 at 22:29










  • $begingroup$
    @BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
    $endgroup$
    – Charles Hernandez
    Jan 16 at 23:07












  • $begingroup$
    If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
    $endgroup$
    – Brian Borchers
    Jan 16 at 23:18










  • $begingroup$
    Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 9:36










  • $begingroup$
    @IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 15:51
















6












6








6


0



$begingroup$


So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up being a .9 million by .9 million sized matrix.



A is m by n with m < n.



My thoughts have been drawn to doing an economic SVD on A to get A=SVU' (and V ends up being a square diagonal matrix) at which point I only need to worry about inverting the inner U'DU term and U'*U=I, I feel like there should be something possible but I can't figure it out.



Any ideas?



some additional notes: A is fairly sparse, preprocessing things like the SVD of A can take as long as necessary...etc



MATLAB code that i've tested to show that the suggested approach doesn't work (unsure how to format this):



rows=90;
cols=120;
G=rand(rows,cols);
[X,Y,Z]=svd(G,'econ');
A=Z'; %the above was just to generate A s.t. A'A=I, as in second paragraph above
d=rand(1,cols);
D=diag(d);
M=A*D*A';
Minv=M^(-1) %something to compare with
%[U,E,V]=svd(A); %also tried this, it didn't work either
[U,E,V]=svd(A,'econ');
Einv=E';
Einv(1:rows,1:rows)=diag(1./diag(E)); %calculate inverse of E
Ap=V*Einv*U';
Minv2=Ap'*D^(-1)*Ap;
max(max((Minv-Minv2).^2)) %did it work? (no)






matrices inverse sparse-matrices







share|cite|improve this question











$endgroup$




So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up being a .9 million by .9 million sized matrix.



A is m by n with m < n.



My thoughts have been drawn to doing an economic SVD on A to get A=SVU' (and V ends up being a square diagonal matrix) at which point I only need to worry about inverting the inner U'DU term and U'*U=I, I feel like there should be something possible but I can't figure it out.



Any ideas?



some additional notes: A is fairly sparse, preprocessing things like the SVD of A can take as long as necessary...etc



MATLAB code that i've tested to show that the suggested approach doesn't work (unsure how to format this):



rows=90;
cols=120;
G=rand(rows,cols);
[X,Y,Z]=svd(G,'econ');
A=Z'; %the above was just to generate A s.t. A'A=I, as in second paragraph above
d=rand(1,cols);
D=diag(d);
M=A*D*A';
Minv=M^(-1) %something to compare with
%[U,E,V]=svd(A); %also tried this, it didn't work either
[U,E,V]=svd(A,'econ');
Einv=E';
Einv(1:rows,1:rows)=diag(1./diag(E)); %calculate inverse of E
Ap=V*Einv*U';
Minv2=Ap'*D^(-1)*Ap;
max(max((Minv-Minv2).^2)) %did it work? (no)






matrices inverse sparse-matrices




matrices inverse sparse-matrices






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 18 at 19:15







Charles Hernandez

















asked Jan 16 at 22:24









Charles HernandezCharles Hernandez

312




312








  • 1




    $begingroup$
    Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
    $endgroup$
    – Brian Borchers
    Jan 16 at 22:29










  • $begingroup$
    @BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
    $endgroup$
    – Charles Hernandez
    Jan 16 at 23:07












  • $begingroup$
    If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
    $endgroup$
    – Brian Borchers
    Jan 16 at 23:18










  • $begingroup$
    Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 9:36










  • $begingroup$
    @IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 15:51
















  • 1




    $begingroup$
    Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
    $endgroup$
    – Brian Borchers
    Jan 16 at 22:29










  • $begingroup$
    @BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
    $endgroup$
    – Charles Hernandez
    Jan 16 at 23:07












  • $begingroup$
    If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
    $endgroup$
    – Brian Borchers
    Jan 16 at 23:18










  • $begingroup$
    Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 9:36










  • $begingroup$
    @IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 15:51










1




1




$begingroup$
Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
$endgroup$
– Brian Borchers
Jan 16 at 22:29




$begingroup$
Is $ADA^{T}$ positive definite? How sparse is $ADA^{T}$? Can the matrix be reordered to reduce fill-in in the factors? Do all of the entries in $D$ change in each iteration or just a few? Do you actually need the inverse of $ADA^{T}$ or just to solve systems of equations involving this matrix? Problems like these are dealt with in interior point methods for linear programming- there's a large literature on that.
$endgroup$
– Brian Borchers
Jan 16 at 22:29












$begingroup$
@BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
$endgroup$
– Charles Hernandez
Jan 16 at 23:07






$begingroup$
@BrianBorchers its for the algorithm from here: arxiv.org/pdf/1702.04300.pdf so its a convex optimization problem rather than a system of linear equations though it does have a closed form solution which is why I'm trying to invert $ADA^{T}$. I don't think $ADA^{T}$ is either PSD or sparse...
$endgroup$
– Charles Hernandez
Jan 16 at 23:07














$begingroup$
If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
$endgroup$
– Brian Borchers
Jan 16 at 23:18




$begingroup$
If the entries in $D$ are positive than $ADA^{T}$ will be positive definite. If entries in $D$ can be negative then the matrix might be indefinite.
$endgroup$
– Brian Borchers
Jan 16 at 23:18












$begingroup$
Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
$endgroup$
– Klaas van Aarsen
Jan 17 at 9:36




$begingroup$
Just an immediate observation, the A in your code is not mxn, but is nxn and orthogonal instead. Is that intended?
$endgroup$
– Klaas van Aarsen
Jan 17 at 9:36












$begingroup$
@IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
$endgroup$
– Charles Hernandez
Jan 17 at 15:51






$begingroup$
@IlikeSerena I just tested again to verify, it works correctly. You'd be right if it was a normal SVD, but Its an economic SVD at the start so for an m by n matrix with m<n you get 3 matrices, (mxm)(mxm)(nxm) and i'm setting A to to transpose of that nxm matrix. note: this is just so that the columns of A are orthagonal to see if that has any effect, the code does the same thing if you just set A to be a random mxn matrix.
$endgroup$
– Charles Hernandez
Jan 17 at 15:51












1 Answer
1






active

oldest

votes


















2












$begingroup$

How about:
$$(ADA')^{-1} = {A^+}' D^{-1} A^+$$
where $A^+$ is the Moore-Penrose pseudoinverse?



Note that if $A=USigma V'$ is the economic SVD, then $A^+=VSigma^{-1}U'$.



Btw, I'm assuming that your matrices are real, that $A$ is of rank $m$, and $D$ of rank $n$.




Edit:
Turns out that this doesn't work. I don't have a working solution (yet), only the following observations.



Let $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'},boxed{quad V'quad}$ be the economic SVD.



Then we can write the full SVD as $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'quad 0phantom'}begin{array}{|cc|}hline V'\ hline quad! N'!!quad\hlineend{array}$.



Moreover, the columns of $U$ form the column space of $A$. And the columns of $N$ form the null space of $A$.



Consequently we can write either:
$$(ADA')^{-1} = (USigma V'DVSigma' U')^{-1}=USigma^{-1}(V'DV)^{-1}Sigma^{-1}U'$$
or:
$$(ADA')^{-1} = left(U(Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma'}{0} U'right)^{-1}
= Uleft((Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma}{0}right)^{-1}U'$$
In the second form we can say that:
$$left(binom{V'}{N'}D(Vmid N)right)^{-1} = binom{V'}{N'}D^{-1}(Vmid N) $$
However, unfortunately we cannot leave out the $N$ submatrices and we have:
$$(V'DV)^{-1}ne V'D^{-1}V $$
This is why my original suggestion does not work.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:09












  • $begingroup$
    Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:12










  • $begingroup$
    That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:18












  • $begingroup$
    Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:24










  • $begingroup$
    U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:44












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%2f3076370%2ffast-way-to-invert-ada-when-d-is-a-diagonal-matrix-that-changes-each-iteration%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









2












$begingroup$

How about:
$$(ADA')^{-1} = {A^+}' D^{-1} A^+$$
where $A^+$ is the Moore-Penrose pseudoinverse?



Note that if $A=USigma V'$ is the economic SVD, then $A^+=VSigma^{-1}U'$.



Btw, I'm assuming that your matrices are real, that $A$ is of rank $m$, and $D$ of rank $n$.




Edit:
Turns out that this doesn't work. I don't have a working solution (yet), only the following observations.



Let $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'},boxed{quad V'quad}$ be the economic SVD.



Then we can write the full SVD as $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'quad 0phantom'}begin{array}{|cc|}hline V'\ hline quad! N'!!quad\hlineend{array}$.



Moreover, the columns of $U$ form the column space of $A$. And the columns of $N$ form the null space of $A$.



Consequently we can write either:
$$(ADA')^{-1} = (USigma V'DVSigma' U')^{-1}=USigma^{-1}(V'DV)^{-1}Sigma^{-1}U'$$
or:
$$(ADA')^{-1} = left(U(Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma'}{0} U'right)^{-1}
= Uleft((Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma}{0}right)^{-1}U'$$
In the second form we can say that:
$$left(binom{V'}{N'}D(Vmid N)right)^{-1} = binom{V'}{N'}D^{-1}(Vmid N) $$
However, unfortunately we cannot leave out the $N$ submatrices and we have:
$$(V'DV)^{-1}ne V'D^{-1}V $$
This is why my original suggestion does not work.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:09












  • $begingroup$
    Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:12










  • $begingroup$
    That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:18












  • $begingroup$
    Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:24










  • $begingroup$
    U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:44
















2












$begingroup$

How about:
$$(ADA')^{-1} = {A^+}' D^{-1} A^+$$
where $A^+$ is the Moore-Penrose pseudoinverse?



Note that if $A=USigma V'$ is the economic SVD, then $A^+=VSigma^{-1}U'$.



Btw, I'm assuming that your matrices are real, that $A$ is of rank $m$, and $D$ of rank $n$.




Edit:
Turns out that this doesn't work. I don't have a working solution (yet), only the following observations.



Let $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'},boxed{quad V'quad}$ be the economic SVD.



Then we can write the full SVD as $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'quad 0phantom'}begin{array}{|cc|}hline V'\ hline quad! N'!!quad\hlineend{array}$.



Moreover, the columns of $U$ form the column space of $A$. And the columns of $N$ form the null space of $A$.



Consequently we can write either:
$$(ADA')^{-1} = (USigma V'DVSigma' U')^{-1}=USigma^{-1}(V'DV)^{-1}Sigma^{-1}U'$$
or:
$$(ADA')^{-1} = left(U(Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma'}{0} U'right)^{-1}
= Uleft((Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma}{0}right)^{-1}U'$$
In the second form we can say that:
$$left(binom{V'}{N'}D(Vmid N)right)^{-1} = binom{V'}{N'}D^{-1}(Vmid N) $$
However, unfortunately we cannot leave out the $N$ submatrices and we have:
$$(V'DV)^{-1}ne V'D^{-1}V $$
This is why my original suggestion does not work.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:09












  • $begingroup$
    Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:12










  • $begingroup$
    That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:18












  • $begingroup$
    Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:24










  • $begingroup$
    U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:44














2












2








2





$begingroup$

How about:
$$(ADA')^{-1} = {A^+}' D^{-1} A^+$$
where $A^+$ is the Moore-Penrose pseudoinverse?



Note that if $A=USigma V'$ is the economic SVD, then $A^+=VSigma^{-1}U'$.



Btw, I'm assuming that your matrices are real, that $A$ is of rank $m$, and $D$ of rank $n$.




Edit:
Turns out that this doesn't work. I don't have a working solution (yet), only the following observations.



Let $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'},boxed{quad V'quad}$ be the economic SVD.



Then we can write the full SVD as $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'quad 0phantom'}begin{array}{|cc|}hline V'\ hline quad! N'!!quad\hlineend{array}$.



Moreover, the columns of $U$ form the column space of $A$. And the columns of $N$ form the null space of $A$.



Consequently we can write either:
$$(ADA')^{-1} = (USigma V'DVSigma' U')^{-1}=USigma^{-1}(V'DV)^{-1}Sigma^{-1}U'$$
or:
$$(ADA')^{-1} = left(U(Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma'}{0} U'right)^{-1}
= Uleft((Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma}{0}right)^{-1}U'$$
In the second form we can say that:
$$left(binom{V'}{N'}D(Vmid N)right)^{-1} = binom{V'}{N'}D^{-1}(Vmid N) $$
However, unfortunately we cannot leave out the $N$ submatrices and we have:
$$(V'DV)^{-1}ne V'D^{-1}V $$
This is why my original suggestion does not work.






share|cite|improve this answer











$endgroup$



How about:
$$(ADA')^{-1} = {A^+}' D^{-1} A^+$$
where $A^+$ is the Moore-Penrose pseudoinverse?



Note that if $A=USigma V'$ is the economic SVD, then $A^+=VSigma^{-1}U'$.



Btw, I'm assuming that your matrices are real, that $A$ is of rank $m$, and $D$ of rank $n$.




Edit:
Turns out that this doesn't work. I don't have a working solution (yet), only the following observations.



Let $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'},boxed{quad V'quad}$ be the economic SVD.



Then we can write the full SVD as $boxed{quad Aphantom'quad}=boxed{Uphantom'},boxed{Sigmaphantom'quad 0phantom'}begin{array}{|cc|}hline V'\ hline quad! N'!!quad\hlineend{array}$.



Moreover, the columns of $U$ form the column space of $A$. And the columns of $N$ form the null space of $A$.



Consequently we can write either:
$$(ADA')^{-1} = (USigma V'DVSigma' U')^{-1}=USigma^{-1}(V'DV)^{-1}Sigma^{-1}U'$$
or:
$$(ADA')^{-1} = left(U(Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma'}{0} U'right)^{-1}
= Uleft((Sigmamid0)binom{V'}{N'}D(Vmid N)binom{Sigma}{0}right)^{-1}U'$$
In the second form we can say that:
$$left(binom{V'}{N'}D(Vmid N)right)^{-1} = binom{V'}{N'}D^{-1}(Vmid N) $$
However, unfortunately we cannot leave out the $N$ submatrices and we have:
$$(V'DV)^{-1}ne V'D^{-1}V $$
This is why my original suggestion does not work.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 19 at 12:12

























answered Jan 16 at 23:49









Klaas van AarsenKlaas van Aarsen

4,3421822




4,3421822












  • $begingroup$
    Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:09












  • $begingroup$
    Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:12










  • $begingroup$
    That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:18












  • $begingroup$
    Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:24










  • $begingroup$
    U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:44


















  • $begingroup$
    Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:09












  • $begingroup$
    Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:12










  • $begingroup$
    That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:18












  • $begingroup$
    Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
    $endgroup$
    – Charles Hernandez
    Jan 17 at 1:24










  • $begingroup$
    U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
    $endgroup$
    – Klaas van Aarsen
    Jan 17 at 1:44
















$begingroup$
Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
$endgroup$
– Charles Hernandez
Jan 17 at 1:09






$begingroup$
Ignore that comment, didn't realize there was an edit deadline. So if you do that you would get $(ADA') ({A^+}' D^{-1} A^+)=(U Sigma V' D V Sigma U') times (U Sigma^{-1} V' D^{-1} V Sigma^{-1} U')$ so the U' and U cancels as do the $Sigma$'s but I believe $V V' neq I$ since V is n by m with n>m. i.e. you'd need V to have n orthagonal vectors of size m, no?
$endgroup$
– Charles Hernandez
Jan 17 at 1:09














$begingroup$
Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:12




$begingroup$
Yes. U is unitary, $Sigma$ is square and diagonal, and with the full unitary V we can invert VDV'.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:12












$begingroup$
That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:18






$begingroup$
That is, consider the full SVD to complete the multiplication where V is unitary. Afterwards we can discard the part of V again that corresponds to the null space of A.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:18














$begingroup$
Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
$endgroup$
– Charles Hernandez
Jan 17 at 1:24




$begingroup$
Sorry if i'm making this harder than it has to be.... I'm not sure what your last comment is implying. Is that the definition of economic SVD? or are you saying something more nuanced.
$endgroup$
– Charles Hernandez
Jan 17 at 1:24












$begingroup$
U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:44




$begingroup$
U is exactly the column space of A. In a full SVD, V contains the column space of A' plus the null space of A'. In an economic SVD that null space is left out since it serves no purpose. But with it V is unitary, which facilitates a proof.
$endgroup$
– Klaas van Aarsen
Jan 17 at 1:44


















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%2f3076370%2ffast-way-to-invert-ada-when-d-is-a-diagonal-matrix-that-changes-each-iteration%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

Questions related to Moebius Transform of Characteristic Function of the Primes

Image
2 $begingroup$ Consider the function defined in (1) below related to the fundamental prime counting function $pi(x)$ . Note that A143519(n) is not multiplicative. (1) $quad f(x)=sumlimits_{n=1}^{x}A143519(n)$ https://oeis.org/A143519 The following plot illustrates $f(x)$ defined in formula (1) above. Figure (1) : Illustration of $f(x)$ defined in formula (1) The integer zeros of $f(x)$ for $xle 10,000$ are listed in (2) below. (2) $quad$ {1,6,9,12,19,30,79,80,81,116,193,201,287,288,291,668,673,679,680,685,686,1109} The zero crossings of $f(x)$ for $xle 10,000$ where $f(x)$ doesn't settle at zero are listed in (3) below. (3) $quad$ {14,21,33,114,115,118,195,286,290,295,442,445,665,667,670,671,678,682} Question (1) : Does $f(x)$ have a finite number of integer zeros, and if so ...
Read more

List of scandals in India

Image
List of scandals in India From Wikipedia, the free encyclopedia Jump to navigation Jump to search This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries. This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages) This article has an unclear citation style . The references used may be made clearer with a different or consistent style of citation and footnoting. ( January 2014 ) (Learn how and when to remove this template message) This list is in reverse order. As a consequence it appears to be slanted towards recent events. Please try to keep recent events in historical perspective and add more content related to non-recent events. ( May 2013 ) (Learn how and when to remove this template message) ...
Read more

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

Image
0 1 What exactly does the error message beginning with E: mean? I assume it has to do with the file structure on Ubuntu-on-Windows, but what exactly? The following package was automatically installed and is no longer required: os-prober Use 'apt-get autoremove' to remove it. The following extra packages will be installed: libxslt1.1 The following NEW packages will be installed: libxslt1.1 xmlstarlet 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded. Need to get 435 kB of archives. After this operation, 1023 kB of additional disk space will be used. Get:1 http://archive.ubuntu.com/ubuntu/ trusty/main libxslt1.1 amd64 1.1.28-2build1 [145 kB] Get:2 http://archive.ubuntu.com/ubuntu/ trusty/universe xmlstarlet amd64 1.5.0-1 [290 kB] ...
Read more