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?

$\endgroup$
  • 1
    $\begingroup$ This doesn't look like a generalization but a quadratic problem. $\endgroup$ – percusse Jun 19 '18 at 20:00
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\}$$

$\endgroup$
  • $\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 Jun 24 '18 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 Jun 24 '18 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 Jun 24 '18 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 Jun 25 '18 at 10:47

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.