Starting from:
$30
236200 Homework 3 - k-term solved
On Circulant Matrices
0
1
a. Consider the matrix J = 0
...
0 In particular, what is Jn?
...
0
1
...
...
...
...
0
...
0
0
...
...
...
1
1
0
∈ R ×n. For k ∈ N, compute Jk.
0 n
...
0
b. Compute the eigenvalues of J.
c. Do the full eigendecomposition of J. Is J diagonalisable? If yes, can it be diagonalised in a unitary basis?
h0
h1
d. Consider the general circulant matrix H = h2
...
hn−1
hn−1 h0 h1
...
hn−2
hn−2 hn−1 h0
...
hn−3
...
...
...
...
...
h1 h2 h3. Show
...
h0
that H and J are linked by a polynomial expression, i.e. find a polynomial P such that H = P(J).
e. Compute the full eigendecomposition of H. Is it diagonalisable and if so is it in a unitary basis?
f. Show that the diagonalisation basis matrix B can be chosen as the DFT∗ matrix.
g. Prove that the eigenvalues, stacked in a column, equals to the product of B and the first row of H rewritten in column form, i.e. if λ0,...,λn−1 are the eigenvalues of H then:
.
h. Consider two circulant matrices H1 and H2. Show that they commute. Compute H1H2, is this matrix circulant?
i. Compute DFTk for k ∈ N. What are the resulting matrices?
j. Prove that a convolution of n-dimensional signals can be computed by point-wise multiplication of the signals in the Fourier domain. This means prove that if z = x⊗y where ⊗ the convolution operator, then ( where is the Hadamard product.
2. Convolutional Neural Networks (CNN)
In this exercise we will set ourselves in the trendy context of Convolutional Neural networks. The input signals are typically 2D images but are reshaped as a 1D vector. The layers of the network can be seen as successive operators applied to the input. We want to study some basic properties, seen from the perspective of the class, of these transforms. Please provide appropriate mathematical justifications for all your claims.
a. Consider a convolution operator, also known as layer, C1. Is this layer linear? Is it shift-invariant?
b. Assume layer C1 is followed by another convolutional layer C2. Is the operator C1,2 = C2 ◦ C1 defined as the composition of the two convolutional layers linear? Is it shift-invariant?
c. Show that the result of a succession of any number of convolutional layers is equivalentto the result of a single convolutional layer.
d. We now wish to introduce a non linear layer to the network. Consider the relu operator. This operator applies for each entry of its input signal x the new entry x+ = max{x,0} of the its output signal. Is this layer linear? Is it shift invariant? Is the current network (the successive convolutions and relu layers) linear? Is it shift-invariant?
e. We now add to the architecture of the network successive alternations of convolutionallayers and relu layers. The network provides a deep vector, also called embedding, on the input signal to the network. The embedding is to be used for various purposes, such as providing as low dimensional compact and informative representation of the signal that is appropriate for classification. Is the embedding a linear transform of the input signal? Is it shift-invariant with respect to the input signal?
3. Optimal Basis for Smooth Signals
Complete the proof of Theorem 3 (Optimal Basis for Smooth Signals) by showing the uniqueness of the Fourier basis for the case of a simple spectrum with:
0 < λ1 < λ2 < λ3 < ...
Your proof should rely on Poincar`e’s “magic trick” that appears also in the uniqueness proof given in the following paper for a general spectrum: Haim Brezis and David GomezCastro, ”Rigidity of optimal bases for signal spaces”, Comptes Rendus Mathematique 355.7 (2017): 780-785.
Your proof should be a simplified version of the proof in the above paper, as we consider here the simple spectrum defined above (and in the lecture notes).
4. Fourier Transform
a. Given two functions f(t) and g(t) and denote the convolution of the two functions by h(t), that is
f(t) ∗ g(t) = h(t) (1)
What is f(t − 1) ∗ g(t + 1) in terms of h(t)?
b. Given two functions f(t) and g(t), show that the following condition holds
(2)
where F(u) and G(u) are the Fourier transform of f(t) and g(t) respectively.
Hint: you should represent the function by convolution and apply the convolution theorem in Fourier domain. Note that the inverse Fourier transform should be taken into accounts.
c. Using the results from the previous question. Given two functions f(t) and g(t), show that the following condition holds
(3)
d. Compute the following integral
(4)
Hint: the continuous Fourier transform of the normalized sinc(t) (to ordinary frequency) is rect(u),
II Matlab
The purpose of this exercise is to get familiar with the concept of functional maps. We will transform images/signal in some ways and consider these transforms as the result of remapping the image after some changes in the parametrisation. In class, you saw that when the transform is known then the link between the coefficients of orthonormal basis in the first image/signal and in the second image/signal are linked by a linear transform, i.e. a matrix called the functional map. However, here we do not provide you with the corresponding transform but you can still recover approximately the functional map.
Instruction:
• Figures should be titled in a appropriate font size.
• Submit the code and a report describing the results and your understanding of the exercise.
• Note that the additional image files and audio files provided in the course website with this homework assignment.
• It is recommended to normalize the graylevels to the range [0,1] after loading the images.
1. Image example
Consider the mandril image and its distorted version. The distortion was found by applying a transform of the x parameter space, by squeezing and strecthing the x axis. Here, we consider one signal as a row of the image. Thus each row of the original image has been squeezed and stretched in the same way, giving the rows of the distorted image.
The basis of interest, both in the original image domain and in the distorted image domain is the DFT matrix basis. The DFT has as many columns (and rows) than the signals have entries, i.e. as many columns as the images.
a. Compute the DFT representation coefficients for each row signal in the original anddistorted image. Denote αr,i (resp. βr,i) the i-th coefficient of the r-th row in the original (resp. distorted) image. As usual with the DFT, we start indexing at 0 (be careful in your matlab implementations as indexing starts at 1 in this programming language).
b. Denote, using the notations in the lecture, eci,j the i,j-th coefficient of the functional map C. Recall that then βr,j = Pαr,keck,j. We can rewrite this in a more compact
i
matrix formulation for each row r as ber = arC, where ar (resp. ber) is the representation row of coefficients of the r-th row of the original (resp. distorted) row in the DFT basis. We can stack this matrix formulation into an even more compact formulation by writing Be = AC where the r-th row of A (resp. Be) is ar (resp. ber). When the transform mapping is known, C can be explicitly computed. Unfortunately, it is here considered as unknown and slight errors may exist leading to noise effects. Thus stacking each row allows to improve the stability of the recovered functional map. We wish to compute empirically C using a least squares approach. That is compute
Cb such that Cb ∈ argmin . Least squares is a well-known problem and it
C
can be solved, with some assumptions on the rank of A with pseudo inversion. Show that the matrix A is full rank, and so computing the pseudo inverse is legal. If it is not full rank remove redundant columns from the problem until you get a full rank matrix. Find then Cb. You might want to consider using the matlab built-in function pinv for pseudo inversion.
c. Distort the original image rows using your approximation of the functional map Cb. Note that you must go into the DFT domain to do your calculations and back to the normal domain to display an image understandable for a human being. Compare your result with the given distorted image.
d. Distort the ‘butterfly’ image by distorting its rows using Cb.
2. Audio example
Consider two audio signals (skycastle.wav and skycastle-distortion.wav) note that skycastledistortion signal is the distortional signal of skycastle. Assume that the period of the distortion is known and it is 512 in entry unit.
Utilizing the same approach as with the image case, estimate an approximate functional map between the clean signal and the noisy signal. Use the DFT basis for the basis functions. (Hint: Note that the distortion is independent from the true signal and it is periodic, then the transformation can be done periodically as well. You might want to divide your signal into successive non overlapping small signals.) Use the matrices to denoise the other audio signal (totoro-distortion.wav). Compare the obtained result with the corresponding true audio signal (totoro.wav) by graph. What is the MSE error?
To read the audiofiles you can use the audioread function. To run a vector in audio (i.e. send it to your speakers and hear your signal), you can use the sound function. For these audio signals, set the sample frequency to be Fs = 48000 when sounding them (since it is the sampling frequency).
0
1
a. Consider the matrix J = 0
...
0 In particular, what is Jn?
...
0
1
...
...
...
...
0
...
0
0
...
...
...
1
1
0
∈ R ×n. For k ∈ N, compute Jk.
0 n
...
0
b. Compute the eigenvalues of J.
c. Do the full eigendecomposition of J. Is J diagonalisable? If yes, can it be diagonalised in a unitary basis?
h0
h1
d. Consider the general circulant matrix H = h2
...
hn−1
hn−1 h0 h1
...
hn−2
hn−2 hn−1 h0
...
hn−3
...
...
...
...
...
h1 h2 h3. Show
...
h0
that H and J are linked by a polynomial expression, i.e. find a polynomial P such that H = P(J).
e. Compute the full eigendecomposition of H. Is it diagonalisable and if so is it in a unitary basis?
f. Show that the diagonalisation basis matrix B can be chosen as the DFT∗ matrix.
g. Prove that the eigenvalues, stacked in a column, equals to the product of B and the first row of H rewritten in column form, i.e. if λ0,...,λn−1 are the eigenvalues of H then:
.
h. Consider two circulant matrices H1 and H2. Show that they commute. Compute H1H2, is this matrix circulant?
i. Compute DFTk for k ∈ N. What are the resulting matrices?
j. Prove that a convolution of n-dimensional signals can be computed by point-wise multiplication of the signals in the Fourier domain. This means prove that if z = x⊗y where ⊗ the convolution operator, then ( where is the Hadamard product.
2. Convolutional Neural Networks (CNN)
In this exercise we will set ourselves in the trendy context of Convolutional Neural networks. The input signals are typically 2D images but are reshaped as a 1D vector. The layers of the network can be seen as successive operators applied to the input. We want to study some basic properties, seen from the perspective of the class, of these transforms. Please provide appropriate mathematical justifications for all your claims.
a. Consider a convolution operator, also known as layer, C1. Is this layer linear? Is it shift-invariant?
b. Assume layer C1 is followed by another convolutional layer C2. Is the operator C1,2 = C2 ◦ C1 defined as the composition of the two convolutional layers linear? Is it shift-invariant?
c. Show that the result of a succession of any number of convolutional layers is equivalentto the result of a single convolutional layer.
d. We now wish to introduce a non linear layer to the network. Consider the relu operator. This operator applies for each entry of its input signal x the new entry x+ = max{x,0} of the its output signal. Is this layer linear? Is it shift invariant? Is the current network (the successive convolutions and relu layers) linear? Is it shift-invariant?
e. We now add to the architecture of the network successive alternations of convolutionallayers and relu layers. The network provides a deep vector, also called embedding, on the input signal to the network. The embedding is to be used for various purposes, such as providing as low dimensional compact and informative representation of the signal that is appropriate for classification. Is the embedding a linear transform of the input signal? Is it shift-invariant with respect to the input signal?
3. Optimal Basis for Smooth Signals
Complete the proof of Theorem 3 (Optimal Basis for Smooth Signals) by showing the uniqueness of the Fourier basis for the case of a simple spectrum with:
0 < λ1 < λ2 < λ3 < ...
Your proof should rely on Poincar`e’s “magic trick” that appears also in the uniqueness proof given in the following paper for a general spectrum: Haim Brezis and David GomezCastro, ”Rigidity of optimal bases for signal spaces”, Comptes Rendus Mathematique 355.7 (2017): 780-785.
Your proof should be a simplified version of the proof in the above paper, as we consider here the simple spectrum defined above (and in the lecture notes).
4. Fourier Transform
a. Given two functions f(t) and g(t) and denote the convolution of the two functions by h(t), that is
f(t) ∗ g(t) = h(t) (1)
What is f(t − 1) ∗ g(t + 1) in terms of h(t)?
b. Given two functions f(t) and g(t), show that the following condition holds
(2)
where F(u) and G(u) are the Fourier transform of f(t) and g(t) respectively.
Hint: you should represent the function by convolution and apply the convolution theorem in Fourier domain. Note that the inverse Fourier transform should be taken into accounts.
c. Using the results from the previous question. Given two functions f(t) and g(t), show that the following condition holds
(3)
d. Compute the following integral
(4)
Hint: the continuous Fourier transform of the normalized sinc(t) (to ordinary frequency) is rect(u),
II Matlab
The purpose of this exercise is to get familiar with the concept of functional maps. We will transform images/signal in some ways and consider these transforms as the result of remapping the image after some changes in the parametrisation. In class, you saw that when the transform is known then the link between the coefficients of orthonormal basis in the first image/signal and in the second image/signal are linked by a linear transform, i.e. a matrix called the functional map. However, here we do not provide you with the corresponding transform but you can still recover approximately the functional map.
Instruction:
• Figures should be titled in a appropriate font size.
• Submit the code and a report describing the results and your understanding of the exercise.
• Note that the additional image files and audio files provided in the course website with this homework assignment.
• It is recommended to normalize the graylevels to the range [0,1] after loading the images.
1. Image example
Consider the mandril image and its distorted version. The distortion was found by applying a transform of the x parameter space, by squeezing and strecthing the x axis. Here, we consider one signal as a row of the image. Thus each row of the original image has been squeezed and stretched in the same way, giving the rows of the distorted image.
The basis of interest, both in the original image domain and in the distorted image domain is the DFT matrix basis. The DFT has as many columns (and rows) than the signals have entries, i.e. as many columns as the images.
a. Compute the DFT representation coefficients for each row signal in the original anddistorted image. Denote αr,i (resp. βr,i) the i-th coefficient of the r-th row in the original (resp. distorted) image. As usual with the DFT, we start indexing at 0 (be careful in your matlab implementations as indexing starts at 1 in this programming language).
b. Denote, using the notations in the lecture, eci,j the i,j-th coefficient of the functional map C. Recall that then βr,j = Pαr,keck,j. We can rewrite this in a more compact
i
matrix formulation for each row r as ber = arC, where ar (resp. ber) is the representation row of coefficients of the r-th row of the original (resp. distorted) row in the DFT basis. We can stack this matrix formulation into an even more compact formulation by writing Be = AC where the r-th row of A (resp. Be) is ar (resp. ber). When the transform mapping is known, C can be explicitly computed. Unfortunately, it is here considered as unknown and slight errors may exist leading to noise effects. Thus stacking each row allows to improve the stability of the recovered functional map. We wish to compute empirically C using a least squares approach. That is compute
Cb such that Cb ∈ argmin . Least squares is a well-known problem and it
C
can be solved, with some assumptions on the rank of A with pseudo inversion. Show that the matrix A is full rank, and so computing the pseudo inverse is legal. If it is not full rank remove redundant columns from the problem until you get a full rank matrix. Find then Cb. You might want to consider using the matlab built-in function pinv for pseudo inversion.
c. Distort the original image rows using your approximation of the functional map Cb. Note that you must go into the DFT domain to do your calculations and back to the normal domain to display an image understandable for a human being. Compare your result with the given distorted image.
d. Distort the ‘butterfly’ image by distorting its rows using Cb.
2. Audio example
Consider two audio signals (skycastle.wav and skycastle-distortion.wav) note that skycastledistortion signal is the distortional signal of skycastle. Assume that the period of the distortion is known and it is 512 in entry unit.
Utilizing the same approach as with the image case, estimate an approximate functional map between the clean signal and the noisy signal. Use the DFT basis for the basis functions. (Hint: Note that the distortion is independent from the true signal and it is periodic, then the transformation can be done periodically as well. You might want to divide your signal into successive non overlapping small signals.) Use the matrices to denoise the other audio signal (totoro-distortion.wav). Compare the obtained result with the corresponding true audio signal (totoro.wav) by graph. What is the MSE error?
To read the audiofiles you can use the audioread function. To run a vector in audio (i.e. send it to your speakers and hear your signal), you can use the sound function. For these audio signals, set the sample frequency to be Fs = 48000 when sounding them (since it is the sampling frequency).
1 file (9.0MB)
