Linear Algebra – 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.