Given any vector $\boldsymbol{x}=(x_1,x_2,\ldots,x_n)^\top\in\mathbb{R}^{n}$ with a certain kernel size $\tau\in\mathbb{N}^+$ ($1<\tau<n$), then its convolution matrix is given by \begin{equation} \mathcal{C}_{\tau}(\boldsymbol{x})=\begin{bmatrix} x_1 & x_n & x_{n-1} & \cdots & x_{n-\tau+2} \\ x_2 & x_1 & x_n & \cdots & x_{n-\tau+3} \\ x_3 & x_2 & x_1 & \cdots & x_{n-\tau+4} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_n & x_{n-1} & x_{n-2} & \cdots & x_{n-\tau+1} \\ \end{bmatrix}\in\mathbb{R}^{n\times\tau} \end{equation}
Note that the above convolution matrix is not a circulant matrix of size $n\times n$. Here, the circulant matrix can be written as follows, \begin{equation} \mathcal{C}(\boldsymbol{x})=\begin{bmatrix}x_1 & x_n & x_{n-1} & \cdots & x_2 \\ x_2 & x_1 & x_{n} & \cdots & x_{3} \\ x_3 & x_2 & x_1 & \cdots & x_4 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_n & x_{n-1} & x_{n-2} & \cdots & x_1 \end{bmatrix}\in\mathbb{R}^{n\times n} \end{equation}
It is not hard to see that the convolution matrix $\mathcal{C}_\tau(\boldsymbol{x})$ consists of the first $\tau$ columns of the circulant matrix $\mathcal{C}(\boldsymbol{x})$.
In terms of circulant matrix, we can utilize fast Fourier transform to compute its singular values. Since $\mathcal{C}_\tau(\boldsymbol{x})$ is the submatrix of $\mathcal{C}(\boldsymbol{x})$, is it possible to compute the singular values of convolution matrix through fast Fourier transform?