# Nuclear norm minimization of convolution matrix (circular matrix) with fast Fourier transform

I am reading a paper Recovery of Future Data via Convolution Nuclear Norm Minimization. Here, I know there is a definition for convolution matrix.

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), then its convolution matrix is given by $$$$\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},$$$$ which is also a circular matrix, but it is not a circulant matrix of size $$n\times n$$. In the case of circulant matrix, we can utilize fast Fourier transform to solve the nuclear norm minimization problem.

In fact, I am interested in the nuclear norm minimization of the convolution matrix, just like $$$$\min_{\boldsymbol{x}}~\|\mathcal{C}_{\tau}(\boldsymbol{x})\|_{*}+\frac{\lambda}{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}^{2}$$$$ where $$\|\mathcal{C}_{\tau}(\boldsymbol{x})\|_{*}$$ is the nuclear norm of $$\mathcal{C}_{\tau}(\boldsymbol{x})$$, i.e., the sum of singular values. $$\boldsymbol{z}$$ is a known variable.

[Q] Is it possible to utilize the fast Fourier transform to solve the nuclear norm minimization of the convolution matrix?