Lecture 5
Complex and Spectrum matrices
Definition: Sampling Periodic Functions
Given a function of period, T, i.e
choose N and samplex(t) within the interval, 0tT, at N equally spaced points, n, where n = 0,1,...,N−1 and = T/N. The result is a discrete function of period, N, which can be represented as a vector, , in (or) where :
5.1 Complex Matrices
- Inner Product of Discrete Periodic Functions
The Euclidean inner product of two discrete functions and of period N as follows:
The associated norm is
- Hermitian Matrices
If A is real matrix and symmetric then A=AT. But if the matrix A is complex and symmetric then this formula must be extended to be . Any matrix that equal their conjugate transpose is called Hermitian matrix.
Hemitian Matrix, A=
Example: A=
Properties of Hermitian Matrices:
1-The diagonal entries must be real; they are unchanged by conjugation.
2-A real symmetric matrix is certainly Hermitian. (For real matrices there is no difference between AT and AH).
3-The eigenvalues of A are real.
4-Two eigenvectors of a real symmetric matrix or a Hermitian matrix, if they come from different eigenvalues, are orthogonal to one another.
Example: the eigenvalues and the corresponding eigenvectors of
A= are
The eigenvalues are and
For ,
For ,
These two eigenvectors are orthogonal:
- Unitary Matrices
A Hermitian (or symmetric) matrix can be compared to a real number. A unitary (or orthogonal) matrix can be compared to a number on theunit circle—a complex number of absolute value 1. The eigenvalues are real if AH = A, and they are on the unit circle if UHU = I. The eigenvectors can be scaled to unit length and made orthonormal.
properties of Unitary matrix:
1-Multiplication by U has no effect on inner products, angles, or lengths.
and lengths are preserved by U:
Length unchanged
2-Every eigenvalue of U has absolute value .
This follows directly from by comparing the lengths of the two sides: by Property 1, and always. Therefore .
3-Eigenvectors corresponding to different eigenvalues are orthonormal.
Example:has eigenvalues eit and e-it
The orthogonal eigenvectors are (Remember to take conjugates in xHy = 1+i2 = 0) After division by they areorthonormal
Example: show that is unitary matrix
- Real versus Complex:
5.2 Discrete Fourier Transform (DFT)
The formulas for the DFT and IDFT are expressed as
where, by definition,
Forapositive integer N, the complex numbers are called the N-th roots of unity because they represent all solutions to zN =1. Geometrically, they are the vertices of a regular polygon of N sides as depicted in Figure below for N=4 and N=8. They are listed in clockwise order around the unit
The roots of unity are cyclic in the sense that if kN, then
where denotes the remainder where k is divided by N. For example, when N=4, and so on
The following identities will be useful in our development. If k is an integer, then
.
Furthermore, the fact that
Let us define an N-point vector of the signal sequence x(n), n = 0, 1, ... , N - 1, an N -point vector of frequency samples, and an N N matrix as
,
Where is called the Fourier matrix of order N.
With these definitions, the N -point DFTmay be expressed in matrix form as
Similarly for IDFT
where denotes the complex conjugate of the matrix FN.
Properties of Fourier matrix:
1-FN are mutually orthogonal
The inner product of any two columns in FN, say the rth and sth, is
Therefore the columns in FN are mutually orthogonal.
2- is a unitary matrix
Each column in FN has norm because
and consequently every column of FN can be normalized by multiplying by the same scalar—namely,1/. This means that (1/)FN is a unitary matrix. Since it is also true that, we have
Note: any matrix A is called unitary matrixIf (A*)TA=I
and therefore
Example: The Fourier matrices of orders 2 and 4 are given by
and
and there inverses are
and
HW: determine the Fourier matrix of order 8 and 16.
Definition (Discrete Fourier Transform): Thechangeofcoordinatesfrom the standard basis of to the Fourier basisFN is called the discrete Fourier transform (DFT). The NN matrix FN thatrepresentsthischangeofbasis is called the (N-point) Fourier matrix. If is a vector in, its coordinates =( X0,X1,...,XN−1) relative to the Fourier basis are called the Fourier coefficients of , in other words = FN.
Example:Compute the DFT of the four-point sequence
Example:for the signal given by x(t) = 3cos2t +5sin2t , with T=1 and N=4. Find and plot the magnitude and phase spectrum of x(t) using DFT. Also plot the real and imaginary of the spectrum.
Solution:
The four values of x(t) is
The DFT of is calculated as
HW: If possible, diagonalize the Fourier matrix of order 4 with a similarity transformation:
HW: By means of the DFT and IDFT, determine the response of the FIR filter with impulse response = (1, 2, 3)T to the input vector
= (1, 2, 2, 1)T
MATLAB: X = fft(x) returns the discrete Fourier transform (DFT) of vector x, computed with a fast Fourier transform (FFT) algorithm. See also ifft, fft2,ifft2.
5.3 Fast Fourier Transform (FFT)
Example: Draw the signal flow graph of the 4-point decimation in time FFT then derive the FFT matrix decomposition.
;
;
The factorization of F4 is
, ,
In general,
Or,
Example: Draw the signal flow graph of the 8-point decimation in time FFT then derive the FFT matrix decomposition.
HW : Draw the signal flow graph of the 16-point decimation in time FFT then derive the FFT matrix factorizing.
5.4 Discrete Convolution
The output response of the LTI system as a function of the input signal x(n) and the impulse response h(n) can be expressed as
- Convolution as Matrix Multiplication
Let us define an N-point vector of the signal sequence x(n), n = 1, ... , M– 1 that represent input to the system with impulse response ofN-point vector (FIR filter) of the signal sequence h(n), n=0,1,..,N-1, and an (N+M-1)Mmatrix as
,
Where is called the convolution matrix of size (N+M-1).
With these definitions, the output response vector may be expressed in matrix form as:
Example: Findby using a matrix multiplication?
Solution:The convolution matrix,
H=
The output response ,
MATLAB: y= conv(x, h) convolves vectors x and h.
5.5Autocorrelation matrix
It is used in various digital signal processing algorithms for example in linear prediction problem. Define R(k) to be the autocorrelation sequence of the signal x(n), that is:
Where .
Using the fact that R(k)=R* (−k), the N×Nautocorrelationmatrix,RN, is written as
For example, with N = 3, we get
Properties of RN:
1-RN is Hermitian symmetric, which means that
We will see that this means that the eigenvalues of RN are real and the eigenvectorscorresponding to distinct eigenvalues areorthogonal.If RNis real, then RNis symmetric:
2-is a Toeplitz matrix, which means that is constant along the diagonals. If, denotes the i, jth element of , then
which is to say, the element of depends only on the difference between the indexvalues. This Toeplitz structure of leads to efficient algorithms forsolving equations similar to the Yule-Walker equations (Levinson’s recursion).
Hint:Toeplitz matrix or diagonal-constant matrix, a matrix is called Toeplitz matrix if the entries are constant along each diagonal such that.
3-Diagonal elements. The quantity (0) appears on all the diagonalelements and isthe mean squarevalueof the randomprocess,that is,
- Estimating the Autocorrelation
The autocorrelation method. In this method, we define the truncated version of measured data
Andcompute itsdeterministicautocorrelation.Thus, the estimateofRN(k) hasthe form
A simple matrix interpretation of the estimation of RN is useful. For example, if we have L = 5 and wish to estimate the 3×3 autocorrelation matrix R3, the data matrix is defined as
And forming the estimateof R3 using
where represents the conjugate transpose operation.
Example: assuming the data samples x(n)=[1 0.299 -0.08 0.03 0.186]T to find the autocorrelation matrix R3 ,firstly find the data matrix
Then
Example: Diagonalize the following correlation matrix
The characteristic equation is
The eigenvalues are (0,1,2) and the corresponding the eigenvectors are
and
1