Paraunitary matrices, entropy, algebraic condition number and Fourier computation

DOI10.1016/J.TCS.2020.02.002MaRDI QIDQ2304569zbMATH OpenOpenAlexFDO

Authors Nir Ailon

Publication date 12 March 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexityFourier transformlinear algebraic computationlower bounds

Mathematics Subject Classification ID

Orthogonal matrices (15B10) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukey's Fast Fourier Transform (FFT) from 1964 is a method for computing this transformation in time $O(nlogn)$. From a lower bound perspective, relatively little is known. Ailon shows in 2013 an $Omega(nlogn)$ bound for computing the normalized Fourier Transform assuming only unitary operations on two coordinates are allowed at each step, and no extra memory is allowed. In 2014, Ailon then improved the result to show that, in a $kappa$-well conditioned computation, Fourier computation can be sped up by no more than $O(kappa)$. The main conjecture is that Ailon's result can be exponentially improved, in the sense that $kappa$-well condition cannot admit $omega(logkappa)$ speedup. The main result here is that `algebraic' $kappa$-well condition admits no more than $O(sqrtkappa)$ speedup. The definition of algebraic condition number is obtained by formally viewing multiplication by constants, as performed by the algorithm, as multiplication by indeterminates, giving rise to computation over polynomials. The algebraic condition number is related to the degree of these polynomials. Using the maximum modulus theorem from complex analysis, we show that algebraic condition number upper bounds standard condition number, and equals it in certain cases. Algebraic condition number is an interesting measure of numerical computation stability in its own right. Moreover, we believe that the approach of algebraic condition number has a good chance of establishing an algebraic version of the main conjecture.

Recommendations

• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• Tighter Fourier transform lower bounds
• A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy
• The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform
• scientific article; zbMATH DE number 1421270

Cites work

• (Nearly) sample-optimal sparse Fourier transform
• 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
• scientific article; zbMATH DE number 432514 (Why is no real title available?)
• scientific article; zbMATH DE number 3137662 (Why is no real title available?)
• On computing the Discrete Fourier Transform
• Optimality of the Fast Fourier transform
• Some bilinear forms whose multiplicative complexity depends on the field of constants
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms
• Tighter Fourier transform lower bounds

Cited in

(4)

• The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform
• An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
• Tighter Fourier transform lower bounds
• A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy

This page was built for publication: Paraunitary matrices, entropy, algebraic condition number and Fourier computation

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