Suppose P is a $2 \times 2$ matrix and both $m_i$ and $n_i$ are given 2 dimensional vectors in Cartesian coordinates, $d$ is an Euclidean distance. Is the following correct?
I will try to rewrite the problem as $b - Ax$ and minimize over $x$. $$i \leq N$$ $$P = \begin{pmatrix}p_1 & p_2 \\ p_3 & p_4\end{pmatrix} \mapsto x = \begin{pmatrix}p_1 \\p_2\\p_3\\p_4\end{pmatrix}$$ $$b \in R^{2N}; b = \begin{pmatrix}m_{1,1} \\m_{1,2}\\m_{2,1} \\m_{2,2}\\\vdots\\m_{N,2}\end{pmatrix}$$ $$A \in R^{2N \times 4}$$ $$A = \begin{pmatrix}n_{1,1} & n_{1,2} & 0 & 0 \\0 & 0 & n_{1,1} & n_{1,2} \\ n_{2,1} & n_{2,2} & 0 & 0 \\0 & 0 & n_{2,1} & n_{2,2} \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & n_{N,1} & n_{N,2}\end{pmatrix}$$
Your problem is much simpler...
Minimization can be performed independently for unknowns $(p_{1}, p_{2})$ and $(p_{3}, p_{4})$.
$$ I(p_{1}, p_{2}, p_{3}, p_{4}) = \sum \limits_{i = 1}^{N}((m_{i, 1} - p_{1} n_{i, 1} - p_{2} n_{i, 2})^{2} + (m_{i, 2} - p_{3} n_{i, 1} - p_{4} n_{i, 2})^{2}) = \\ = I_{1}(p_{1}, p_{2}) + I_{2}(p_{3}, p_{4}) $$
where
$$ I_{1}(p_{1}, p_{2}) = \sum \limits_{i = 1}^{N}(m_{i, 1} - p_{1} n_{i, 1} - p_{2} n_{i, 2})^{2} $$
and
$$ I_{2}(p_{3}, p_{4}) = \sum \limits_{i = 1}^{N}(m_{i, 2} - p_{3} n_{i, 1} - p_{4} n_{i, 2})^{2} $$
can be minimized independently with usual least squares method.