|
Size: 2017
Comment: Moving vector pages
|
← Revision 12 as of 2026-02-04 02:17:02 ⇥
Size: 3459
Comment: Rewrite
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| '''Gram-Schmidt orthonormalization''' is a process for making vectors into orthonormal vectors. It is generalized as '''''A''' = '''QR'''''. | '''Gram-Schmidt orthonormalization''' is a process for transforming a set of vectors (or a matrix) into [[LinearAlgebra/Orthogonality|orthogonal]] [[Calculus/UnitVector|unit vectors]]. |
| Line 11: | Line 11: |
| == Vectors == | == Description == |
| Line 13: | Line 13: |
| [[LinearAlgebra/Orthogonality|Orthogonality]] is fundamentally about the relation between two vectors. So as the first point of reference, ''a'' needs no transformation. It is automatically denoted as the orthogonal vector ''A''. | To '''orthonormalize''' a set of vectors is to... 1. make them [[LinearAlgebra/Orthogonality|orthogonal]] to each other, then 2. normalize them to a unit [[Calculus/Distance|distance]] of 1. |
| Line 15: | Line 17: |
| The process of transforming vector ''b'' into orthogonal vector ''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/Projections#Vectors|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)''. 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)''. The orthogonal vectors are then normalized by scaling to their [[Calculus/Distance#Euclidean_distance|Euclidean distances]], as ''A/||A||'' and ''B/||B||''. |
Note that orthogonality is a property of two vectors, not one. No process is needed to 'orthogonalize' a single vector. |
| Line 29: | Line 23: |
| == Matrices == | == Process == |
| Line 31: | Line 25: |
| 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,,||''. | === Solution === |
| Line 33: | Line 27: |
| Note that '''''Q''''' is a [[LinearAlgebra/Orthogonality#Matrices|matrix with orthonormal columns]], not necessarily an '''orthogonal matrix'''. | Consider two vectors, ''A'' and ''B''. They will be made [[Calculus/Orthogonality|orthogonal]] to each other and become ''a'' and ''b''. Then they will be normalized and become ''â'' and ''b̂''. |
| Line 35: | Line 29: |
| To re-emphasize, this is a linear combination and does not change the column space. | The '''Gram-Schmidt procedure''' does this using linear combinations, so does not change the subspace spanned by ''A'' and ''B''. Put another way, if ''A'' and ''B'' are a [[LinearAlgebra/Basis|basis]] for some subspace, then ''â'' and ''b̂'' will be a basis for the exact same subspace. But they will be orthonormal, so certain operations will be simpler. First, recall 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||''. === QR Decomposition === To reiterate, the Gram-Schmidt procedure uses linear combinations. It can therefore be represented with matrices. 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, in the matrix representing this procedure... * the numbers on the diagonal are normalizing factors; how much of the same column to take. * the numbers above the diagonal are how much of each preceding column to take away. * the numbers below the diagonal are all zeros. Note furthermore that this is 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 set of vectors (or a matrix) into orthogonal unit vectors.
Description
To orthonormalize a set of vectors is to...
make them orthogonal to each other, then
normalize them to a unit distance of 1.
Note that orthogonality is a property of two vectors, not one. No process is needed to 'orthogonalize' a single vector.
Process
Solution
Consider two vectors, A and B. They will be made orthogonal to each other and become a and b. Then they will be normalized and become â and b̂.
The Gram-Schmidt procedure does this using linear combinations, so does not change the subspace spanned by A and B. Put another way, if A and B are a basis for some subspace, then â and b̂ will be a basis for the exact same subspace. But they will be orthonormal, so certain operations will be simpler.
First, recall 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||.
QR Decomposition
To reiterate, the Gram-Schmidt procedure uses linear combinations. It can therefore be represented with matrices. 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, in the matrix representing this procedure...
- the numbers on the diagonal are normalizing factors; how much of the same column to take.
- the numbers above the diagonal are how much of each preceding column to take away.
- the numbers below the diagonal are all zeros.
Note furthermore that this is 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.