Computational Scaling of Unstructured Correlations

Why the Number of Visits Matters

An unstructured working correlation allows each pair of visits to have its own correlation. This flexibility can be useful when the dependence pattern does not fit a simpler structure. But flexibility has a cost: with more visits, there are many more correlations to estimate, and GEE calculations must work with larger matrices. The growth is faster than the visit count itself.

Let \(m\) be the number of scheduled visits in a repeated-measures study, with the same schedule for each cluster. A working correlation matrix \(R\) is an \(m\times m\) symmetric matrix whose diagonal entries equal one. In the unstructured case, each distinct off-diagonal entry is a separate working-correlation parameter. The matrix must also satisfy the positive-definite constraint needed for stable inversion.

This count concerns the correlation matrix alone. It does not include mean-model coefficients or any other parameters. It also does not say how many independent pieces of information the data provide: pairwise residual products from the same cluster are dependent.

Deriving the Parameter and Storage Growth

There are \(m\) choices for the first visit in an ordered listing of a pair and \(m-1\) choices for the second. Each unordered pair is counted twice, once in each order. Therefore the number of distinct pairs is \(m(m-1)/2\).

The number of entries stored is similar in order of growth. A full matrix stores \(m^2\) entries, while a representation that stores only one triangle, including the diagonal, stores \(m(m+1)/2\). Since the diagonal is known, only \(m(m-1)/2\) entries need to be estimated, but an implementation may still store or manipulate the full matrix.

Dense Matrix Operations in GEE

The working covariance matrix for cluster \(i\) is commonly written \(V_i=A_i^{1/2}RA_i^{1/2}\), where \(A_i\) contains marginal variances. When \(A_i\) has positive diagonal entries and \(R\) is positive definite, \(V_i\) is positive definite as well. A GEE calculation uses \(V_i^{-1}\) to weight residuals and derivatives of the mean. The correlation matrix therefore affects both statistical estimation and the linear algebra required to carry it out.

For a general dense positive-definite \(m\times m\) matrix, Cholesky factorization takes order \(m^3\) arithmetic operations and order \(m^2\) storage. This is a matrix-size cost, not a claim that every implementation must refactor a separate matrix for every cluster.

To see the cubic cost, consider the Cholesky algorithm’s updates to the trailing submatrix after each pivot. At pivot \(k\), the remaining block has side length \(m-k\), so its rank-one update requires order \((m-k)^2\) operations. Summing across pivots gives

Thus the leading growth is cubic. The factorization stores a triangular array with \(m(m+1)/2\) entries, which is order \(m^2\). A matrix-vector product computes \(m\) dot products of length \(m\), giving order \(m^2\) operations. These are asymptotic costs; exact operation counts depend on the implementation.

For a fixed complete visit schedule, the same \(R\) is used across clusters. Since \(A_i\) is diagonal, \(V_i^{-1}=A_i^{-1/2}R^{-1}A_i^{-1/2}\). One can factor or invert \(R\) once per update of its parameters, then use diagonal rescaling and matrix operations for each cluster. The precise cost depends on how the GEE is implemented. In contrast, when clusters have different observed visit subsets, their covariance matrices are generally different submatrices; factoring each distinct matrix can require order \(m_i^3\) work for a cluster with \(m_i\) observed visits. Repeated missingness patterns may permit reuse within a pattern, but reuse is not automatic across different submatrices.

Numerical Stability and Practical Choices

As \(m\) grows, an unstructured estimate must determine more correlations from the available clusters. If there are few clusters, or if some visit pairs are rarely observed together, the estimated entries can be noisy. Those entries are not independent estimates: many pairs share a visit and all pairwise quantities within a cluster share data. Consequently, the raw count of available pairs should not be treated as the number of independent observations.

There is also a numerical issue. A correlation matrix close to singular has a small eigenvalue, so its inverse can be highly sensitive to small changes in its entries. Estimation noise can then produce unstable weighted calculations; an estimate that is not positive definite cannot be used as a valid covariance matrix. The positive-definite constraint is a property of the whole matrix, not a separate check on each correlation.

A structured working correlation can reduce the number of free parameters substantially. For example, an exchangeable structure uses one common off-diagonal correlation, while an AR(1) structure uses a single parameter to describe decay across equally spaced ordered visits. Such restrictions can simplify estimation and reduce the dimension of the matrix problem. They do not guarantee a better-conditioned estimate in every data set, and an overly restrictive structure may represent the dependence poorly.

Reducing the number of visits can likewise lower parameter and computation burdens, but it trades away observed information. When visit times are missing for some clusters rather than deliberately removed for everyone, the number of pairwise observations may vary across visit pairs. That imbalance is a warning sign for unstable unstructured estimates, not a reason to count all pairs as equally informative.

Common Mistake

A common error is to say, “The number of visits doubled, so the computational burden doubled,” or to multiply a cubic cost by the number of clusters without checking whether the same matrix factorization can be reused.

The correction is to identify the operation first. The unstructured parameter count and dense storage grow quadratically in \(m\); a dense factorization grows cubically. Then determine whether each cluster uses the same matrix, as with a shared complete schedule, or a different observed submatrix. A shared factorization may be reused while the working correlation is fixed, but cluster-specific matrix-vector calculations remain.