1
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ 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}$? $\endgroup$
    – Xinyu Chen
    Oct 27, 2022 at 20:28
  • $\begingroup$ This looks correct but I haven't had time to check the answers in the linked post. $\endgroup$
    – VHarisop
    Oct 27, 2022 at 21:57
  • $\begingroup$ Thank you! I just checked out your answer, and it is correct! $\endgroup$
    – Xinyu Chen
    Oct 27, 2022 at 23:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .