|
Size: 2271
Comment: Link
|
Size: 3522
Comment: Cleanup
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| Two vectors ''a'' and ''b'' can be orthonormalized into [[Calculus/UnitVector|unit vectors]] ''A'' and ''B''. This means... 1. that they are made [[Calculus/Orthogonality|orthogonal]] to each other by removing any components of one from the other. 2. that they are normalized to a unit [[Calculus/Distance|distance]] of 1. |
Two vectors ''A'' and ''B'' can be orthonormalized into [[Calculus/UnitVector|unit vectors]] ''â'' and ''b̂''. This means... 1. that they are made [[Calculus/Orthogonality|orthogonal]] to each other by removing any components of one from the other: ''A'' to ''a'' and ''B'' to ''b''. 2. that they are normalized to a unit [[Calculus/Distance|distance]] of 1: ''a'' to ''â'' and ''b'' to ''b̂''. |
| Line 17: | Line 17: |
| These are accomplished in discrete steps. The first is to enforce orthogonality. But orthogonality is a property of two vectors, not one. Therefore ''a'' needs no transformation to become ''A''. | This is a linear combination and does not change the column space of a system that includes both ''A'' and ''B''. Put another way, if ''A'' and ''B'' are a [[LinearAlgebra/Basis|basis]], then ''â'' and ''b̂'' will be a basis for the exact same column space. But as they are orthonormal, certain operations will be simpler. |
| Line 19: | Line 19: |
| The process of transforming ''b'' into ''B'' is simply the subtraction of all components of ''a'' from ''b''. This is a linear combination and does not change the column space of a system that includes both ''a'' and ''b''. [[LinearAlgebra/Projection|Projections]] are a complimentary idea; ''p'' is the component of ''a'' that estimates ''b''. The process of '''orthonormalization''' is the same as computing projections but the error term ''e'' is the desired result. Recall that ''e = b - ax̂'' and ''x̂ = (A^T^b)/(A^T^A)''. Therefore, ''B = b - A (A^T^b)/(A^T^A)''. | |
| Line 21: | Line 20: |
| To transform another vector ''c'' into being orthogonal to ''both'' ''A'' and ''B'', apply the same process for each component: ''C = c - A (A^T^c)/(A^T^A) - B (B^T^c)/(B^T^B)''. | |
| Line 23: | Line 21: |
| The final step is to normalize the orthogonal vectors by their own distance, as in ''A/||A||'' and ''B/||B||''. | === Solution === The '''Gram-Schmidt procedure''' is an algorithm for orthonormalization. First, note that orthogonality is a property of two vectors, not one. Therefore ''A'' needs no transformation to become ''a''. ''B'' is transformed into ''b'' by subtracting all components of ''a'' from ''B''. Recall that [[LinearAlgebra/Projection|projections]] capture how much a vector moves in the column space of another vector. It follows that subtracting the projection of ''a'' onto ''B'', from ''B'', results in a ''b'' that is independent of ''a''. This is generally notated as ''b = B - [(a⋅B)/(a⋅a)]a'' (i.e., in terms of the [[Calculus/VectorOperations#Dot_Product|dot product]]) or ''b = B - [(a^T^B)/(a^T^a)]a''. But it can also be expressed in terms of the [[LinearAlgebra/InnerProduct|inner product]]: ''b = B - [⟨a, B⟩/⟨a, a⟩]a''. If there is a third term ''C'', it must be transformed by subtracting all components of ''a'' and of ''b'' (not ''B''!) from ''C''. That is, ''c = C - [(a^T^C)/(a^T^a)]a - [(b^T^C)/(b^T^b)]b'' or ''c = C - [⟨a, C⟩/⟨a, a⟩]a - [⟨b, C⟩/⟨b, b⟩]b''. And so on. The final step is to normalize each vector by their own distance, as in ''â = a/||a||''. |
| Line 31: | Line 41: |
| The process applied to vectors is also applicable to the columns in a matrix. Instead of vectors ''a'' and ''b'', use ''v,,1,,'' and ''v,,2,,'' in '''''V'''''. The process yields ''u,,1,,'' and ''u,,2,,'' in '''''U'''''. Then the columns are normalized into '''''Q''''' like ''q,,1,, = u,,1,,/||u,,1,,||''. | Only a square matrix can be called '''orthogonal'''. |
| Line 33: | Line 43: |
| To re-emphasize, this is a linear combination generalized as '''''A''' = '''QR''''', and does not change the column space of '''''A'''''. | With that said, matrices of any size can be called '''orthonormal''', meaning that the columns are orthonormal vectors. |
| Line 35: | Line 45: |
| Note that '''''Q''''' is a [[LinearAlgebra/Orthogonality|matrix with orthonormal columns]]; it must also be square to be called an '''orthogonal matrix'''. | === Solution for Square Matrices === The Gram-Schmidt procedure can be directly applied to the columns of a square matrix. To reiterate, it does not change the column space. Note that the procedure involves linear combinations. First, to orthogonalize a column, a combination of all preceding columns is subtracted. Second, to normalize a column, some portion of itself is taken. Therefore the diagonal will be the normalizing factors, the values above the diagonal will be the components of other columns to subtract, and everything below the diagonal will be zeros. This can be expressed as a matrix, and importantly it will be an upper triangular matrix. Following the above notation, where a matrix has columns ''A'', ''B'', and ''C'' and the transformed matrix will have columns ''â'', ''b̂'', and ''ĉ'': {{attachment:r.svg}} The orthonormalized columns comprise the matrix '''''Q'''''. Because this matrix is orthonormal, it has useful properties like '''''Q'''^T^ = '''Q'''^-1^''. Altogether, this is the '''QR decomposition''' and it is expressed as '''''A''' = '''QR'''''. |
Orthonormalization
Gram-Schmidt orthonormalization is a process for transforming a vectors into unit vectors.
Vectors
Two vectors A and B can be orthonormalized into unit vectors â and b̂. This means...
that they are made orthogonal to each other by removing any components of one from the other: A to a and B to b.
that they are normalized to a unit distance of 1: a to â and b to b̂.
This is a linear combination and does not change the column space of a system that includes both A and B. Put another way, if A and B are a basis, then â and b̂ will be a basis for the exact same column space. But as they are orthonormal, certain operations will be simpler.
Solution
The Gram-Schmidt procedure is an algorithm for orthonormalization.
First, note that orthogonality is a property of two vectors, not one. Therefore A needs no transformation to become a.
B is transformed into b by subtracting all components of a from B. Recall that projections capture how much a vector moves in the column space of another vector. It follows that subtracting the projection of a onto B, from B, results in a b that is independent of a.
This is generally notated as b = B - [(a⋅B)/(a⋅a)]a (i.e., in terms of the dot product) or b = B - [(aTB)/(aTa)]a. But it can also be expressed in terms of the inner product: b = B - [⟨a, B⟩/⟨a, a⟩]a.
If there is a third term C, it must be transformed by subtracting all components of a and of b (not B!) from C. That is, c = C - [(aTC)/(aTa)]a - [(bTC)/(bTb)]b or c = C - [⟨a, C⟩/⟨a, a⟩]a - [⟨b, C⟩/⟨b, b⟩]b. And so on.
The final step is to normalize each vector by their own distance, as in â = a/||a||.
Matrices
Only a square matrix can be called orthogonal.
With that said, matrices of any size can be called orthonormal, meaning that the columns are orthonormal vectors.
Solution for Square Matrices
The Gram-Schmidt procedure can be directly applied to the columns of a square matrix. To reiterate, it does not change the column space.
Note that the procedure involves linear combinations. First, to orthogonalize a column, a combination of all preceding columns is subtracted. Second, to normalize a column, some portion of itself is taken. Therefore the diagonal will be the normalizing factors, the values above the diagonal will be the components of other columns to subtract, and everything below the diagonal will be zeros. This can be expressed as a matrix, and importantly it will be an upper triangular matrix.
Following the above notation, where a matrix has columns A, B, and C and the transformed matrix will have columns â, b̂, and ĉ:
The orthonormalized columns comprise the matrix Q. Because this matrix is orthonormal, it has useful properties like QT = Q-1.
Altogether, this is the QR decomposition and it is expressed as A = QR.