Data Science, Audio, Mathematics, Computer Science, Deep Dives.
I_{N/2} is just the identity matrix of N/2 rows/columns, known to us. D_{N/2} is simply the diagonal entries of the first N/2 × N/2 partition of the N × N Fourier matrix F . This can be calculated easily in O(N) as it only requires us to calculate the values of 1, α, α⁴, …., α^{(N/2–1)²}, which