  We study the Gaussian and robust covariance estimation, assuming the true
covariance matrix to be a Kronecker product of two lower dimensional square
matrices. In both settings we define the estimators as solutions to the
constrained maximum likelihood programs. In the robust case, we consider
Tyler's estimator defined as the maximum likelihood estimator of a certain
distribution on a sphere. We develop tight sufficient conditions for the
existence and uniqueness of the estimates and show that in the Gaussian
scenario with the unknown mean, $p/q+q/p + 2$ samples are almost surely enough
to guarantee the existence and uniqueness, where $p$ and $q$ are the dimensions
of the Kronecker product factors. In the robust case with the known mean, the
corresponding sufficient number of samples is $\max[p/q, q/p] + 1$.
