3
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ This is a very interesting question, but I seriously doubt you will be able to come up with a non-iterative solution to this. $\endgroup$ – Michael Grant Apr 8 '15 at 19:08
  • $\begingroup$ Thank you Michael, Would you please let me know your idea for iterative dealing with the problem? $\endgroup$ – mmn61 Apr 9 '15 at 3:46
  • $\begingroup$ I don't have a specific idea. I'm just saying there is not going to be a closed-form solution. $\endgroup$ – Michael Grant Apr 9 '15 at 5:14
  • $\begingroup$ 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. $\endgroup$ – Royi Aug 1 '19 at 8:27
0
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.