# Classical Matrix-Vector multiplication Complexity of standard matrices

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})$).

• 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. – Niel de Beaudrap Jun 15 '12 at 20:45
• What are "multiplicative complexity" and "additive complexity"? – Robin Kothari Jun 15 '12 at 21:09
• You really need a reference for the claim, as Niel indicates – Suresh Venkat Jun 15 '12 at 21:35
• It would be quite helpful if you could answer Robin's question. – Joe Fitzsimons Jun 16 '12 at 15:32
• @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. – 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.
• @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. – Markus Bläser Jun 18 '12 at 9:51