Singular value decomposition of truncated discrete Fourier transform matrix

Question

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<N$.

Answer 1

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.