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,
\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}
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?
\begin{equation}
\min_{\boldsymbol{x}}~\|\mathcal{C}(\boldsymbol{x})\|_{*}+\frac{\lambda}{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}^{2}
\end{equation}
where $\boldsymbol{z}\in\mathbb{R}^{n}$ is a known variable.
Equivalently, we have
\begin{equation}
\min_{\boldsymbol{x}}~\|\mathcal{C}(\boldsymbol{x})\|_{*}+\frac{\lambda}{2n}\|\mathcal{C}(\boldsymbol{x})-\mathcal{C}(\boldsymbol{z})\|_{F}^2
\end{equation}
Thanks for your help in advance!
Best 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 \begin{equation} \hat{x}_k:=\frac{\hat{z}_{k}}{|\hat{z}_k|}\cdot\max\{0,|\hat{z}_k|-\frac{n}{\lambda}\},k=1,\ldots,n. \end{equation}