# 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?

• This doesn't look like a generalization but a quadratic problem. – percusse Jun 19 '18 at 20:00

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

• 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? – Federico Poloni Jun 24 '18 at 9:56
• @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. – Rodrigo de Azevedo Jun 24 '18 at 10:01
• 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. :) – Federico Poloni Jun 24 '18 at 10:07
• @FedericoPoloni Gradient descent is an option only if the cost function is convex. However, deciding whether quartic polynomials are convex is NP-hard. – Rodrigo de Azevedo Jun 25 '18 at 10:47