1.11 Least squares estimation in hilbert spaces  (Page 2/2)

The coefficients of the best approximation can then be obtained as a vector $a=G^{-1}\beta$ , as long as the Gram matrix $G$ is invertible, i.e., it has a nonzero determinant.

In the case that $x$ and $y_i$ are complex-valued vectors, one can rewrite the approximation ${\sum }_{i=1}^n{a}_i{y}_i=Ya$ , where $a$ is the coefficient vector denoted above and $Y=[y_1...y_n]$ is a matrix that collects the vectors $y_i$ as its columns. The projection theorem requirement then becomes $⟨x-Ma,y_j⟩=0$ for $j=1...,n$ , which can be rewritten as $y_j^H(x-Ma)=0$ and collected as before into the matrix equation

which is known as the least squares solution and exists as long as $M^{H}M$ is an invertible matrix. Once these coefficients are obtained, the approximation is equal to $\widehat{x}=Ma=M{\left(M^{H}M\right)}^{-1}{M}^{H}x$ ; therefore, the matrix $P_M=M{\left(M^{H}M\right)}^{-1}{M}^H$ is known as the projection operator.

Application: channel equalization

We consider a linear channel with impulse response $h$ that maps an input $x$ into an output $y$ :

We wish to design a linear equalizer of impulse response $g$ for the input $x$ so that after it is run through the equalizer and the channel of impulse response $h$ the output $f\approx x$ (i.e., $f$ is as close as possible to $x$ ):

Since the equalizer is linear, the order of $g$ and $h$ can be reversed (this will be discussed in more detail later):

Our design for $g$ will be a finite impulse response filter with tap coefficients $g_i$ ; the mapping from input to output index $n$ is therefore given by

The error in approximating $x_n$ is given by

The total error magnitude over $N$ observations is given by

We want to pose this question in terms of error of approximation into a subspace:

By convention, we assume that the values $g_n=0$ and $x_n=0$ for $n<0$ (i.e., $n=0$ is the time of the first observation). It can be easily seen that

formulating $M$ requires a separate study of the sum in [link] for each value of $n$ . For $n=0$ ,

and so terms $n\le 0$ can be ignored. For $n=1$ ,

Similarly, for $n=2$ ,

Continuing until $n=N$ ,

The concatenation of these sums as a vector can then be expressed by the matrix-vector product $Mg$ , where the matrix $M$ is given by

Note that for $M$ to have linearly independent columns (a condition for uniqueness of the solution to $g$ ) the number of nonzero values of $y_i$ must be at least $k$ . In this case, the solution

minimizes the error as established in the Projection Theorem.

Application: linear regression

In linear regression, we are given a set of input/output pairs $(x_i,y_i)$ , $i=1,...,N$ , and we wish to find a linear relationship between inputs and outputs $y_i=a{x}_i+b$ that minimize the sum of squared errors $E={\sum }_{i=1}^N(y_i-{(a{x}_i+b)}^2)$ . As in previous examples, we seek to pose this minimization problem in terms of the problem considered by the projection theorem: the error $E={\parallel Mg-y\parallel }_2^2$ , where $M$ is a matrix, $y$ is a vector, and $g$ is the optimization variable vector. One can easily see that the following choice achieves the desired equality:

As before, the solution that minimizes the error is given by

which exists and is unique as long as $G=M^{T}M$ is invertible, i.e., as long as $M$ has linearly independent columns, i.e., as long as not all $x_i$ are equal. Now, we see that

Collecting these results, we have that

Least squares: rejoinder

We have studied several examples where an optimization problem can be formulated as

where $M$ is a matrix and $b$ and $g$ are column vectors of appropriate sizes.

• When the columns of $M$ are orthonormal (i.e., orthogonal and unit norm), we compute $\widehat{g}=M^{H}b$ , i.e., ${\widehat{g}}_i=⟨M_i,b⟩$ , where ${\widehat{g}}_i$ is the $i^{th}$ entry of $g$ and $M_i$ is the $i^{th}$ column of $M$ .
• When the columns of $M$ are linearly independent, we compute $\widehat{g}=M^{†}b={\left(M^{H}M\right)}^{-1}{M}^{H}b$ . The Moore-Penrose pseudoinverse $M^{†}={\left(M^{H}M\right)}^{-1}{M}^H$ is well defined because the Gram matrix $G=M^{H}M$ of a linearly independent set is invertible.
• When the columns of $M$ are linearly dependent, there exists a vector $a\ne 0$ such that $Ma=0$ . Thus, if a solution $g_0$ to the optimization exists, then $g_0+a$ is also a solution: note that $\parallel M{g}_0-b\parallel =\parallel M(g_0+a)-b\parallel$ , and so we lose uniqueness of the minimizer; in fact, we will have infinitely many solutions to the minimization. However, there are ways to rank the solutions and pick a "favorite", e.g., the solution with the smallest norm. This will be considered later in the course.