Given a vector $\vec{x}$ with unit magnitude, we want to find a $m \times n$ matrix B such that $BB^T = I$, with first row $\vec{B}_0 = \vec{x}$. To do this, we calculate $\vec{p}=\frac{\vec{x}+\vec{e}_0}{\sqrt{1+x_0}}$ where $x_0$ is the first element of $\vec{x}$ and $\vec{e}_0$ is the first standard basis vector. We then calculate $B$ with an outer product operation as $\vec{p}_{k \leq m}\vec{p}^T - I$, where $\vec{p}_{k \leq m}$ is $\vec{p}$ truncated to the first $m$ elements.
$$\displaystyle \vec{p}=\frac{\vec{x}+\vec{e}_0}{\sqrt{1+x_0}}$$
$$\displaystyle B=\vec{p}_{k \leq m}\vec{p}^T - I$$
This is obviously of the order $(nm)/2$ operations, but by making creative use of pointers this can be even faster. Note each column is independently calculable as scalar multiplication of $\vec{p}$ followed by a single element change. Passing that scalar through to following operations allows for working with just $\vec{p}$ with a single element modification, effectively making the method an $O(m)$ cost when applied right.
No comments:
Post a Comment