Method to reverse a Kronecker product Let's say I have two simple vectors: $[0, 1]$ and $[1, 0]$.
Their Kronecker product would be $[0, 0, 1, 0]$.
Let's say I have only the Kronecker product. How can I find the two initial vectors back?
If my two vectors are written as : $[a, b]$ and $[c, d]$, the (given) Kronecker product is:
$$[ac, ad, bc, bd] = [k_0, k_1, k_2, k_3]$$
So I have a system of four non linear equations that I wish to solve:
$$\begin{align*}
ac &= k_0\\
ad&= k_1\\
bc&= k_2\\
bd &=k_3.
\end{align*}$$
I am looking for a general way to solve this problem for any number of initial vectors in $\mathbb{C}^2$ (leading my number of variables to $2n$ and my equations to $2^n$ if I have $n$ vectors).
So here are a few specific questions:
What is the common name of this problem? 
If a general solution is known, what is its complexity class?
Does the fact that I have more and more equations when $n$ goes up compared to the number of variables help?
(Note: I really didn't know what to put as a tag.)

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.
