Proximal Operator for the Nuclear Matrix Norm of Hankel Matrix - $ \operatorname{Hankel} \left( x \right) $ I have a problem in hand for which I need to compute the proximal operator of the composite function $ {\left\| \mbox{Hankel} (x) \right\|}_{\ast} $ where $ x \in \mathbb R^N $ and $ \left\| \cdot \right\|_{\ast} $ denotes the matrix nuclear norm.
For a general matrix $X$, the proximal map of the $\| X \|_{\ast}$ becomes a soft-thresholding of the singular values. I'll be grateful if somebody help me to evaluate the proximal map of $\| \mbox{Hankel} (x)\|_{\ast}$.
 A: You could solve this iteratively with a splitting approach. Let $\mathcal{H} = \mathbb{R}^N$ and set $\mathcal{G}$ to be Hilbert space of appropriately-sized matrices. Notice that the Hankel transformation $H$ is an invertible linear operator, and its adjoint can be computed explicitly. Rephrasing the problem, we seek to
$$\text{minimize}_{(x,M) \in \mathcal{H} \times \mathcal{G}} \frac{1}{2}\|y-x\|^2 + \|M\|_{\text{nuc}} \text{ such that } Hx = M.$$
Now we will do some rephrasing with an eye towards applying Douglas Rachford splitting. Set $F:\mathcal{H}\times \mathcal{G} : (x,M) \mapsto \frac{1}{2}\|y-x\|^2 + \|M\|_{\text{nuc}}$. Then since it's a separable function, $\text{prox}_F = (\text{prox}_{\frac{1}{2}\|y - \cdot \|^2}\ ,\ \text{prox}_{\|\cdot\|_{\text{nuc}}})$ which is easily computable. Let $G$ be the $0-\infty$ indicator function of $C = \{(x,M) \in \mathcal{H} \times \mathcal{G} | Hx=M\}$. Therefore $\text{prox}_G = P_C$ is the projection onto the graph of a linear operator which is computable, provided you can evaluate the adjoint (e.g. several formulae are provided in Bauschke & Combettes' 2017 book, Example 29.19).
Now you're really just minimizing $F +G$ over the Hilbert space $\mathcal{H} \times \mathcal{G}$, so you're free to use the DR algorithm (also in the same book).
It is worth noting that if $HH^*$ was invertible, this could solved in closed-form (via Prop. 23.25 from the same book), but this is not the case for the Hankel transformation.
