I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses multiplications by scalar and addtions, that he stated Morgenstern's theorem the following way

Every linear algorithm that computes DFT (Discrete Fourier Transform) , in which the scalar are bounded in their absolute value by $C$ , takes at least $\Omega_C(n\log{n})$ addition operations.

I haven't understood his proof , if someone can give me guidlines to the proof I'll be more than happy :) [right now my proof of the theorem looks like a mess]

p.s.: In class he said we will write in each step the coeffiecents of the linear function that was just computed , then he defined a "computation advancment function" , I didn't understand his definition of this function , it was definied something like $\phi(k)=$ maximum determinant of n$\times$n matrices that were computed untill the k'th step [I probably copied wrong]

  • $\begingroup$ The problem lies in the following two facts: I literally couldn't understand what I wrote in my notebook(The proffesor went really fast) I nned the proof from class because I am scribing a class including this theorem.(it was the last class so no one except me wrote at that time) I am not asking for proof but I haven't undertood the start of the proof , maybe after understanding what he meant when he defined the computation advancment function it would be clearer how to prove this theorem $\endgroup$ – UserB95 Feb 19 '15 at 0:00
  • $\begingroup$ I ask for guidelines not proof because few lines confused me , and I don't have the intution for why the theorem is correct. $\endgroup$ – UserB95 Feb 19 '15 at 0:00
  • $\begingroup$ A source where the proof is readible will be also super :) [I haven't found one] $\endgroup$ – UserB95 Feb 19 '15 at 0:06

Morgenstern first defines the notion of a linear algorithm. A linear algorithm gets as input $x_1,\ldots,x_n$ and its goal is to compute some $y_1,\ldots,y_m$, each of which is a (specific) linear combination of $x_i$s. The algorithm proceeds in steps, starting with step $n+1$. At step $t$, the algorithm computes $x_t = \lambda_t x_i + \mu_t x_j$ for some $i,j < t$. At the end of the computation, for each $i$, $y_i = x_j$ for some $j$.

For example, here is an algorithm computing the unnormalized DFT on 2 variables: $$ x_3 \gets x_1 + x_2 \\ x_4 \gets x_1 - x_2 $$ Similarly, the unnormalized two dimensional DFT on $2^2$ variables is computed by: $$ x_5 \gets x_1 + x_2 \\ x_6 \gets x_1 - x_2 \\ x_7 \gets x_3 + x_4 \\ x_8 \gets x_3 - x_4 \\ x_9 \gets x_5 + x_7 \\ x_{10} \gets x_5 - x_7 \\ x_{11} \gets x_6 + x_8 \\ x_{12} \gets x_6 - x_8 $$

We can view each $x_t$ as an $n$-dimensional vector which gives the linear combination of $x_1,\ldots,x_n$ producing $x_t$; call this vector $v_t$. The vectors $v_1,\ldots,v_n$ are just the $n$ basis vectors.

Morgenstern defines the quantity $\Delta_t$, which is the maximum magnitude of the determinant of any square submatrix of the matrix $V_t$ whose rows are $v_1,\ldots,v_t$.

Lemma. Let $c \geq 1/2$. If $|\lambda_s|,|\mu_s| \leq c$ for all $s$ then $\Delta_{n+t} \leq (2c)^t$.

Proof. The proof is by induction on $t$. When $t = 0$, this is easy to verify directly since $V_n$ is just the identity matrix. Consider now any $t > 0$. Every square submatrix of $V_t$ is either a square submatrix of $V_{t-1}$, in which case its determinant is at most $(2c)^{t-1} \leq (2c)^t$ by induction, or it involves the new row $v_t = \lambda_t v_i + \mu_t v_j$. In the latter case, we can write the square submatrix $A$ as $A = \lambda_t B + \mu_t C$, where $B,C$ are square submatrices of $V_{t-1}$ (replace the relevant part of $v_t$ by the corresponding parts of $v_i$ and $v_j$). Since the determinant is a linear function of any of its rows, $\det(A) = \lambda_t \det(B) + \mu_t(C)$. By induction, $|\det(B)|,|\det(C)| \leq (2c)^{t-1}$, and so $$|\det(A)| \leq |\lambda_t| |\det(B)| + |\mu_t| |\det(C)| \leq c(2c)^{t-1} + c(2c)^{t-1} = (2c)^t.$$

Corollary. Computing the DFT on $n$ variables using a linear algorithm with bounded coefficients requires $\Omega(n\log n)$ steps.

Proof. The determinant of the DFT matrix is $n^{n/2}$. Hence any linear algorithm computing the DFT in $t$ steps satisfies $\Delta_t \geq n^{n/2}$. If the bound on the coefficients is $c$, then the lemma shows that $(2c)^t \geq n^{n/2}$ and so $t = \Omega(n\log n)$.

Remark. Strassen has shown that any algebraic algorithm (algorithm involving $+,-,\cdot,/$) for computing the DFT can be transformed to a linear algorithm using the same number of steps.


Morganstern's original paper is here:

Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast Fourier transform. J. ACM, 20(2):305–306, April 1973.

  • $\begingroup$ I do't have access to this $\endgroup$ – UserB95 Feb 19 '15 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.