Multiplication of the DFT matrix and any vector can be implemented by FFT.
I'm interesting about other fast Multiplication.
Suppose there are three matrix of size $N\times N$, $F$ , $Q$ and $P$, where $P=QFQ^T$.
$F$ is the DFT matrix and $Q$ is any orthogonal matrix.
$w$ and $x$ are two vectors of size $N\times 1$ .
If $w=Px$ (i.e., $w=[QFQ^T]x$), matrix computation need complexity of $\mathcal O(N^2)$ to obtain $w$.
Is there any way to fast implement the multiplication like FFT by complexity of $\mathcal O(N\log N)$ or other fast way?
Thanks for your answers.