Jump to content
  • Advertisement
Sign in to follow this  
kloffy

Orthonormal basis of the orthogonal complement of a one dimensional subspace

This topic is 2944 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Phew, that's quite a thread title. I've stumbled across this old thread about generating the vertices of platonic solids and I found the approaches suggested by Emergent quite interesting. For a tetrahedron he suggests projecting the 4D unit vectors onto the subspace with normal (1,1,1,1). Given a orthonormal basis of this subspace calculating the orthogonal projection is quite simple (P = A*A^T where A is a matrix whose columns are the orthonormal basis vectors). However, I'm wondering how to generate such a basis.

Now, after searching the web, I've found a way to generate an orthonormal basis for the orthogonal complement of any subspace using singular value decomposition, but to be honest I don't quite understand how it works. I know it decomposes a matrix A into U, S and V such that A = U*S*V^T, but that's about it. It also seems more generic than it would need it to be, because it works for subspaces of arbitrary dimensions. If anybody's interested here's my implementation using ILNumerics.Net:

        static ILArray<double> OrthogonalComplement(ILArray<double> basis)
{
var U = new ILArray<double>();
var V = new ILArray<double>();
var S = ILMath.svd(basis, ref U, ref V);

return U[":", string.Format("{0}:end", basis.Dimensions[1])];
}



Some examples:

            Console.WriteLine(OrthogonalComplement(new ILArray<double>(new double[] {
1, 0, 0,
0, 1, 0
}, 3, 2)));

// Result:
// [0, 0, 1]

Console.WriteLine(OrthogonalComplement(new ILArray<double>(new double[] {
1, 1, 1, 1
}, 4, 1)));

// Result:
// [-0.5, 0.83333, -0.16667, -0.16667]
// [-0.5, -0.16667, 0.83333, -0.16667]
// [-0.5, -0.16667, -0.16667, 0.83333]



If I have some extra time, I'll definitely invest it to try and understand singular value decomposition. This article looks like a good place to start, as it is based on a concrete example, which is always nice. However, right now I have to move on because I'm getting slightly off track with what I really *should* be doing...

Anyways, I was wondering if somebody knows an approach that is maybe a bit easier to follow.

Share this post


Link to post
Share on other sites
Advertisement
Ah, the great Dave Eberly! Many of your PDFs are safely archived on my computer for future reference. I haven't knowingly come across this one, yet. It indeed looks very much like what I'm looking for. Excellent and concise description, as always. Thank you!

Share this post


Link to post
Share on other sites
Hey! :-) A pleasant surprise to see an old post of mine mentioned.

If you just need a basis that's orthonormal, and perpendicular to (1,1,...,1), you can just use the DCT or Hadamard basis. The DCT basis in n dimensions, for instance, is a collection of vectors v1,v2,...,vn with vi=(vi1,...,vin) for all vi and

vik = ci cos( (pi/n)*(k-1/2)*(i-1) )

where

c1 = sqrt(1/n)

and

ci = sqrt(2/n)

for i > 1

are constants that make the vectors unit-length.

You'll notice that v1 is proportional to (1,1,...,1), since then i-1=0, and cos(0)=1. And you can prove that all the vi are orthogonal to one another. So the vectors v2,...,vn span the subspace orthogonal to (1,1,...,1).

[Edited for clarity.]

[Edited by - Emergent on October 24, 2010 4:27:20 PM]

Share this post


Link to post
Share on other sites
Hey, cool! I wasn't sure if you'd still be around. I really like your approach because it is very easy to visualize in 2D/3D and it still works quite intuitively when you extend it to 3D/4D. You mentioned the DCT basis in your original post, thanks for elaborating on that! I really wanted to learn a method that works with an arbitrary normal, though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!