4
$\begingroup$

Background

We know how to solve the following minimization problem

$$ \min_{X} \lVert AX - B \rVert_F^2 $$

But what about the extended version?

$$ \min_{X} \lVert A \begin{bmatrix} X & X^2 \end{bmatrix} - \begin{bmatrix} B_1 & B_2 \end{bmatrix} \rVert_F^2 $$

Is there any analytical solution to this? Or we have to use gradient descent like method?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This doesn't look like a generalization but a quadratic problem. $\endgroup$
    – percusse
    Commented Jun 19, 2018 at 20:00

1 Answer 1

Reset to default
4
$\begingroup$

$$\big\| \mathrm A \begin{bmatrix} \mathrm X & \mathrm X^2\end{bmatrix} - \begin{bmatrix} \mathrm B_1 & \mathrm B_2\end{bmatrix} \big\|_{\text{F}}^2 = \underbrace{\| \mathrm A \mathrm X - \mathrm B_1 \|_{\text{F}}^2}_{=: f_1 (\mathrm X)} + \underbrace{\| \mathrm A \mathrm X^2 - \mathrm B_2 \|_{\text{F}}^2}_{=: f_2 (\mathrm X)}$$

Everybody knows that

$$\nabla f_1 (\mathrm X) = 2 \, \mathrm A^\top \big( \mathrm A \, \mathrm X - \mathrm B_1 \big)$$

The challenge is to compute $\nabla f_2 (\mathrm X)$. Since $f_2$ is quartic in $\mathrm X$, the gradient $\nabla f_2$ should be cubic.

$$f_2 (\mathrm X + h \mathrm V) = \cdots = f_2 (\mathrm X) + 2 h \, \mbox{tr} \big( \left( \mathrm X \mathrm V + \mathrm V \mathrm X \right)^\top \mathrm A^\top \left( \mathrm A \mathrm X^2 - \mathrm B_2 \right) \big) + o (h^2)$$

Computing the directional derivative of $f_2$ in the direction of $\mathrm V$ at $\mathrm X$,

$$\lim_{h \to 0} \frac{f_2 (\mathrm X + h \mathrm V) - f_2 (\mathrm X)}{h} = 2 \, \mbox{tr} \big( \left( \mathrm X \mathrm V + \mathrm V \mathrm X \right)^\top \mathrm A^\top \left( \mathrm A \mathrm X^2 - \mathrm B_2 \right) \big)$$

Extracting the gradient $\nabla f_2 (\mathrm X)$ from the (Frobenius) inner product,

$$\boxed{\nabla f_2 (\mathrm X) = 2 \, \mathrm X^\top \mathrm A^\top \big( \mathrm A \,\mathrm X^2 - \mathrm B_2 \big) + 2 \, \mathrm A^\top \big( \mathrm A \,\mathrm X^2 - \mathrm B_2 \big) \mathrm X^\top}$$

which is indeed cubic in $\rm X$. Using the anticommutator,

$$\nabla f_2 (\mathrm X) = \big\{ \mathrm X^\top, 2 \, \mathrm A^\top \big( \mathrm A \,\mathrm X^2 - \mathrm B_2 \big) \big\}$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ So what's the answer to OP's question Is there any analytical solution to this? Or we have to use gradient descent like method? $\endgroup$
    – Federico Poloni
    Commented Jun 24, 2018 at 9:56
  • 1
    $\begingroup$ @FedericoPoloni You're the expert on matrix equations! I took it as far as my knowledge goes, which is not that far. I assume that the cubic matrix equation is very hard to solve, for some rank-constrained problems I encountered in the past reduced to cubic matrix equations. $\endgroup$
    – Rodrigo de Azevedo
    Commented Jun 24, 2018 at 10:01
  • $\begingroup$ I'm thinking about that, but I don't know of a closed-form solution on the top of my head (or I would have written an answer / comment). I was just pointing out that it's useful to have the gradient computed explicitly, but that's not what OP was asking. :) $\endgroup$
    – Federico Poloni
    Commented Jun 24, 2018 at 10:07
  • 1
    $\begingroup$ @FedericoPoloni Gradient descent is an option only if the cost function is convex. However, deciding whether quartic polynomials are convex is NP-hard. $\endgroup$
    – Rodrigo de Azevedo
    Commented Jun 25, 2018 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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