# Nuclear norm minimization of a circulant matrix with fast Fourier transform

Given any vector $$\boldsymbol{x}=(x_1,x_2,\cdots,x_n)^\top\in\mathbb{R}^{n}$$, its circulant matrix can be written as follows, $$$$\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}$$$$

Here, for the circulant matrix $$\mathcal{C}(\boldsymbol{x})$$, we can define its nuclear norm as the sum of singular values, namely, $$\|\mathcal{C}(\boldsymbol{x})\|_{*}$$.

[Q] Is it possible to utilize the fast Fourier transform to solve the following optimization problem?

$$$$\min_{\boldsymbol{x}}~\|\mathcal{C}(\boldsymbol{x})\|_{*}+\frac{\lambda}{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}^{2}$$$$ where $$\boldsymbol{z}\in\mathbb{R}^{n}$$ is a known variable.

Equivalently, we have $$$$\min_{\boldsymbol{x}}~\|\mathcal{C}(\boldsymbol{x})\|_{*}+\frac{\lambda}{2n}\|\mathcal{C}(\boldsymbol{x})-\mathcal{C}(\boldsymbol{z})\|_{F}^2$$$$

Thanks for your help in advance!

## 1 Answer

Here is an idea (rough sketch; please be wary of typos). Let $$F_n$$ denote the $$n \times n$$ (unnormalized) DFT matrix and $$U_n := \frac{1}{\sqrt{n}} F_n$$ its unitary version. We know that

$$C(x) = U_n \mathrm{diag}(\hat{x}) U_n^*,$$ where $$\hat{x} := F_n x$$ denotes the Fourier transform of $$x$$. Because $$U_n$$ is unitary and $$\| \cdot \|_*$$ is a unitarily invariant norm, we have $$\|C(x) \|_{*} = \| U_n \mathrm{diag}(\hat{x}) U_n^*\|_* = \| \mathrm{diag}(\hat{x})\|_* = \| \hat{x} \|_1.$$

Now, observe that $$\|x - z\|_2^2 = \| U_n^* U_n (x - z) \|_2^2 = \|U_n(x - z)\|_2^2 = \frac{1}{n} \| F_n(x - z) \|_2^2 = \frac{1}{n} \| \hat{x} - \hat{z} \|^2.$$

where $$\hat{x}$$ is the Fourier transform of $$x$$ and $$\hat{z}$$ is the Fourier transform of $$z$$. So you have reduced your problem to

$$\arg\min_{\hat{x}} \| \hat{x} \|_1 + \frac{\lambda}{2n} \| \hat{x} - \hat{z} \|_2^2,$$

which reduces to the proximal operator of the $$\ell_1$$ norm in complex space. Specifically, the solution is given by $$$$\hat{x}_k:=\frac{\hat{z}_{k}}{|\hat{z}_k|}\cdot\max\{0,|\hat{z}_k|-\frac{n}{\lambda}\},k=1,\ldots,n.$$$$

• Thank you very much! Great reply! Is $\hat{x}_{k}=\frac{\hat{z}_k}{|\hat{z}_k|}\cdot\max\{0,|\hat{z}_k|-n/\lambda\},k=1,\ldots,n$ the solution to $\min_{\hat{\boldsymbol{x}}}~\|\hat{\boldsymbol{x}}\|_1+\frac{\lambda}{2n}\|\hat{\boldsymbol{x}}-\hat{\boldsymbol{z}}\|_{2}^{2}$? Commented Oct 27, 2022 at 20:28
• This looks correct but I haven't had time to check the answers in the linked post. Commented Oct 27, 2022 at 21:57
• Thank you! I just checked out your answer, and it is correct! Commented Oct 27, 2022 at 23:11