4
$\begingroup$

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

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

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.

$\endgroup$
4
  • 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_Y
    Feb 14, 2022 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.