The complexity of computing (almost) orthogonal matrices with -copies of the Fourier transform

DOI10.1016/J.IPL.2020.106024MaRDI QIDQ2224843zbMATH OpenOpenAlexFDO

Authors Nir Ailon, Gal Yehuda

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1604.02557

zbMATH Keywords

computational complexityFourier transform complexitytheory of computation

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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, motivated by one such limitation, partly overcomes it, while at the same time sheds llight on new interesting, and 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.

Recommendations

• Paraunitary matrices, entropy, algebraic condition number and Fourier computation
• Tighter Fourier transform lower bounds
• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy
• scientific article; zbMATH DE number 1559521

Cites work

• A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy
• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Faster integer multiplication
• scientific article; zbMATH DE number 43862 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Introduction to algorithms.
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On the complexity of integer matrix multiplication
• Optimality of the Fast Fourier transform
• Paraunitary matrices, entropy, algebraic condition number and Fourier computation
• Testing juntas
• Tight bounds for testing k-linearity
• Tighter Fourier transform lower bounds
• Unified Matrix Treatment of the Fast Walsh-Hadamard Transform

Cited in

(4)

• Paraunitary matrices, entropy, algebraic condition number and Fourier computation
• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• scientific article; zbMATH DE number 5528957 (Why is no real title available?)
• A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy

Describes a project that uses

Uses Software

• Blendenpik

This page was built for publication: The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224843)