Sample-Size Requirements for Separable Covariance Estimation

Why Structure Changes the Sample-Size Question

A covariance matrix for a vectorized tensor can have an enormous number of free entries. A separable covariance model replaces that single unrestricted matrix with a Kronecker product of smaller mode covariances. This can reduce the number of parameters dramatically, but it does not make every sample size adequate: the observations must still contain enough variation in each mode to estimate a positive-definite factor.

There are two different questions to keep separate. A parameter count describes the dimension of a model. A rank condition asks whether the observed residuals can support a nonsingular covariance estimate or a nonsingular mode-wise update. Neither count alone guarantees that the full separable likelihood has a finite maximum.

Models and Covariance Parameter Counts

Suppose $X_1,\ldots,X_n$ are independent, identically distributed order-$K$ random tensors, with mode dimensions $d_1,\ldots,d_K$. Let $p=\prod_{k=1}^K d_k$. Assume a tensor-normal model with a common mean tensor $M$ and covariance $\Sigma=\Sigma_K\otimes\cdots\otimes\Sigma_1$, where each $\Sigma_k$ is a $d_k\times d_k$ positive-definite matrix. Vectorization is taken in the mode order consistent with this Kronecker product. An unrestricted covariance for the vectorized observation is instead any positive-definite $p\times p$ matrix.

Definition: An unrestricted covariance model allows any symmetric positive-definite $p\times p$ covariance matrix. A separable covariance model restricts that covariance to $\Sigma_K\otimes\cdots\otimes\Sigma_1$, with each mode covariance $\Sigma_k$ positive definite. The mode factors have a scale nonidentifiability: multiplying factors by positive constants whose product is one leaves the Kronecker product unchanged.

A symmetric $d\times d$ covariance matrix has $d(d+1)/2$ distinct entries. Thus the unrestricted covariance has $p(p+1)/2$ parameters. The separable factors appear to have $\sum_k d_k(d_k+1)/2$ parameters, but this overcounts because of the $K-1$ independent scale ambiguities. For example, one can impose $\det(\Sigma_k)=1$ for $k=1,\ldots,K-1$, leaving the final factor to carry the overall scale.

Parameter-count result: The unrestricted covariance dimension is $p(p+1)/2$. The separable covariance dimension, after accounting for scale nonidentifiability, is $$ m_{\mathrm{sep}}=\sum_{k=1}^K\frac{d_k(d_k+1)}{2}-(K-1). $$ These are dimensions of covariance families, not universal minimum sample sizes.

Worked Example: Comparing the Number of Covariance Parameters

Consider a three-way tensor with dimensions $2\times3\times4$. Then $p=2\cdot3\cdot4=24$. The unrestricted covariance requires $$ \frac{24(25)}{2}=300 $$ parameters.

The mode factors have $2(3)/2=3$, $3(4)/2=6$, and $4(5)/2=10$ distinct entries, for $3+6+10=19$ entries before scale adjustment. There are $K-1=2$ redundant scale dimensions, so the separable covariance dimension is $19-2=17$. The restriction therefore reduces the covariance dimension from 300 to 17. This is a substantial reduction, but it does not by itself establish that 17 parameters can be reliably estimated from any particular sample.

Unrestricted Covariance: Exact Rank Thresholds

Write $x_r=\operatorname{vec}(X_r)$. If the mean vector $\mu=\operatorname{vec}(M)$ is known, form residual vectors $z_r=x_r-\mu$. The known-mean scatter is $S=\sum_{r=1}^n z_rz_r^\mathsf{T}$. If the mean is unknown, its Gaussian maximum-likelihood estimate is the sample mean $\bar{x}=n^{-1}\sum_r x_r$; the scatter about that estimate is $S=\sum_r(x_r-\bar{x})(x_r-\bar{x})^\mathsf{T}$.

For the unrestricted Gaussian covariance model, the likelihood has a positive-definite covariance maximizer exactly when the corresponding scatter is positive definite. The following rank argument gives the resulting sample-size requirements.

Theorem: For $n$ independent $p$-dimensional Gaussian observations, the unrestricted covariance maximum-likelihood estimate is positive definite if and only if the relevant residual vectors span $\mathbb{R}^p$. With known mean, this requires $n\ge p$ and full row rank of the matrix with columns $x_r-\mu$. With an estimated mean, it requires $n\ge p+1$ and full row rank of the centered data matrix with columns $x_r-\bar{x}$.

To prove the claim, let $Z$ be the $p\times n$ matrix whose columns are the relevant residual vectors. Then $S=ZZ^\mathsf{T}$. For any $v\in\mathbb{R}^p$, $v^\mathsf{T}Sv=\|Z^\mathsf{T}v\|^2$, so $S$ is positive definite exactly when $Z^\mathsf{T}v=0$ implies $v=0$, or equivalently, when $\operatorname{rank}(Z)=p$. With known mean, $Z$ has $n$ columns, so its rank cannot exceed $n$. With estimated mean, its columns sum to zero, so its rank cannot exceed $n-1$. These give the stated necessary sample sizes; when the relevant matrix has full row rank, they are also sufficient for positive definiteness. The Gaussian covariance likelihood has its unrestricted maximum at $S/n$, or at the corresponding maximum-likelihood divisor for the model being fitted, when $S$ is positive definite. If $S$ is singular, no positive-definite unrestricted covariance attains a finite interior maximum. $\square$

Worked Example: Unrestricted Covariance With an Estimated Mean

Suppose each observation is a $2\times3\times4$ tensor, so its vectorization has $p=24$ coordinates. With an estimated mean, the centered data matrix has $n$ columns whose sum is zero. Its rank is therefore at most $n-1$. To have rank 24, it is necessary that $n-1\ge24$, or $n\ge25$. At $n=24$, the rank is at most 23, so the unrestricted sample scatter must be singular. At $n=25$, full rank is possible, though the actual data must still span all 24 dimensions. This threshold concerns existence of a positive-definite unrestricted estimate, not its precision.

Separable Covariance: Mode-Wise Rank Conditions

For mode $k$, let $X_{r,(k)}$ denote the mode-$k$ unfolding of observation $r$; it has $d_k$ rows and $q_k=\prod_{j\ne k}d_j$ columns. Use residual tensors $R_r=X_r-M$ if the mean is known, and $R_r=X_r-\bar{X}$, where $\bar{X}=n^{-1}\sum_r X_r$, if the mean is estimated. The mode-wise scatter used when updating $\Sigma_k$, with the other factors held positive definite, has the form $$ S_k=\sum_{r=1}^n R_{r,(k)}W_kR_{r,(k)}^\mathsf{T}, $$ where $W_k$ is the positive-definite Kronecker product of the inverses of the other mode covariance factors, in the unfolding's corresponding order.

This formula uses residuals, not raw observations. In particular, if a known mean is nonzero, subtract it before forming the scatter. A zero-mean formula applies to raw observations only when the mean is indeed zero (or the data have already been centered by the known mean).

Theorem: For positive-definite $W_k$, $S_k$ is positive definite exactly when the concatenated residual unfolding $A_k=[R_{1,(k)}\ \cdots\ R_{n,(k)}]$ has row rank $d_k$. Consequently, a necessary condition for a nonsingular mode-$k$ update is $nq_k\ge d_k$ with known mean, and $(n-1)q_k\ge d_k$ with estimated mean.

For the proof, define the block-diagonal matrix $B_k$ with $n$ copies of $W_k$ on its diagonal. Then $S_k=A_kB_kA_k^\mathsf{T}$. Since $B_k$ is positive definite, for every $v\in\mathbb{R}^{d_k}$, $v^\mathsf{T}S_kv=(A_k^\mathsf{T}v)^\mathsf{T}B_k(A_k^\mathsf{T}v)$ is zero exactly when $A_k^\mathsf{T}v=0$. Thus $S_k$ is positive definite exactly when $A_k$ has full row rank. With known mean, $A_k$ has $nq_k$ columns, so its rank is at most $nq_k$. With estimated mean, for each of the $q_k$ column positions the residual columns sum to zero across observations, since $\sum_r R_r=0$. These $q_k$ independent column relations imply $\operatorname{rank}(A_k)\le(n-1)q_k$. Full row rank therefore requires the stated inequalities. $\square$

Equivalently, the mode-wise necessary thresholds are $n\ge\lceil d_k/q_k\rceil$ for a known mean and $n\ge\lceil d_k/q_k\rceil+1$ for an estimated mean. They must hold for every mode. They ensure that a mode scatter is not forced to be singular by its dimensions. They are not sufficient conditions for existence of a finite joint maximum of the separable likelihood: factor interactions and the full likelihood's behavior also matter.

Worked Example: Unequal Mode Dimensions

Take dimensions $8\times2\times2$, with an estimated mean. Here $p=32$. For mode 1, $d_1=8$ and $q_1=2\cdot2=4$, so the necessary condition is $4(n-1)\ge8$, giving $n\ge3$. For mode 2, $d_2=2$ and $q_2=8\cdot2=16$, so $16(n-1)\ge2$, which requires $n\ge2$ for integer $n$. Mode 3 gives the same inequality. All mode-wise rank necessities therefore hold only when $n\ge3$, as the mode-1 condition is the limiting one.

For comparison, the unrestricted covariance has dimension $32(33)/2=528$ and requires $n\ge33$ for a positive-definite estimate with unknown mean. The separable dimension is $8(9)/2+2(3)/2+2(3)/2-2=36+3+3-2=40$. The contrast shows why the structure can make mode-wise estimation feasible at much smaller $n$, while the rank calculation alone does not certify a finite joint separable maximum.

Worked Example: A Known Nonzero Mean Must Be Subtracted

Let each observation be a $2\times2$ matrix with known mean $M=\begin{pmatrix}10&0\\0&-3\end{pmatrix}$. Suppose two observed matrices are $X_1=M+R_1$ and $X_2=M+R_2$, where $R_1=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ and $R_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. For mode 1, the unfolding is the matrix itself. Set the other factor's inverse $W_1=I_2$ to display the rank calculation. The correct scatter is $$ S_1=R_1R_1^\mathsf{T}+R_2R_2^\mathsf{T}=I_2+I_2=2I_2. $$ It is positive definite, and the concatenated residual unfolding $[R_1\ R_2]$ has row rank 2.

Using the raw observations instead would give $X_1=\begin{pmatrix}11&0\\0&-2\end{pmatrix}$ and $X_2=\begin{pmatrix}10&1\\1&-3\end{pmatrix}$. Their raw scatter has a different value because it includes the nonzero mean contribution; it is not the covariance scatter around the specified mean. Thus the known-mean rank argument must be applied to $X_r-M$, not $X_r$.

What the Thresholds Do—and Do Not—Say

The unrestricted threshold is exact for a positive-definite Gaussian maximum-likelihood covariance: below it, the scatter cannot have full rank. In the separable model, the parameter count and the mode rank inequalities answer different questions. A much smaller value of $m_{\mathrm{sep}}$ expresses the reduction in model dimension; the mode inequalities identify dimensional bottlenecks for the factor updates. Neither should be read as a universal rule such as “sample size must exceed the number of covariance parameters.”

For example, satisfying all mode inequalities only removes particular rank obstructions. It does not prove that the full likelihood is bounded or that the maximizing factors are unique. Conversely, parameter counting does not replace an analysis of the likelihood or the observation geometry. For practical planning, calculate the unrestricted threshold, the separable parameter dimension, and every mode-wise rank bound, then treat them as distinct diagnostics rather than interchangeable guarantees.

Common Mistake

Wrong reasoning: “The mean is known, so the covariance scatter is $\sum_r x_rx_r^\mathsf{T}$, even if the specified mean is nonzero.” This treats observations as residuals from zero.
Correction: For known mean $\mu$, use $\sum_r(x_r-\mu)(x_r-\mu)^\mathsf{T}$. For tensors, use the residuals $X_r-M$ in every mode-wise scatter. The raw-observation formula is appropriate only for a known zero mean or already-centered observations.
Another overreach: “Every mode-wise rank inequality holds, so a finite separable maximum is guaranteed.” The inequalities establish that the scatters are not forced to be singular by their dimensions; they are not a general existence theorem for the joint likelihood.

Key takeaway: Separable structure can sharply reduce covariance dimension, but sample-size reasoning still depends on mode dimensions and residual rank. Use the correct residuals, check each mode, and do not confuse necessary rank conditions with a guarantee of finite joint estimation.

Check Your Understanding

Use the dimensions and mean assumptions in each question; distinguish parameter counts from rank requirements.

For dimensions $3\times4\times5$, calculate the separable covariance parameter dimension and the unrestricted covariance parameter dimension.
For an unrestricted covariance in dimension $p$, why is $n\ge p+1$ necessary when the mean is estimated?
For dimensions $5\times3\times2$ and an estimated mean, calculate the necessary sample-size inequality for each mode.
If a known tensor mean is nonzero, what residual tensors belong in the mode-wise scatter?
Explain why satisfying every mode-wise rank inequality does not, by itself, prove that the full separable likelihood has a finite maximum.