Can $\sum_i{d(m_i,Pn_i)^2}$ be minimized over $P$ using linear least squares? 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.
