# Frobenius norm minimization problem

Given matrices $$A, B \in \mathbb{R}^{m \times n}$$, I want to solve the following least-squares problem

$$\min_{X \in \mathbb{R}^{n \times n}} \| A - B X \|_F^2$$

where $$\| \cdot \|_F$$ is the Frobenius norm. In this problem, $$m \ge n$$.

Does anyone know how to solve this? Or possibly convert it into an ordinary least squares problem?

• The pseudoinverse $B^+$ can be calculated by almost any numerical library, in terms of which the least-squares solution is simply $\;X=B^+A\quad$
– greg
Commented Oct 3, 2021 at 17:07

Recall that for $$A \in \mathbb{R}^{m \times n},$$

\begin{align*} \| A \|^{2}_{F} = \textrm{trace}(A^{\top} A). \end{align*}

With this in mind, consider the following (very relevant) post:

Derivative of squared Frobenius norm of a matrix

Hence, you can differentiate your expression in the usual way (being mindful of 2nd-order conditions for optimality), and find a solution to your optimization problem.

Additionally, a useful reference for a variety of matrix identities (including matrix calculus) is "The Matrix Cookbook" by Kaare Brandt Petersen and Michael Syskind Pedersen. A version of the document can be found here:

https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf

• thanks this helps a lot
– vibe
Commented Oct 2, 2021 at 5:49

For future readers, the post linked by the accepted answer leads to the following result, $$X = (B^T B)^{-1} B^T A$$ This system could be solved with a Cholesky decomposition of $$B^T B$$, however a more numerically stable method is to use a $$QR$$ decomposition of $$B$$. \begin{align} \left|\left| A - B X \right|\right|_F^2 &= \left|\left| A - Q \pmatrix{R \\ 0} X \right|\right|_F^2 \\ &= \left|\left| Q^T A - \pmatrix{R \\ 0} X \right|\right|_F^2 \\ &= \left|\left| C_1 - R X \right|\right|_F^2 + || C_2 ||_F^2 \end{align} where $$Q^T A = \pmatrix{C_1 \\ C_2}$$ and $$C_1$$ is the first $$n$$ rows of $$Q^T A$$. Then, we just need to minimize the term $$|| C_1 - R X||_F^2$$ which can be made zero by the choice, $$X = R^{-1} C_1$$ This assumes of course that $$B$$ is invertible.