main.tex (7789B)
1 \documentclass[a4paper]{article} 2 3 4 \usepackage[T1]{fontenc} 5 \usepackage[utf8]{inputenc} 6 \usepackage{mlmodern} 7 8 %\usepackage{ngerman} % Sprachanpassung Deutsch 9 10 \usepackage{graphicx} 11 \usepackage{geometry} 12 \geometry{a4paper, top=15mm} 13 14 \usepackage{subcaption} 15 \usepackage[shortlabels]{enumitem} 16 \usepackage{amssymb} 17 \usepackage{amsthm} 18 \usepackage{mathtools} 19 \usepackage{braket} 20 \usepackage{bbm} 21 \usepackage{graphicx} 22 \usepackage{float} 23 \usepackage{yhmath} 24 \usepackage{tikz} 25 \usetikzlibrary{patterns,decorations.pathmorphing,positioning} 26 \usetikzlibrary{calc,decorations.markings} 27 28 %\usepackage[backend=biber, sorting=none]{biblatex} 29 %\addbibresource{uni.bib} 30 31 \usepackage[framemethod=TikZ]{mdframed} 32 33 \tikzstyle{titlered} = 34 [draw=black, thick, fill=white,% 35 text=black, rectangle, 36 right, minimum height=.7cm] 37 38 39 \usepackage[colorlinks=true,naturalnames=true,plainpages=false,pdfpagelabels=true]{hyperref} 40 \usepackage[parfill]{parskip} 41 \usepackage{lipsum} 42 43 \usepackage[OT2,T1]{fontenc} 44 \DeclareSymbolFont{cyrletters}{OT2}{wncyr}{m}{n} 45 \DeclareMathSymbol{\Sha}{\mathalpha}{cyrletters}{"58} 46 47 \usepackage{tcolorbox} 48 \tcbuselibrary{skins,breakable} 49 50 \pagestyle{myheadings} 51 52 \markright{Popović\hfill Applied Analysis\hfill} 53 54 55 \title{University of Vienna\\ Faculty of Mathematics\\ 56 \vspace{1cm}Applied Analysis Problems 57 } 58 \author{Milutin Popovic} 59 60 \begin{document} 61 \maketitle 62 \tableofcontents 63 64 \section{Sheet 8} 65 \subsection{Finite Discrete Fourier Transform (FDFT)} 66 Consider the vector $\begin{pmatrix}a & b & c & d\end{pmatrix}^T \in 67 \mathbb{C}^4$ with a FDFT $\begin{pmatrix}A & B & C & D\end{pmatrix}^T$. We 68 can show that the vector 69 \begin{align} 70 \begin{pmatrix}a & 0 & b & 0 & c & 0 & d & 0\end{pmatrix}^T, 71 \end{align} 72 has the FDFT of 73 \begin{align} 74 \frac{1}{2}\begin{pmatrix}A & 0 & B & 0 & C & 0 & D & 0\end{pmatrix}^T. 75 \end{align} 76 For the $N=4$, $n\in\{0,\dots,3\}$ the coefficients $a, b, c, d$ are denoted in 77 $f[n]$. The FDFT is 78 \begin{align} 79 \hat{f}[k] &= \frac{1}{4} * \sum_{n=0}^3 f[n] e^{-2\pi i \frac{n}{4}k} \\ 80 &=\frac{1}{4}\left( 81 a + be^{-\pi i \frac{k}{2}} 82 + ce^{-\pi i k}+ de^{-\frac{3\pi i k}{2}} 83 \right) = \\ 84 (&=\begin{pmatrix}A & B & C & D\end{pmatrix}^T) 85 \end{align} 86 for $k \in \{0,\dots, 3\}$ accordingly. For the $N=8$, $\mathbb{C}^8$ case 87 we have $f_2[n]$ for $n \in \{0,\dots 7\}$, 88 \begin{align} 89 \hat{f}_2[k] &= \frac{1}{8} * \sum_{n=0}^7 f_2[n] e^{-2\pi i \frac{n}{8}k} \\ 90 &=\frac{1}{2}\frac{1}{4}\left( 91 a + be^{-\pi i \frac{k}{2}} 92 + ce^{-\pi i k}+ de^{-\frac{3\pi i k}{2}} 93 \right) = \\ 94 (&=\frac{1}{2}\begin{pmatrix}A & B & C & D & A & B & C & D\end{pmatrix}^T) 95 \end{align} 96 for $k \in \{0,\dots, 7\}$ accordingly. We may generalize now for 97 $\mathbb{C}^{4N}$, and the sequence for $a, b, c, d, 0$ represented by the 98 function $g[n]$ for $n \in \{0,\dots, 4N-1\}$, 99 \begin{align} 100 g[n] =\begin{cases} 101 f[n] \qquad n\in \{0, N, 2N, 3N\}\\ 102 0 \qquad \text{else} 103 \end{cases}. 104 \end{align} 105 Now we can compute the FDFT for $k \in \{0,\dots, 4N-1\}$ 106 \begin{align} 107 \hat{g}[k] &= \frac{1}{4N}\sum_{n=0}^{4N-1} g[n]e^{-2\pi i 108 \frac{n}{4N}k}\\ 109 &=\frac{4}{N}\sum_{n=0}{3}f[n]e^{-2\pi i \frac{n}{4}k}\\ 110 &=\frac{1}{N}\left(\frac{1}{4}\sum_{n=0}^3 f[n] e^{-2\pi i 111 \frac{n}{4}k} \right) \\ 112 &= \frac{1}{N} \underbrace{\begin{pmatrix}A & B & C & D & \dots & 113 \dots & A & B & C & D\end{pmatrix}^T)}_{\text{$4N$ entries, $N$ 114 sequences}}. 115 \end{align} 116 \subsection{More FDFT} 117 Consider the discrete complex exponential with frequency of $1Hz$ in 118 $\mathbb{C}^8$, for $n \in \{0, \dots , 7\}$, 119 \begin{align} 120 \exp[n] = e^{2\pi i n/8}. 121 \end{align} 122 The FDFT for $k \in \{0, \dots, 7\}$ is 123 \begin{align} 124 \hat{\exp}[k] &= \frac{1}{8}\sum_{n=0}^7 e^{2\pi i \frac{n}{8}}e^{-2\pi i 125 n \frac{k}{8}} \\ 126 &= \frac{1}{8} \sum_{n=0}^7e^{-2\pi i (k-1)\frac{n}{8}}\\ 127 &= 128 \begin{cases} 129 1\quad k=1\\ 130 0 \qquad k\neq 1 131 \end{cases}. 132 \end{align} 133 \begin{figure}[H] 134 \centering 135 \includegraphics[width=0.49\textwidth]{./fdft.png} 136 \includegraphics[width=0.49\textwidth]{./normal.png} 137 \caption{Test in Julia} 138 \end{figure} 139 \subsection{Sampling Sinusoids} 140 Consider the following continuous signal 141 \begin{align} 142 f(t) = sin(20\pi t) + sin(40\pi t) 143 \end{align} 144 with frequencies $\omega = 2\pi \nu$, $\nu_1 = 10\ \text{Hz}$ and $\nu_2 = 20\ 145 \text{Hz}$. Sketching its Fourier transform would be something like this 146 \begin{figure}[H] 147 \centering 148 \begin{tikzpicture}[ 149 axisline/.style={very thick, -stealth}, 150 xscale = 1.5, 151 yscale = 1.5 152 ] 153 \draw[axisline] (-3,0)--(3,0) node[right]{$\nu$}; 154 \draw[axisline] (0,-1.5)--(0,1.5) node[above]{$\hat{f}$}; 155 \draw[->] (-1,0) -- (-1, -1) node[below] {$-\delta(\nu - 10)$}; 156 \draw[->] (-2,0) -- (-2, 1) node[above] {$\delta(\nu - 20)$}; 157 \draw[->] (1,0) -- (1, 1) node[above] {$\delta(\nu - 10)$}; 158 \draw[->] (2,0) -- (2, 1) node[above] {$\delta(\nu - 20)$}; 159 \end{tikzpicture} 160 \end{figure} 161 The Nyquist frequency for sampling would be 162 \begin{align} 163 \nu_{\text{Nyquist}} = 2\nu_\text{max} = 2\nu_2 = 40\ \text{Hz}, 164 \end{align} 165 If we choose $50\ \text{Hz}$ for sampling we would get aliasing with the 166 following frequencies 167 \begin{align} 168 n \cdot 50\ \text{Hz} - 20\ \text{Hz} = 30\ \text{Hz},80\ \text{Hz}, 130\ 169 \text{Hz}, \dots 170 \end{align} 171 \subsection{Short-Time Fourier Transform (STFT)} 172 The Definition of the STFT is 173 \begin{align} 174 \text{STFT}\{f\} &= S_\varphi f(\tau, \omega) = \int_\mathbb{R} f(t) 175 \overline{\text{M}_\omega \text{T}_\tau \varphi}dt \\ 176 &=\int_\mathbb{R} f(t) 177 \bar{\varphi}(t - \tau)e^{-2\pi i \omega t}\ dt \\ 178 \end{align} 179 Then we have the following identity 180 \begin{align} 181 S_\varphi(\text{T}_u\text{M}_\eta f)(x,\omega) 182 &= \int_\mathbb{R} 183 \left(\text{T}_u \text{M}_\eta f(t)\right) \bar{\varphi}(t-x) e^{-2\pi i 184 \omega t}\ dt\\ 185 &= \int_\mathbb{R} e^{2\pi i \eta(t-u)}f(t-u) e^{-2\pi i \omega 186 t}\bar{\varphi}(t-x)\ dt \qquad \text{(sub: $s = t-u$)}\\ 187 &= \int_\mathbb{R} f(s)\bar{\varphi}(s-(x-u))e^{2\pi i \eta s}e^{-2\pi i 188 \omega s} e^{-2\pi i \omega u}\ ds \\ 189 &=e^{-2\pi i \omega u}\int_\mathbb{R} f(s) \bar{\varphi}(s-(x-u))e^{-2\pi i 190 (\omega - \eta)s}\ ds\\ 191 &=e^{-2\pi i \omega u}\int_\mathbb{R} 192 f(s)\overline{ \text{M}_{(\omega-\eta)} \text{T}_{(x-u)}\varphi(s)}\ ds\\ 193 &=e^{-2\pi i \omega u} S_\varphi f\left(x-u,\ \omega -\eta\right). 194 \end{align} 195 The second identity we can show 196 \begin{align} 197 S_\varphi f(x, \omega) 198 &= \langle f, \overline{\text{M}_\omega \text{T}_x \varphi}\rangle \\ 199 &= \langle\mathcal{F} f, \mathcal{F} \overline{\text{M}_\omega \text{T}_x \varphi}\rangle \\ 200 &= \int_\xi \hat{f}(\xi)\int_t \overline{\text{M}_\omega \text{T}_x 201 \varphi}(t) e^{-2\pi i \xi t}\ dt\ d\xi \\ 202 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(t-x) e^{2\pi i \omega 203 t} e^{-2\pi i \xi t}\ dt\ d\xi \\ 204 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(t-x)e^{-2\pi i (\xi 205 -\omega)t}\ dt\ d\xi \qquad \text{sub $u=t-x$}\\ 206 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(u)e^{-2\pi i (\xi 207 -\omega)u}e^{-2\pi i (\xi -\omega)x} \ dt\ d\xi\\ 208 &= \int_\xi \hat{f}(\xi)e^{-2\pi i (\xi -\omega)x}\int_t 209 \hat{\varphi}(u)e^{-2\pi i (\xi -\omega)u} \ dt\ d\xi\\ &= e^{2\pi i 210 \omega x}\int_\xi \hat{f}(\xi) \hat{\bar{\varphi}}(\xi - \omega) e^{-2\pi 211 i \xi x}d\xi\\ 212 &= e^{2\pi i \omega x} S_{\hat{\varphi}} \hat{f}(\omega, -x). 213 \end{align} 214 % printbibliography 215 \end{document}