日時：9月22日（月）15:00-16:00

Nir Ailon (Technion)

Lower Bound for Fourier Transform in the Well-Conditioned Linear Model
(Or: If You Want a Faster Fourier Transform You'd Need to Sacrifice Accuracy)


The Fourier Transform is one of the most important linear transformations
used in science and technology. Cooley and Tukey's Fast Fourier Transform
(FFT) from 1964 is a method for computing this transformation in time 
O(n log n). In spite of its importance, no nontrivial (super-linear)
lower bounds were known without making very strong assumptions.
Morgenstern's result from 1974 provides an Ω(n log n) lower bound for
the *unnormalized* Fourier Transform (of determinant n^{n/2}), 
assuming only numbers with bounded constant modulus are used.
[Ailon 2013] shows an Ω(n log n) bound for the *normalized* Fourier
Transform (of determinant 1) assuming only unitary operations on two
coordinates are allowed. In this work we show that, as long as the
computation is well conditioned, *any scaling* of the Fourier transform
requires Ω((n log n)/R) operations, where R is the condition number.
This means that, on a given machine, a faster Fourier transform is less
accurate. The main new technique is definition of a matrix entropy
function, using "quasi-probabilities" (which can be negative or >1).
I will discuss the result and present some open questions.

問合せ先：瀧本（C03）