Sparse Design Matrices for Complex Hierarchies

Why Membership Becomes a Matrix

In a complex hierarchy, the model may include random effects for several kinds of units: for example, schools and classes, or subjects and test items. The number of possible units can be large even though each observation belongs to only a few of them. A design matrix records exactly which units contribute to each observation. Its important feature is often not its number of columns, but how few entries in each row are nonzero.

The matrix representation makes the structure explicit. A row corresponds to one observation; a column corresponds to a random-effect coefficient; and an entry records whether, or how strongly, that coefficient contributes to the observation’s linear predictor. Correctly identifying the nonzero entries is essential: they encode the dependence implied by shared units.

For a GLMM, a standard conditional specification is

where \(g\) is the link function, \(\mu_i=E(Y_i\mid b)\), \(\mathbf{x}_i\) is the fixed-effects design row, and \(\mathbf{z}_i\) is row \(i\) of \(Z\). The response distribution \(\mathcal{F}\) is chosen for the outcome, and observations are conditionally independent given the random effects and covariates in the usual GLMM formulation. Random effects are commonly modeled as mean-zero normal variables with a specified covariance matrix \(G\). The design matrix describes membership; by itself it does not establish that the chosen hierarchy, distribution, or covariance assumptions are appropriate.

One-Hot Membership for Nested Intercepts

For a random intercept at one level, each observation belongs to one unit at that level. Put one column in \(Z\) for each unit, and enter 1 in the column for the observation’s unit and 0 in the other columns. This is a one-hot membership row. When a second level is added, its membership indicators form another block of columns.

Nested membership requires consistent unit identities. If class labels are reused within schools—for instance, each school has a “Class 1”—the columns must represent distinct classes. The membership key is then the school–class pair, not the local class label alone. Otherwise observations from different schools could be assigned to the same class coefficient.

Separate Blocks for Crossed Factors

For crossed factors, an observation belongs to one unit from each factor, but units from one factor are not contained within units of the other. Construct one membership block per factor and concatenate the blocks. Thus each row has one indicator for its subject and one for its item in a random-intercept model. The two sets of columns remain separate because a subject effect and an item effect are different coefficients.

Random Slopes and Weighted Nonzeros

A random slope changes the entries from binary membership indicators to membership indicators multiplied by a covariate. If each class has a random intercept and a random slope for \(x\), then a row contributes the value 1 to that class’s intercept column and the observed \(x_i\) to that class’s slope column. All columns for other classes remain zero. The matrix can therefore be sparse even though its nonzero values are not all 1.

Why the Pattern Encodes Dependence

The relationship between membership and covariance can be seen directly for independent random intercepts. Suppose there are \(K\) grouping factors. Let \(g_k(i)\) denote the unit from factor \(k\) to which observation \(i\) belongs, and let \(b_{k,u}\) be the random intercept for unit \(u\) of factor \(k\). Assume \(b_{k,u}\) has mean zero and variance \(\tau_k^2\), and that distinct units and factors have independent effects. The random contribution is

Expanding the covariance of \(u_i\) and \(u_j\), any pair of distinct independent random effects contributes zero. A term contributes \(\tau_k^2\) precisely when observations \(i\) and \(j\) share the same unit of factor \(k\). Equivalently, the indicator columns in that factor’s membership block are both 1 for the same column. Therefore

This is a short derivation of the structural connection: common nonzero membership entries create covariance contributions under the stated independence and variance assumptions. With correlated random coefficients, the covariance calculation also depends on the corresponding entries of their covariance matrix; membership alone does not determine the numerical covariance.

Building and Checking Large Sparse Designs

For a large hierarchy, it is often useful to define the row and column meanings before constructing the matrix. A reliable sequence is:

Several failures have recognizable signatures. A row with no school indicator in a model that requires exactly one school membership may indicate a missing or incorrectly mapped label. Two school indicators in that row may indicate duplicated membership. Unexpectedly repeated class columns across different schools can signal that local labels were treated as globally unique. For a random slope, a row with a nonzero slope entry in another class’s block indicates a mapping error. These checks are structural: they do not establish that a random-effects distribution or link function fits the data.

Storage Choices, Alternatives, and Limits

A dense representation allocates space for all \(nq\) entries. A sparse representation stores nonzero values together with their row and column positions, so storage can be much smaller when \(\operatorname{nnz}(Z)\ll nq\). Sparse matrix operations can likewise avoid work on zeros. This is especially useful in crossed or multilevel models with many units and only a few memberships per observation.

Sparse \(Z\) does not imply that every matrix in model fitting is sparse. The random-effects covariance matrix \(G\) may contain nonzero covariance terms among coefficients, and computations involving it can have different storage and computational properties. Matrix factorizations may also create additional nonzero entries during computation. Sparse design matrices improve representation of membership; they do not guarantee that all estimation steps will be cheap.

A common alternative is to describe the model using grouping factors in statistical software and let the software construct the design internally. This can be convenient, but the implied matrix pattern is still the one defined by the memberships. Explicit matrix reasoning is useful for checking that the software’s grouping structure matches the scientific design. Conversely, manually storing a dense matrix is usually unnecessary when the membership pattern is sparse.

Another tempting alternative is to replace crossed subject and item effects with a single random intercept for each observed subject–item pair. That represents a different model: pair-specific effects do not, by themselves, give observations sharing only a subject a common subject effect, or observations sharing only an item a common item effect. Separate blocks preserve those distinct sources of dependence.

The representation also has limits. It cannot correct a wrong choice of grouping factors, compensate for insufficient replication, or resolve a mismatch between the assumed random-effects distribution and the data. A sparse matrix is a computational description of the specified model, not evidence that the model is scientifically or statistically adequate. The earlier material on covariance matrices from membership structure provides the broader covariance interpretation; here the emphasis is on how that structure appears entry by entry in \(Z\).

Common Mistake

A second practical safeguard is to treat column order as part of the model specification. Reordering columns is harmless only when the corresponding random-effect coefficients and covariance structure are reordered consistently. Otherwise a valid-looking sparse matrix can assign memberships to the wrong coefficients.