In an algorithm I am implementing, there is a relation of the type $A=BM$, where $A,B$ are known matrices with more rows than columns, and $M$ is an unknown square matrix. My question is how to choose $M$? I wrote "choose" because it comes down to a choice.
In the algorithm, it seems to be solved using $M=\text{pseudoinverse}(B)A$, which, from this question, corresponds to minimizing $\|A-BM\|$ for the Frobenius norm.
I am wondering if there are different expressions of $M$ which could make sense. Minimizing numerically $\|A-BM\|$ for any norm would be too costly given that typically $A\in\mathbb{R}^{500\times 100}$ so $M$ as 10000 coefficients...
TLDR; I don't think you'll get closed form solutions for other generic norms.
You can look at your problem in basically two ways:
A natural perspective is to suggest $M$ a linear transformation of $A$ for some $X$ of appropriate dimensions with then
$$M=XA=XBM$$
and therefore you would want $XB=I$. Indeed choosing the pseudo-inverse is then natural with $[(B^T B)^{-1}B^T] B = I$.
In that case, $BM=BXA=B(B^TB)^{-1}B^T A$ and indeed that is the $M$ such that $\| A-BM\|_F$ is minimized.
The other perspective is to pick another norm (nuclear norm, induced $2$-norm, ..., take a pick from https://en.wikipedia.org/wiki/Matrix_norm) and try to minimize it but (as far as I'm aware) it will typically not lead to a closed form for $M$ and you will indeed need to resort to numerical methods which apparently you do not want (note that the size of your problem is not really large so a numerical method is likely to work just fine).
The problem is then to justify the use of a specific norm over the one for which you have a closed form solution, this will depend on your application but may therefore limit the number of norms you may want to consider.