Steven M. Kay: “Modern Spectral Estimation – Theory and Applications”,p. 34 exercise 2.13

Author: Panagiotis

27 Apr

In [1, p. 34 exercise 2.13] we are asked to consider the problem of fitting the data $\left\{x[0],...,x[N-1]\right\}$ by the sum of a dc signal and a sinusoid as: $\hat{x}=\mu+A_c e^{j2\pi f_0n} \; n=0,1,...,N-1$ . The complex dc level $\mu$ and the sinusoidal amplitude $A_c$ are unknown and we are notified that we may view the determination of $\mu$ , $A_c$ as the solution of the overdetermined set of equations.

$\left[\begin{array}{cc}1 & 1 \\ 1 & e^{j2\pi f_{0}} \\ \vdots & \vdots \\ 1 & e^{j2\pi f_{0}(N-1)}\end{array} \right] \cdot \left[\begin{array}{c}\mu \\ A_{c} \end{array} \right] = \left[\begin{array}{c}x[0] \\ \vdots \\ x[N-1] \end{array} \right].$

(1)

It is asked to find the least squares solution for $\mu$ and $A_c$ . If furthermore $f_0=k/N$ , where $k$ is a nonzero integer in the range $[-N/2,N/2-1]$ for $N$ even and $[-(N-1)/2,(N-1)/2]$ for $N$ odd we are asked to determine again the least squares solution.
Solution: The least square solution of a overdetermined system $\mathbf{A}\mathbf{x}=\mathbf{b}$ is given by [1, p.30, (2.57)]:

$\mathbf{x} = (\mathbf{A}^H\mathbf{A})^{-1}\mathbf{A}^H\mathbf{b}.$

(2)

$\left[\begin{array}{c}\mu \\ A_{c} \end{array} \right]$	$=$	$\left( \left[\begin{array}{ccc} 1 & \cdots & 1 \\ 1 & \cdots & e^{-j2\pi f_{0}(N-1)}\end{array} \right] \cdot \left[\begin{array}{cc} 1 & 1 \\ 1 & e^{j2\pi f_{0}} \\ \vdots & \vdots \\ 1 & e^{j2\pi f_{0}(N-1)}\end{array} \right] \right)^{-1} \cdot$
	$\text{[math]}$	$\cdot \left[ \begin{array}{cccc} 1 & 1 & \cdots & 1 \\ 1 & e^{-j2\pi f_{0}} & \cdots & e^{-j2\pi f_{0}(N-1)} \end{array}\right] \left[ \begin{array}{c} x[0] \\ \vdots \\ x[N-1] \end{array} \right]$
	$=$	$\left[\begin{array}{cc} N & \sum\limits_{n=0}^{N-1} e^{+j2\pi f_{0} n} \\ \sum\limits_{n=0}^{N-1} e^{-j2\pi f_{0} n} & N \end{array}\right]^{-1} \cdot \left[\begin{array}{c}\sum\limits_{n=0}^{N-1} x[n] \\ \sum\limits_{n=0}^{N-1} x[n] e^{-j2\pi f_{0} n}\end{array}\right]$

The summations are equal to

$\sum\limits_{n=0}^{N-1} e^{-j2\pi f_{0} n}$	$=$	$\frac{1-e^{-j2\pi f_{0} N}}{1-e^{-j2\pi f_{0}}}$	(3)
	$=$	$\left( \frac{ e^{-j\pi f_{0} N}}{e^{-j\pi f_{0}}} \right) \frac{e^{j\pi f_{0}N}-e^{-j\pi f_{0} N}}{e^{+j\pi f_{0}}-e^{-j\pi f_{0}}}$	(4)
	$=$	$\frac{\sin(\pi f_{0} N)}{\sin(\pi f_{0})} e^{-j\pi f_{0} (N-1)}$	(5)

and

$\sum\limits_{n=0}^{N-1} e^{+j2\pi f_{0}n}$	$=$	$\frac{1-e^{j2\pi f_{0}N}}{1-e^{j2\pi f_{0}}}$	(6)
	$=$	$\left( \frac{ e^{j\pi f_{0} N}}{e^{j\pi f_{0}}} \right) \frac{e^{-j\pi f_{0}N}-e^{j\pi f_{0}N}}{e^{-j\pi f_{0}}-e^{j\pi f_{0}}}$	(7)
	$=$	$\frac{ \sin(\pi f_{0} N)}{ \sin(\pi f_{0})} e^{j \pi f_{0} (N-1)}$	(8)

as they are both geometric sums [2, p.16] of the form $S=1+a+a^2+...+a^{(N-1)}=\frac{1-a^N}{1-a}$ with $a=e^{+j2\pi f_{0} n}$ in the one case and $a=e^{-j2\pi f_{0} n}$ in the second case. The estimation of the mean and the amplitude is thus given by:

$\left[\begin{array}{c}\mu \\ A_{c} \end{array} \right]$	$=$	$\frac{1}{N^2-\left( \frac{\sin(\pi f_0N)}{\sin(\pi f_0)} \right)^2}$
	$\text{[math]}$	$\cdot \left[\begin{array}{cc} N &- \frac{\sin(\pi f_{0} N)e^{j\pi f_{0} (N-1)}}{\sin(\pi f_{0}) } \\ -\frac{\sin(\pi f_{0} N)e^{-j\pi f_{0} (N-1)}}{\sin(\pi f_{0})} & N \end{array}\right]$
	$\text{[math]}$	$\cdot \left[\begin{array}{c} \sum\limits_{n=0}^{N-1} x[n] \\ \sum\limits_{n=0}^{N-1} x[n] e^{-j2\pi f_{0} n} \end{array} \right]$	(9)

If furthermore $f_0=\frac{k}{N}$ , $k \in \mathbb{Z}$ as described in the problem statement then both sums (3), (6) are equal to zero because $a=e^{+j2\pi f_{0}N}=e^{+j2\pi k}=1=e^{-j2\pi k}=e^{-j2\pi f_{0} n}$ . In this case the least squares solution of the overdetermined system is given by:

$\left[\begin{array}{c}\mu \\ A_{c} \end{array} \right]$

$=$

$\left[\begin{array}{c}\frac{1}{N} \sum\limits_{n=0}^{N-1} x[n] \\ \frac{1}{N}\sum\limits_{n=0}^{N-1} x[n] e^{-j2\pi f_{0} n} \end{array}\right] = \left[\begin{array}{c}\frac{1}{N} \sum\limits_{n=0}^{N-1} x[n] \\ X(k) \end{array}\right].$