Let $\mathbf{F}$ be a discrete Fourier transform (DFT) matrix such that \begin{align} F_{m,n}=e^{j2\pi(m1)(n1)/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$.
1 Answer
Let me insert a factor $N^{1/2}$, so that the Fourier transform is unitary: $$U_{mn}=N^{1/2}e^{2\pi i(m1)(n1)/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(m1)(n1)/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 TimeFrequency Limiting Operators and in The Future Fast Fourier Transform?.
Of order $k^2/n$ of the singular values are close to unity and $kk^2/n$ are close to 0.
_{singular values squared of $U^{(k)}$ for $N=1024$, $k=256$.}
Comment: Actually a total of $\max(0,2kN)$ of the singular values of $U^{(k)}$ are precisely equal to 1, as Noam Elkies was kind enough to explain to me here.

1$\begingroup$ (presumably after normalizing the DFT matrix $\mathbf F$ so that it is unitary.) $\endgroup$ Feb 13, 2022 at 22:27

1$\begingroup$ One can find various definitions; the OP's does not have the factor $N^{1/2}$. $\endgroup$ Feb 13, 2022 at 22:38

$\begingroup$ thank you for spotting this, I inserted the missing factor. $\endgroup$ Feb 14, 2022 at 7:18

$\begingroup$ Can't we say something about singular vectors? $\endgroup$– Math_YFeb 14, 2022 at 9:38