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}$$.

• This is a very interesting question, but I seriously doubt you will be able to come up with a non-iterative solution to this. Apr 8 '15 at 19:08
• Thank you Michael, Would you please let me know your idea for iterative dealing with the problem? Apr 9 '15 at 3:46
• I don't have a specific idea. I'm just saying there is not going to be a closed-form solution. Apr 9 '15 at 5:14
• I'd assume the solution lies in the connection between the Singular Values of the Matrix and the vector it is composed from. Have you looked for information on that? I'd start with a search - Singular Values of Hankel Matrix.
– Royi
Aug 1 '19 at 8:27

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.