Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta_{m}})$ and an additive complexity of $O(n^{1+\delta_{a}})$ (number of additions) where both $\delta_{m}$ and $\delta_{a}$ cannot be $0$ simultaneously?

(Please refer: Section 2.2 Page 15 of "Complexity Lower Bounds Using Linear Algebra", by Satyanarayana V. Lokam, for candidate matrices conjectured to have an arithmetic complexity (multiplicative + additive complexity) of $\Omega(n^{1+\delta})$).

  • 4
    $\begingroup$ Can you provide a source for the above claims? Specifically, I don't know what you mean by 'Hadamard' transform in this case, as the operation I most commonly know by Hadamard has by definition a complexity of precisely 1 in the usual elementary gate sets discussed in the literature. $\endgroup$ – Niel de Beaudrap Jun 15 '12 at 20:45
  • 5
    $\begingroup$ What are "multiplicative complexity" and "additive complexity"? $\endgroup$ – Robin Kothari Jun 15 '12 at 21:09
  • 3
    $\begingroup$ You really need a reference for the claim, as Niel indicates $\endgroup$ – Suresh Venkat Jun 15 '12 at 21:35
  • 4
    $\begingroup$ It would be quite helpful if you could answer Robin's question. $\endgroup$ – Joe Fitzsimons Jun 16 '12 at 15:32
  • 2
    $\begingroup$ @Arul: The reference you provide isn't complete, and even if it was, it's asking a lot to get people to go off to read a paper to understand your question. $\endgroup$ – Joe Fitzsimons Jun 16 '12 at 20:18

Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity.

| cite | improve this answer | |
  • $\begingroup$ Hi Markus: Could you explain what do you mean by "the absolute values of the constants go to infinity" and how close the restricted models are to reality? $\endgroup$ – T.... Jun 18 '12 at 9:30
  • $\begingroup$ @Arul: Maybe it is easier to phrase it the other way: If the absolute values of the scalars occuring in the circuits are bounded by some constant, then we have an $\Omega(n \log n)$ lower bound. $\endgroup$ – Markus Bläser Jun 18 '12 at 9:51
  • $\begingroup$ Hi Markus: I am unfamiliar with Morgenstern's theorem. It seems from what you are saying several researcher's tried and failed. The constants are unbounded. It seems to me that this is an evidence of failure in assumption that lower bound is superlinear. It does not explain why a superlinear lower bound is conjectured except people have failed. $\endgroup$ – T.... Jun 18 '12 at 16:49
  • $\begingroup$ Can you provide original reference and standard citations? $\endgroup$ – T.... Jun 18 '12 at 16:51
  • $\begingroup$ Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory, Springer, Theorem 13.14. Originally proved in the thesis of J. Morgenstern. Note that although in the general model, arbitrarily large constants can be used, it is not clear how to use them when computing the DFT, since all coefficients in the DFT matrix are bounded. $\endgroup$ – Markus Bläser Jun 18 '12 at 18:51

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.