Mixing
Approximate low-rank $U^top U$ decomposition / Gaussian elimination.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Page 66 in this slideset discusses and presents an example for the following idea: given the idea that a (Laplacian, hence square) matrix can be exactly decomposed as
$$ A = U^top U $$
(which could be obtained by Gaussian elimination), define the approximated decomposition problem
$$ A approx V^top V$$
where $V$ is lower rank (notionally even a column vector). The slides give a numerical example rather than the algorithm itself, but there are steps I can't follow (it starts with "Find the rank-1 matrix that agrees on" (in the sense of producing the approximated $V_1^top V_1$ matrix reproducing) "the first row and column" -- how?).
I guess my question is more like "does this have a name? Is it implemented in linear algebra packages?" than "how exactly is this computed" (because my naive implementation of a detailed explanation would probably suck). Barring that, some light on how "find the low-rank matrix that agrees work" would be immensely appreciated.
numerical-linear-algebra
asked Aug 3 at 15:04
user8948
355
add a comment |Â
up vote
0
down vote
favorite
Page 66 in this slideset discusses and presents an example for the following idea: given the idea that a (Laplacian, hence square) matrix can be exactly decomposed as
$$ A = U^top U $$
(which could be obtained by Gaussian elimination), define the approximated decomposition problem
$$ A approx V^top V$$
where $V$ is lower rank (notionally even a column vector). The slides give a numerical example rather than the algorithm itself, but there are steps I can't follow (it starts with "Find the rank-1 matrix that agrees on" (in the sense of producing the approximated $V_1^top V_1$ matrix reproducing) "the first row and column" -- how?).
I guess my question is more like "does this have a name? Is it implemented in linear algebra packages?" than "how exactly is this computed" (because my naive implementation of a detailed explanation would probably suck). Barring that, some light on how "find the low-rank matrix that agrees work" would be immensely appreciated.
numerical-linear-algebra
asked Aug 3 at 15:04
user8948
355
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Page 66 in this slideset discusses and presents an example for the following idea: given the idea that a (Laplacian, hence square) matrix can be exactly decomposed as
$$ A = U^top U $$
(which could be obtained by Gaussian elimination), define the approximated decomposition problem
$$ A approx V^top V$$
where $V$ is lower rank (notionally even a column vector). The slides give a numerical example rather than the algorithm itself, but there are steps I can't follow (it starts with "Find the rank-1 matrix that agrees on" (in the sense of producing the approximated $V_1^top V_1$ matrix reproducing) "the first row and column" -- how?).
I guess my question is more like "does this have a name? Is it implemented in linear algebra packages?" than "how exactly is this computed" (because my naive implementation of a detailed explanation would probably suck). Barring that, some light on how "find the low-rank matrix that agrees work" would be immensely appreciated.
numerical-linear-algebra
asked Aug 3 at 15:04
user8948
355
Page 66 in this slideset discusses and presents an example for the following idea: given the idea that a (Laplacian, hence square) matrix can be exactly decomposed as
$$ A = U^top U $$
(which could be obtained by Gaussian elimination), define the approximated decomposition problem
$$ A approx V^top V$$
where $V$ is lower rank (notionally even a column vector). The slides give a numerical example rather than the algorithm itself, but there are steps I can't follow (it starts with "Find the rank-1 matrix that agrees on" (in the sense of producing the approximated $V_1^top V_1$ matrix reproducing) "the first row and column" -- how?).
I guess my question is more like "does this have a name? Is it implemented in linear algebra packages?" than "how exactly is this computed" (because my naive implementation of a detailed explanation would probably suck). Barring that, some light on how "find the low-rank matrix that agrees work" would be immensely appreciated.
numerical-linear-algebra
asked Aug 3 at 15:04
user8948
355
asked Aug 3 at 15:04
user8948
355
asked Aug 3 at 15:04
user8948
355
asked Aug 3 at 15:04
user8948
355
355
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35
add a comment |Â
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871177%2fapproximate-low-rank-u-top-u-decomposition-gaussian-elimination%23new-answer', 'question_page');
);
Post as a guest
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
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
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
You should consider asking this here: scicomp.stackexchange.com.
– amarney
Aug 3 at 15:14
The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank.
– Algebraic Pavel
Aug 3 at 15:35