# Singular value decomposition of truncated discrete Fourier transform matrix

Let $$\mathbf{F}$$ be a discrete Fourier transform (DFT) matrix such that \begin{align} F_{m,n}=e^{-j2\pi(m-1)(n-1)/N},\quad m,n=1,\ldots,N. \end{align} What we can say about the singular value decomposition (SVD) of truncated DFT matrix (the following matrix)? \begin{align} \tilde{\mathbf{F}} = \begin{bmatrix} \mathbf{I}_k,\mathbf{0} \end{bmatrix} \mathbf{F} \begin{bmatrix} \mathbf{I}_k\\\mathbf{0} \end{bmatrix}, \end{align} where $$\mathbf{I}_k$$ is the identity matrix of size $$k.

Let me insert a factor $$N^{-1/2}$$, so that the Fourier transform is unitary: $$U_{mn}=N^{-1/2}e^{-2\pi i(m-1)(n-1)/N},\quad m,n=1,\ldots,N.$$ We truncate the $$N\times N$$ matrix $$U$$ to the $$k\times k$$ upper left corner, $$U^{(k)}_{mn}= N^{-1/2}e^{-2\pi i(m-1)(n-1)/N},\quad m,n=1,\ldots,k\leq N.$$

A characterisation of the singular values of $$U^{(k)}$$ is given in The Eigenvalue Distribution of Discrete Periodic Time-Frequency Limiting Operators and in The Future Fast Fourier Transform?.

Of order $$k^2/n$$ of the singular values are close to unity and $$k-k^2/n$$ are close to 0.

singular values squared of $$U^{(k)}$$ for $$N=1024$$, $$k=256$$.

Comment: Actually a total of $$\max(0,2k-N)$$ of the singular values of $$U^{(k)}$$ are precisely equal to 1, as Noam Elkies was kind enough to explain to me here.

• (presumably after normalizing the DFT matrix $\mathbf F$ so that it is unitary.) Commented Feb 13, 2022 at 22:27
• One can find various definitions; the OP's does not have the factor $N^{-1/2}$. Commented Feb 13, 2022 at 22:38
• thank you for spotting this, I inserted the missing factor. Commented Feb 14, 2022 at 7:18
• Can't we say something about singular vectors? Commented Feb 14, 2022 at 9:38