Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.16044 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |