<< Chapter < Page | Chapter >> Page > |
Recall that a set $S$ is a basis for a subspace $X$ if $\left[S\right]=X$ and $S$ has linearly independent elements. If $S$ is a basis for $X$ then each $x\in X$ is uniquely determined by $({a}_{1},{a}_{2},...,{a}_{n})$ such that ${\sum}_{i=1}^{n}{a}_{i}{s}_{i}=x$ . In this sense, we could operate either with $x$ itself or with the vector $a=[{a}_{1},...{a}_{n}]={R}^{n}$ . One would wonder then whether particular operations can be performed with a representation $a$ instead of the original vector $x$ .
Example 1 Assume $x,y\in X$ have representations $a,b\in {R}^{n}$ in a basis for $X$ . Can we say that $\u2329x,,,y\u232a=\u2329a,,,b\u232a$ ?
For the particular example of $X={L}_{2}[0,1]$ , $S=\{1,t,{t}^{2}\}$ so that $\left[S\right]=Q$ , the set of all quadratic functions supported on $[0,1]$ . Pick $x=2+t+{t}^{2}$ and $y=1+2t+3{t}^{2}$ . One can see then that if we label ${s}_{1}=1$ , ${s}_{2}=t$ , ${s}_{3}={t}^{2}$ , then the coefficient vectors for $x$ and $y$ are $a=\left[2\phantom{\rule{3.33333pt}{0ex}}1\phantom{\rule{3.33333pt}{0ex}}1\right]$ and $b=\left[1\phantom{\rule{3.33333pt}{0ex}}2\phantom{\rule{3.33333pt}{0ex}}3\right]$ , respectively. Let us compute both inner products:
Since $7\ne 9.35$ , we find that we fail to obtain the desired equivalence between vectors and their representations.
While this example was unsuccessful, simple conditions on the basis $S$ will yield this desired equivalence, plus many more useful properties.
Several definitions of orthogonality will be useful to us during the course.
Definition 1 A pair of vectors $x$ and $y$ in an inner product space are orthogonal (denoted $x\perp y$ ) if the inner product $\u2329x,,,y\u232a=0$ .
Note that 0 is immediately orthogonal to all vectors.
Definition 2 Let $X$ be an inner product space. A set of vectors $S\subseteq X$ is orthogonal if $\u2329x,,,y\u232a=0$ for all $x,y\in S,x\ne y$ .
Definition 3 Let $X$ be an inner product space. A set of vectors $S\subseteq X$ is orthonormal if $S$ is an orthogonal set and $\parallel s\parallel =\sqrt{\u27e8s,s\u27e9}=1$ for all $s\in S$ .
Definition 4 A vector $x$ in an inner product space $X$ is orthogonal to a set $S\subseteq X$ (denoted $x\perp S$ ) if $x\perp y$ for all $y\in S$ .
Definition 5 Let $X$ be an inner product space. Two sets ${S}_{1}\subseteq X$ and ${S}_{2}\subseteq X$ are orthogonal (denoted ${S}_{1}\perp {S}_{2}$ ) if $x\perp y$ for all $x\in {S}_{1}$ and $y\in {s}_{2}$ .
Definition 6 The orthogonal complement ${S}^{\perp}$ of a set $S$ is the set of all vectors that are orthogonal to $S$ .
Why is orthonormality good? For many reasons. One of them is the equivalence of inner products that we desired in a previous example. Another is that having an orthonormal basis allows us to easily find the coefficients ${a}_{1},...{a}_{n}$ of $x$ in a basis $S$ .
Example 2 Let $x\in X$ and $S$ be a basis for $X$ (i.e., $\left[S\right]=X$ ). We wish to find ${a}_{1},...{a}_{n}$ such that $x={\sum}_{i=1}^{n}{a}_{i}{s}_{i}$ . Consider the inner products
due to the linearity of the inner product in the first term. If $S$ is orthonormal, then we have that for $i\ne j$ $\u3008{s}_{j},,,{s}_{i}\u3009=0$ . In that case the sum above becomes
due to the orthonormality of $S$ . In other words, for an orthonormal basis $S$ one can find the basis coefficients as ${a}_{i}=\u27e8x,{s}_{i}\u27e9$ .
If $S$ is not orthonormal, then we can rewrite the sum above as the product of a row vector and a column vector as follows:
We can then stack these equations for $i=1,...,n$ to obtain the following matrix-vector multiplication:
The nomenclature given above provides us with the matrix equation $\beta =G\xb7a$ , where $\beta $ and $G$ have entries ${\beta}_{i}=\u2329x,,,{s}_{i}\u232a$ and ${G}_{i,j}=\u2329{s}_{j},,,{s}_{i}\u232a$ , respectively.
Definition 7 The matrix $G$ above is called the Gram matrix (or Gramian) of the set $S$ .
In the particular case of orthonormal $S$ , it is easy to see that $G=I$ , the identity matrix, and so $a=\beta $ as given earlier. For invertible Gramians $G$ , one could compute the coefficients in vector form as $a={G}^{-1}\beta $ . For square matrices (like $G$ ), invertibility is linked to singularity.
Definition 8 A singular matrix is a non-invertible square matrix. A non-singular matrix is an invertible square matrix.
Theorem 1 A matrix is singular if $G\xb7x=0$ for some $x\ne 0$ . A matrix is non-singular if $G\xb7x=0$ only for $x=0$ .
The link between this notion of singularity and invertibility is straightforward: if $G$ is singular, then there is some $a\ne 0$ for which $G\xb7a=0$ . Consider the mapping $y=G\xb7x$ ; we would also have $y=G(x+a)$ . Since $x\ne x+a$ , one cannot “invert” the mapping provided by $G$ into $y$ .
Theorem 2 $S$ is linearly independent if and only if $G$ is non-singular (i.e. $Gx=0$ if and only if $x=0$ ).
Proof: We will prove an equivalent statement: $S$ is linearly dependent if and only if $G$ is singular, i.e., if and only if there exists a vector $x\ne 0$ such that $Gx=0$ .
$(\Rightarrow )$ We first prove that if $S$ is linearly dependent then $G$ is singular. In this case there exist a set $\left\{{a}_{i}\right\}\subseteq R$ , with at least one nonzero, such that ${\sum}_{i=1}^{n}{a}_{i}{s}_{i}=0$ . We then can write $\u2329{\sum}_{i=1}^{n},{a}_{i},{s}_{i},,,{s}_{j}\u232a=\u27e80,{s}_{j}\u27e9=0$ for each ${s}_{j}$ . Linearity allows us to take the sum and the scalar outside the inner product:
We can rewrite this equation in terms of the entries of the Gram matrix as ${\sum}_{i=1}^{n}{a}_{i}{G}_{ji}=0$ . This sum, in turn, can be written as the vector inner product
which is true for every value of $j$ . We can therefore collect these equations into a matrix-vector product:
Therefore we have found a nonzero vector $a$ for which $Ga=0$ , and therefore $G$ is singular. Since all statements here are equalities, we can backtrack to prove the opposite direction of the theorem $(\Leftarrow )$ .
There are still more nice proper ties for orthogonal sets of vectors. The next one has well-known geometric applications.
Theorem 3 (Pythagorean theorem) If $x$ and $y$ are orthogonal ( $x\perp y$ ), then ${\parallel x\parallel}^{2}+{\parallel y\parallel}^{2}={\parallel x+y\parallel}^{2}$ .
Proof:
Because $x$ and $y$ are orthogonal, $\u27e8x,y\u27e9=\u27e8y,x\u27e9=0$ and we are left with $\u27e8x,x\u27e9={\parallel x\parallel}^{2}$ and $\u27e8y,y\u27e9={\parallel y\parallel}^{2}$ . Thus: ${\parallel x+y\parallel}^{2}={\parallel x\parallel}^{2}+{\parallel y\parallel}^{2}.$
Notification Switch
Would you like to follow the 'Introduction to compressive sensing' conversation and receive update notifications?