The complexity of computing (almost) orthogonal matrices with ε-copies of the Fourier transform
| Autor: | Nir Ailon, Gal Yehuda |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Speedup
Computational complexity theory Intersection (set theory) Computer science Open problem Computation 010103 numerical & computational mathematics 0102 computer and information sciences Function (mathematics) 01 natural sciences Computer Science Applications Theoretical Computer Science symbols.namesake Fourier transform 010201 computation theory & mathematics Signal Processing symbols Orthogonal matrix 0101 mathematics Algorithm Information Systems |
| Zdroj: | Information Processing Letters. 165:106024 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2020.106024 |
| Popis: | The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper is motivated by one such limitation, related to the computation of near-orthogonal matrices that have the Fourier transform ‘hidden’ in low-order bits. While partly overcoming this limitation, the paper sheds light on new interesting, open problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect