Let $B$ be a $n$ by $n$ matrix, and $A$ a $n$ by $m$ matrix. I'm looking for the variable $X$, of size $m$ by $n$, that approximately solves $A X = B$; more precisely, the matrix $X$ that minimizes the Frobenius norm $||A X - B||_\text{fro}$.
While $n$ is large, the dimension $m$ is relatively small, and $A$ is dense. The matrix $B$ is either sparse, or products $B Y$ and $Z B$ can be computed efficiently. Thus, I'd like to use an iterative solver for the problem, but wasn't able to find anything.
$B$ is not necessarily symmetric, but I could work with the symmetric case first to benchmark different possibilities.
Is there a name for such a problem already in the community? Are there ways to solve that problem efficiently?
Let $A = Q R$ be the QR decomposition of $A$, where $Q$ is a $n$ by $m$ matrix and $R$ is a $m$ by $m$ matrix. We then minimize $|| Q R X - B ||_\text{fro}$. Let $\overline{Q}$ represent the orthogonal complement to the range of $Q$ (and thus of $A$), so that the horizontal concatenation $(Q, \overline{Q})$ is a unitary matrix.
Then $|| Q R X - B ||_\text{fro} = || R X - Q^+ B ||_\text{fro} + || \overline{Q}^+ B ||_\text{fro}$: we use the fact that the Frobenius norm is invariant under a unitary change of basis ($||U A||_\text{fro} = ||A||_\text{fro}$ for unitary $U$), and split the range of $B$ on the range of $Q$ and $\overline{Q}$.
Obviously only the first term needs to be minimized. If $R$ is non-singular (equivalent to $A$ being full rank), then $X = R^{-1} Q^+ B$. Otherwise, a dense algorithm can be used as the matrices involved are not as big as before.