Given two subspaces $U,V\subset \mathbb{R}^n$ and orthonomal bases $U = \{u_1,\ldots,u_p\}$ and $V = \{v_1,\ldots, v_q\}$ (wlog $p\geq 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.
Why should there be a faster algorithm? Take $U$ included in $\mathbb{R}^4$, $$ U = span( [1, 0, 0, 0]^T, [0, 1, 0, 0]^T) $$ and $$ V = span([1; 1; 1; 0] / \sqrt{3}, [a; b; 0; 1] / \sqrt{1 + a^2 + b^2}) $$ $a = b = 0$ yields indeed a simplification. $a = 1, b = -1$ requires an orthogonalization against $U$