Mixing
Orthogonalize two sets of vectors against one another
$begingroup$
Given two subspaces $U,Vsubset mathbb{R}^n$ and orthonomal bases $U = {u_1,ldots,u_p}$ and $V = {v_1,ldots, v_q}$ (wlog $pgeq q$) is there a fast way to compute an orthonormal basis for $U+V$?
The naieve approach is to use Gram-Schmidt to orthogonalize the smaller basis for $V$ against that of $U$. However this does not take advantage of the fact that we know an orthogonal basis for $V$.
I have talked to a couple professors and they weren't familiar with any algorithms for this problem, so if anyone has some resources which might be related I would be interested. Approximation algorithms and heuristics are very welcome too
Some simplifying assumptions we could make are
- $U cap V = 0$
- $p,q ll n$
- That we only need to add $k<q$ vectors to $U$ so that $U+{v_1,ldots, v_k}$ is contained in $U+V$
A related question is if there is a way to append some orthonormal vectors to $U$ with no restriction as to how that changes the span of the new set.
linear-algebra numerical-methods numerical-linear-algebra
asked Jan 13 at 16:06
tchtch
783310
$endgroup$
add a comment |
$begingroup$
Given two subspaces $U,Vsubset mathbb{R}^n$ and orthonomal bases $U = {u_1,ldots,u_p}$ and $V = {v_1,ldots, v_q}$ (wlog $pgeq q$) is there a fast way to compute an orthonormal basis for $U+V$?
The naieve approach is to use Gram-Schmidt to orthogonalize the smaller basis for $V$ against that of $U$. However this does not take advantage of the fact that we know an orthogonal basis for $V$.
I have talked to a couple professors and they weren't familiar with any algorithms for this problem, so if anyone has some resources which might be related I would be interested. Approximation algorithms and heuristics are very welcome too
Some simplifying assumptions we could make are
- $U cap V = 0$
- $p,q ll n$
- That we only need to add $k<q$ vectors to $U$ so that $U+{v_1,ldots, v_k}$ is contained in $U+V$
A related question is if there is a way to append some orthonormal vectors to $U$ with no restriction as to how that changes the span of the new set.
linear-algebra numerical-methods numerical-linear-algebra
asked Jan 13 at 16:06
tchtch
783310
$endgroup$
1
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20
add a comment |
$begingroup$
Given two subspaces $U,Vsubset mathbb{R}^n$ and orthonomal bases $U = {u_1,ldots,u_p}$ and $V = {v_1,ldots, v_q}$ (wlog $pgeq q$) is there a fast way to compute an orthonormal basis for $U+V$?
The naieve approach is to use Gram-Schmidt to orthogonalize the smaller basis for $V$ against that of $U$. However this does not take advantage of the fact that we know an orthogonal basis for $V$.
I have talked to a couple professors and they weren't familiar with any algorithms for this problem, so if anyone has some resources which might be related I would be interested. Approximation algorithms and heuristics are very welcome too
Some simplifying assumptions we could make are
- $U cap V = 0$
- $p,q ll n$
- That we only need to add $k<q$ vectors to $U$ so that $U+{v_1,ldots, v_k}$ is contained in $U+V$
A related question is if there is a way to append some orthonormal vectors to $U$ with no restriction as to how that changes the span of the new set.
linear-algebra numerical-methods numerical-linear-algebra
asked Jan 13 at 16:06
tchtch
783310
$endgroup$
Given two subspaces $U,Vsubset mathbb{R}^n$ and orthonomal bases $U = {u_1,ldots,u_p}$ and $V = {v_1,ldots, v_q}$ (wlog $pgeq q$) is there a fast way to compute an orthonormal basis for $U+V$?
The naieve approach is to use Gram-Schmidt to orthogonalize the smaller basis for $V$ against that of $U$. However this does not take advantage of the fact that we know an orthogonal basis for $V$.
I have talked to a couple professors and they weren't familiar with any algorithms for this problem, so if anyone has some resources which might be related I would be interested. Approximation algorithms and heuristics are very welcome too
Some simplifying assumptions we could make are
- $U cap V = 0$
- $p,q ll n$
- That we only need to add $k<q$ vectors to $U$ so that $U+{v_1,ldots, v_k}$ is contained in $U+V$
A related question is if there is a way to append some orthonormal vectors to $U$ with no restriction as to how that changes the span of the new set.
linear-algebra numerical-methods numerical-linear-algebra
linear-algebra numerical-methods numerical-linear-algebra
asked Jan 13 at 16:06
tchtch
783310
asked Jan 13 at 16:06
tchtch
783310
edited Jan 13 at 16:21
tch
asked Jan 13 at 16:06
tchtch
783310
asked Jan 13 at 16:06
tchtch
783310
asked Jan 13 at 16:06
tchtch
783310
783310
1
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20
add a comment |
1
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20
1
1
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20
add a comment |
0
active
oldest
votes
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%2f3072156%2forthogonalize-two-sets-of-vectors-against-one-another%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3072156%2forthogonalize-two-sets-of-vectors-against-one-another%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
1
$begingroup$
When you wrote that $Ucap V=emptyset$, did you really mean that?
$endgroup$
– José Carlos Santos
Jan 13 at 16:09
$begingroup$
I think so. For example of $U = { (1,0,0), (0,1,0) }$ and $V = { (1,1,1) }$.
$endgroup$
– tch
Jan 13 at 16:16
$begingroup$
But you wrote that $U$ and $V$ are subspaces. And for any two subspaces, you always have $0$ in their intersection.
$endgroup$
– José Carlos Santos
Jan 13 at 16:20
$begingroup$
My mistake, I meant the intersection is trivial. I have edited this now.
$endgroup$
– tch
Jan 13 at 16:20