Projection (linear algebra)
From Free net encyclopedia
In linear algebra, a projection is a linear transformation P such that P2 = P, i.e., an idempotent transformation. A matrix is a projection if the transformation it represents is a projection. An n × n matrix projection maps an n-dimensional vector space onto a k-dimensional subspace (k ≤ n); such a matrix is also called an idempotent matrix.
For a given projection, every a in Rn can be written as the sum of a vector b in the k-dimensional subspace (the image of the projection) and a vector c in an (n − k)-dimensional subspace, the null space of the projection, i.e. Rn is the direct sum of the two. The projection maps a to b. For a suitable basis the projection is described by a diagonal matrix with k diagonal elements equal to 1 and further only zeros. Thus, for such a basis, projection applied to a linear combination of basis vectors simply corresponds to discarding n − k terms. With respect to this basis, P is represented by a diagonal matrix; all basis vectors are eigenvectors, k with eigenvalue 1 and n-k with eigenvalue 0.
Discarding the other k terms is a projection with matrix I-P giving the vector c in the (n − k)-dimensional subspace. Thus the two projections decompose the original vector into one in the image space and one in null space.
If, instead of discarding terms, we negate them, we get an involution; the eigenvectors are the same, the eigenvalues 0 are now −1. A represents an involution iff A = ±(2P − I), or equivalently P = (I ± A)/2, for a projection operator P. Thus for a given linear involution, we can decompose a vector into two projected vectors by taking the midpoint between its endpoint and its image, and taking half of the vector from the image to the original. (Similarly an affine involution is associated with an affine projection and a linear projection.)
In particular, if n is 2 or 3 and k = n − 1, we have a parallel projection of a plane to a line or of 3D space to a plane. We can distinguish oblique projections and orthogonal projections.
Note that point projection (with perspective) is not a linear transformation because it is not translation-invariant: the scale decreases with distance.
Projections (orthogonal and otherwise) play a major role in algorithms for certain linear algebra problems:
- QR decomposition (see Householder transformation and Gram-Schmidt decomposition);
- Singular value decomposition
- Reduction to Hessenberg form (the first step in many eigenvalue algorithms).
Example
Let <math>\mathbf{u}= \left(u_i\right)_{i \le k}</math> be a matrix with <math>k\le n</math> column entries <math>u_i</math>, and <math>\mathbf{v^*}= \left( v_i^* \right)_{i \le k}</math> be a matrix, its rows representing functionals <math>v_i^*</math>. Then the operator
- <math>P=\mathbf{u} \left( \mathbf{v}^* \mathbf{u} \right)^{-1} \mathbf{v}^*</math>
is a projection onto the linear span of <math>\{u_i: i \le k\}</math> with kernel <math>\{v^*_i=0: i \le k \}</math>.
Orthogonal projections
Orthogonal projections are self-adjoint projections.
One such common projection is the projection of one vector in Rn onto another. For example, we can project the vector (1/2, 1/2)T onto the vector (0, 1)T, to get the vector (0, 1/2)T. We can describe in general the projection of one vector u onto another, v by
- <math>P_{\mathbf{v}}\,\mathbf{u} = {\mathbf{v}\mathbf{\cdot}\mathbf{u}\over\mathbf{v}\mathbf{\cdot}\mathbf{v}}\mathbf{v}</math>
where the dot represents the dot product. Since an inner product generalizes the idea of a dot product, then we have the equivalent formulation for any general inner product space:
- <math>P_{\mathbf{v}}\,\mathbf{u} = {\langle \mathbf{v}, \mathbf{u}\rangle\over\langle \mathbf{v}, \mathbf{v}\rangle}\mathbf{v}</math>
where <v1,v2> represents the inner product.
This projection is indeed a projection, observe:
- <math>P_{\mathbf{w}}\,\mathbf{x}={\langle\mathbf{w},\mathbf{x}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}</math>
by definition, then
- <math>P_{\mathbf{w}}\,\left({\langle\mathbf{w},\mathbf{x}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}\right)={\langle\mathbf{w},{\langle\mathbf{w},\mathbf{x}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}={{\langle\mathbf{w},\mathbf{x}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\langle\mathbf{w},\mathbf{w}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}</math>
- <math>={\langle\mathbf{w},\mathbf{x}\rangle\over\langle\mathbf{w}, \mathbf{w}\rangle}\mathbf{w}</math>
This projection is linear:
- <math>P_{\mathbf{w}}\,({\alpha\mathbf{a}+\beta\mathbf{b}})
={\langle\mathbf{w},\alpha\mathbf{a}+\beta\mathbf{b}\rangle\over\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w} ={\langle\mathbf{w},\alpha\mathbf{a}\rangle\over\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w}+{\langle\mathbf{w},\beta\mathbf{b}\rangle\over\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w}</math>
- <math>=\alpha{\langle\mathbf{w},\mathbf{a}\rangle\over\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w}+\beta{\langle\mathbf{w},\mathbf{b}\rangle\over\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w}
=\alpha\,P_{\mathbf{w}}\,\mathbf{a}+\beta\,P_{\mathbf{w}}\,\mathbf{b}</math>.
This means that projection onto <math>\mathbf{v}</math> can be represented as a matrix. With the standard inner product in Rn, this is
- <math>P_{\mathbf{v}} = \mathbf{v} (\mathbf{v}^T \mathbf{v})^{-1} \mathbf{v}^T.</math>
This construction generalizes to projection onto subspaces. That is,
- <math>P_{\mathbf{A}} = \mathbf{A} (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T.</math>
gives the orthogonal projection of a vector onto the space spanned by the columns of the matrix A.