Numerical Stability of DFT Computation for Signals with Structured Support
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913591732469760 |
|---|---|
| author | Pochimireddy, Charantej Reddy Siripuram, Aditya Osgood, Brad |
| author_facet | Pochimireddy, Charantej Reddy Siripuram, Aditya Osgood, Brad |
| contents | We consider the problem of building numerically stable algorithms for computing Discrete Fourier Transform (DFT) of $N$- length signals with known frequency support of size $k$. A typical algorithm, in this case, would involve solving (possibly poorly conditioned) system of equations, causing numerical instability. When $N$ is a power of 2, and the frequency support is a random subset of $\mathbb{Z}_N$, we provide an algorithm that has (a possibly optimal) $O(k \log k)$ complexity to compute the DFT while solving system of equations that are $O(1)$ in size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16044 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Numerical Stability of DFT Computation for Signals with Structured Support Pochimireddy, Charantej Reddy Siripuram, Aditya Osgood, Brad Signal Processing We consider the problem of building numerically stable algorithms for computing Discrete Fourier Transform (DFT) of $N$- length signals with known frequency support of size $k$. A typical algorithm, in this case, would involve solving (possibly poorly conditioned) system of equations, causing numerical instability. When $N$ is a power of 2, and the frequency support is a random subset of $\mathbb{Z}_N$, we provide an algorithm that has (a possibly optimal) $O(k \log k)$ complexity to compute the DFT while solving system of equations that are $O(1)$ in size. |
| title | Numerical Stability of DFT Computation for Signals with Structured Support |
| topic | Signal Processing |
| url | https://arxiv.org/abs/2401.16044 |