How can you (efficiently) tell whether vectors are nearly parallel before trying to use Gram-Schmidt? What's a better algorithm for finding orthonormal bases?
emmurphy
In which case will this basis be better than the previous one?
rgrao
@elliott, I think we could check the dot product to see if a pair of normalized vectors align with each other closely or not. If the result is very close to 1, it means they are nearly parallel. But like Prof. Keenan mentioned during the Zoom call/lecture, another algorithm to do this would be QR decomposition.
bepis
@emmurphy, Gram-Schmidt is an algorithm used to find the orthonormal basis, not a basis itself. The orthonormal basis is generally nicer to compute things with compared to any other arbitrary basis, due to its unique properties mentioned on the previous slide. You could think of the standard orthonormal basis for R^3: <1,0,0>, <0,1,0>, <0,0,1>. They are like independent components or axes of your vector space. Maybe Prof. Keenan can elaborate more about when they are useful within graphics.
sponge
Why does this algorithm perform a lot worse with nearly parallel vectors? Or is it that QR decomposition is just better in the nearly parallel vectors case?
frog
sponge, I think if you have a bunch of nearly parallel vectors you can run into problems with having limited floating point precision for your representation of the vectors. When there are lots of parallel vectors the component of each next vector not already represented by the vectors before it will be very small, and this gets worse if we have lots of vectors or they're all close to parallel. If this is bad enough the vectors might be rounded so they're effectively not even an orthonormal basis for the purposes of your numerical calculations.
How can you (efficiently) tell whether vectors are nearly parallel before trying to use Gram-Schmidt? What's a better algorithm for finding orthonormal bases?
In which case will this basis be better than the previous one?
@elliott, I think we could check the dot product to see if a pair of normalized vectors align with each other closely or not. If the result is very close to 1, it means they are nearly parallel. But like Prof. Keenan mentioned during the Zoom call/lecture, another algorithm to do this would be QR decomposition.
@emmurphy, Gram-Schmidt is an algorithm used to find the orthonormal basis, not a basis itself. The orthonormal basis is generally nicer to compute things with compared to any other arbitrary basis, due to its unique properties mentioned on the previous slide. You could think of the standard orthonormal basis for R^3: <1,0,0>, <0,1,0>, <0,0,1>. They are like independent components or axes of your vector space. Maybe Prof. Keenan can elaborate more about when they are useful within graphics.
Why does this algorithm perform a lot worse with nearly parallel vectors? Or is it that QR decomposition is just better in the nearly parallel vectors case?
sponge, I think if you have a bunch of nearly parallel vectors you can run into problems with having limited floating point precision for your representation of the vectors. When there are lots of parallel vectors the component of each next vector not already represented by the vectors before it will be very small, and this gets worse if we have lots of vectors or they're all close to parallel. If this is bad enough the vectors might be rounded so they're effectively not even an orthonormal basis for the purposes of your numerical calculations.