|
Size: 2271
Comment: Link
|
← 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 transforming a vectors into [[Calculus/UnitVector|unit vectors]]. | '''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: |
| 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. |
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 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''. 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)''. 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 final step is to normalize the orthogonal vectors by their own distance, as in ''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: |
| To re-emphasize, this is a linear combination generalized as '''''A''' = '''QR''''', and does not change the column space of '''''A'''''. | 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: |
| Note that '''''Q''''' is a [[LinearAlgebra/Orthogonality|matrix with orthonormal columns]]; it must also be square to be called an '''orthogonal matrix'''. | 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.