10
$\begingroup$

Let $K$ be a given integer, with $K$ even (and "large"). Let $\mathbf{v} \in \mathbb{R}^{K \times 1}$ be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix $\mathbf{B} \in \mathbb{R}^{K \times K-1}$ such as that: $(1)$ the column-vectors of $\mathbf{B}$ are orthogonal to each other; $(2)$ $\mathbf{B^T v} = \mathbf{0}$, where $^T$ denotes transpose and $\mathbf{0}$ a ((K-1)-dimensional) vector of all zeros.

Denoting with $\mathbf{b}_i$, $i=1,\dots,K-1$, the $i$-th column of $\mathbf{B}$, the first requirement can be rewritten as: $\mathbf{b}_i^T \mathbf{b}_j = 0$ for $i \neq j$.

Essentially, the problem asks to write an algorithm to find an orthogonal basis to the orthogonal complement of the (mono-dimensional) space spanned by $\mathbf{v}$. The algorithm can be written in pseudo-code (or in MATLAB-like or in C-like code). The algorithm takes in input the vector $\mathbf{v}$ and the integer $K$; its output is the matrix $\mathbf{B}$.

Note: the algorithm cannot do a "random trial-and-error", i.e., generate a random vector, try if it is orthogonal to $\mathbf{v}$ and to the previously found columns of $\mathbf{B}$, discard if it not, memorize it if it is. This is an explicitly forbidden brute-force approach. However, it is indeed allowed to do this as an initializing stage, i.e., for the first column of the matrix or as a "random guess" at the start, if any need to do so should arise. "Normality", i.e., finding an orthonormal basis, is not required. Input checking (e.g. checking if $K$ is an even integer) is not required.

EDIT: My thoughts and previous attempts: The problem is essentially an implementation of Gram-Schmidts orthonormalization process. However, it cannot simply be used as stated, because Gram-Schimdts' theorem assumes to start with a basis (which we do not have). What we can actually construct is a spanning set of vectors, i.e. $\mathbf{v}, e_1, \dots, e_K$, where $e_i$ denotes the $i$-th canonical base vector.

I have already implemented Gram-Schmidts, paying attention to numerical issues. The problem is a slight generalization of the process, in which you do not start with a basis, but with a spanning set, find a suitable basis in the set (I don't know how to do it), which must contain $\mathbf{v}$ as its first element, and then apply Gram-Schimdts process.

P.S. Any help is appreciated, I am no master of linear algebra, especially numerical implementations. Thanks.

$\endgroup$
  • $\begingroup$ The onus is on you to test, you get what you pay for. $\endgroup$ – copper.hat Mar 12 '14 at 23:06
  • $\begingroup$ For orthogonalizing $v,e_1,\ldots,e_K$, you would need to implement some sort of rank revealing Gram-Schmidt (see en.wikipedia.org/wiki/RRQR_factorization); SVD can be useful or simply Gram-Schmidt with pivoting could work as well. I just wonder how that "random trial-and-error" approach would work when one normally does not have the eternity available for calculations. $\endgroup$ – Algebraic Pavel Mar 13 '14 at 12:00
  • 1
    $\begingroup$ @AlgebraicPavel: I used to have a 'fear' of random algorithms (I'm thinking continuous parameter optimization here), but having seen the amount of randomness added by spurious programming/design (and things still work), I have moved beyond my fear :-). $\endgroup$ – copper.hat Mar 13 '14 at 16:07
  • $\begingroup$ @AlgebraicPavel: It is exactly the reason why it was explicitly forbidden (although it was obvious). Note, however, that for extremely low $K$, it does work and that, for very big $K$, a "rationalized" random trial-and-error (with optimization) could actually work, since, for $K$ big, vectors tend to naturally be "numerically orthogonal" to each other. With optimization, I underline. "And things still work", strangely enough. :-) $\endgroup$ – PseudoRandom Mar 13 '14 at 20:45
2
$\begingroup$

Run Gram Schmidt orthogonalization on the vectors $v,e_1,...,e_K$ (ignore one of the reductions as it will be zero or near zero if numerics are an issue), to get $v_1,...,v_K$. Then let $B= \begin{bmatrix} v_2 \cdots v_K \end{bmatrix}$.

Details:

By $e_k$ I mean the vector of zeroes with a one in the $k$th position. Note that $e_1,...,e_K$ forms a basis for $\mathbb{R}^K$.

Let $u_1 = v, u_k = e_{k+1}$ for $k=1,...,K$. Note that $u_1,...,u_{K+1}$ is a spanning set but is not a basis.

Then the algorithm (this is theoretical, in a practical situation the comparison in Step 3 would be replaced by something like $\|w_i\| < \epsilon$) looks like:

  1. $v_1 = {u_1 \over \|u_1\|}$, $i=2$
  2. $w_i = u_i - \sum_{j=1}^{i-1} v_j^T u_i$
  3. if $w_i \neq 0$ then $v_i = { w_i \over \|w_i\|}$ else $v_i = 0$
  4. $i \leftarrow i+1$, if $i \le K+1$ goto Step 2

This is basically the Gram Schmidt algorithm, except one of the $v_i$s will be zero.

By construction, $\operatorname{sp} \{ u_1,...,u_i \} = \operatorname{sp} \{ v_1,...,v_i \}$, hence the final set will span $\mathbb{R}^K$ (since $u_2,...,u_{K+1}$ is a basis). Consequently exactly one of the $v_i$s will be zero.

Also by construction, $v_j^T v_i = 0$ for all $j<i$, and $\|v_i\| = 1$ for all $i$ except one. Let $v'_i, i=1,...,K$ be the non-zero $v_i$s.

Now let $B = \begin{bmatrix} v'_2 \cdots v'_K \end{bmatrix}$ and note that $B^T v'_1 = 0$, and since $v = \|v\| v'_1$, we are finished.

$\endgroup$
  • $\begingroup$ Thanks! It (partially) answers my question: I see a problem in that. Gram-Schmidts orthogonalization assumes you already have a basis to start with (I recently checked it: the theorem starts with a basis, not a spanning set). If, for example, $\mathbf{v}$ = $\mathbf{e}_1$, then what is the "discard criterion" when you do the scalar products $\mathbf{v}^T \mathbf{e}_i$? P.S. When I said "test" I didn't mean numerical tests (of which the onus is on me), I apologize for the poor wording. What I actually meant was simply theoretically correct algorithms. $\endgroup$ – PseudoRandom Mar 13 '14 at 8:39
  • $\begingroup$ @PseudoRandom: I have added details above. There is no problem, the algorithm basically discards vectors that are in the span of the previously computed elements. This is a theoretical algorithm, it would need to be adapted to handle numerics (or better still, just use a QR decomposition). Actually, I am always a little surprised that the Gram Schmidt algorithm and minor extensions as above are not emphasised more in classes. It is a very useful tool numerical or not. $\endgroup$ – copper.hat Mar 13 '14 at 16:01
  • $\begingroup$ In other words, you just proved that, in the Gram-Schimdt theorem, the hypothesis of starting with a basis is uncalled for: a spanning set is more than enough. This was unknown to me. Thank you! P.S. I personally don't like QR decomposition. Numerically speaking, it is not as good as it seems (I am aware of MGS, Modified Gram Schmidt). If you only have to find an orthogonal basis, the normalizing step is not a great idea. It often occured to me that orthogonality (even approximate orthogonality) is lost with normalization, but may be keeped if you do not normalize. Anyway, thanks! $\endgroup$ – PseudoRandom Mar 13 '14 at 20:57
  • $\begingroup$ Well, the usual Gram Schmidt presentation doesn't account for the case when the initial collection is linearly dependent, but (numerics aside) this is easy to deal with. The modified method (MGS, that is) is generally taken to have better properties, the above can be easily modified to avoid the premature normalizing. $\endgroup$ – copper.hat Mar 13 '14 at 21:07
  • $\begingroup$ Question: can the normalization step simply be skipped altogether, since the goal is an orthogonal basis (and not an orthonormal basis)? If (as I think), yes, it could help orthogonality, numerically speaking. P.S. We never considered any variation (no matter how minor) of the Gram-Schimdt process. $\endgroup$ – PseudoRandom Mar 13 '14 at 21:14
8
$\begingroup$

By the way, most likely a much simpler and efficient way to compute your matrix $B$ here is just using a single Householder reflection. Consider $w=v\pm\|v\|_2e_1$ (the sign in "$\pm$" is usually chosen to be same as in the first component in $v$ from numerical reasons). Then set $Q=I-2ww^T/w^Tw$. Since $Qv=\mp\|v\|_2e_1$ (depending on the choice of the sign in $w$), we have $v=\mp\|v\|_2Qe_1$ (multiply by $Q^T=Q$). It means that $v$ is a scalar multiple of the first column (row) of the orthogonal matrix $Q$. Let $Q=[q_1,\ldots,q_K]$. It follows that $q_i^Tv=0$ for $i=2,\ldots,K$. Hence $B=[q_2,\ldots,q_K]$ satisfies $B^Tv=0$ and $B^TB=I$.

In contrast to the $O(K^3)$ complexity of the Gram-Schmidt approach (which is of course generally applicable to compute orthonormal basis for any given set of vectors), this way you get your $B$ using $O(K^2)$ operations if you need the full matrix explicitly computed or $O(K)$ if it's enough to have it implicitly represented by $w$.

$\endgroup$
  • $\begingroup$ A lot of time has passed, but your answer deserves compliments. It is, in fact, an efficient algorithm and the one I'm actually using is (a variant of) this one. Initially, I was unaware of "Householder magic" (the unofficial name of Householder transformations), thus I went with QR/MGS and was satisfied with that. Thank you for your contribution. $\endgroup$ – PseudoRandom Mar 27 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.