This problem (Reverse kronecker product) has a known solution called "Nearest Kronecker Product" and it is generalized to matrices as well.
Given $A\in \mathbb R^{m\times n} $ with $m = m_1m_2$ and $n = n_1n_2$, find $B\in \mathbb R^{m_1\times n_1}$ and $C\in \mathbb R^{m_2\times n_2}$ so
$\phi(B,C)$ = min $|| A- B\otimes C||_F$, where $F$ denotes Frobenius norm.
This is reformulated as:
$\phi(B,C)$ = min $|| R- vec(B)\otimes vec(C)'||_F$
$vec$ is the vectorization operator which stacks columns of a matrix on top of each other. A is rearranged into $R \in \mathbb R^{m_1n_1\times m_2n_2}$ such that the sum of squares in $|| A- B\otimes C||_F$ is exactly the same as $|| R- vec(B)\otimes vec(C)'||_F$.
Example for arrangement where $m_1=3,n_1=m_2=n_2=2$:
$ \phi(B,C) = \left| \left[ \begin{array}{cc|cc} a_{11}& a_{12} & a_{13} & a_{14} \\ a_{21}& a_{22} & a_{23} & a_{24} \\ \hline a_{31}& a_{32} & a_{33} & a_{34} \\ a_{41}& a_{42} & a_{43} & a_{44} \\ \hline a_{51}& a_{52} & a_{53} & a_{54} \\ a_{11}& a_{62} & a_{63} & a_{64} \end{array} \right] - \begin{bmatrix} b_{11}& b_{12} \\ b_{21}& b_{22} \\ b_{31}& b_{32} \end{bmatrix} \otimes \begin{bmatrix} c_{11}& c_{12} \\ c_{21}& c_{22} \end{bmatrix} \right|_F \\ \phi(B,C) = \left| \begin{bmatrix} a_{11}& a_{21} & a_{12} & a_{22} \\ \hline a_{31}& a_{41} & a_{32} & a_{42} \\ \hline a_{51}& a_{61} & a_{52} & a_{62} \\ \hline a_{13}& a_{23} & a_{14} & a_{24} \\ \hline a_{33}& a_{43} & a_{34} & a_{44} \\ \hline a_{53}& a_{63} & a_{54} & a_{64} \end{bmatrix} - \begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ b_{12} \\ b_{22} \\ b_{32} \end{bmatrix} \begin{bmatrix} c_{11}&c_{21} & c_{12} & c_{22} \end{bmatrix} \right|_F $
Now the problem has turned into rank 1 approximation for a rectangular matrix. The solution is given by the singular value decomposition of $R = USV^T$ in [1,2]. $ vec(B) = \sqrt{\sigma_1}u_1, \quad vec(C) = \sqrt{\sigma_1}v_1 $
If $R$ is a rank 1 matrix solution will be exact i.e. $A$ is full seperable.[3]
[1] Golub G, Van Loan C. Matrix Computations, The John Hopkins University Pres. 1996 [2] Van Loan C., Pitsianis N., Approximation with Kronecker Products, Cornell University, Ithaca, NY, 1992 [3] Genton MG. Separable approximations of space–time covariance matrices. Environmetrics 2007; 18:681–695.