Convergence of the Empirical Gram Matrix

Why the Empirical Gram Matrix Matters

In random-design regression, each observation contributes a vector of regressors. Their sample second moments determine whether the observed design contains enough independent variation to support estimation. The population counterpart describes that variation in the sampling distribution; the empirical Gram matrix records it in the realized sample. Understanding how the latter approaches the former is a basic step toward studying large-sample least squares.

The key condition for eventual full rank is not merely that the sample size grows. In fixed dimension, the population Gram matrix must be positive definite. Under iid sampling and finite second moments, the empirical matrix converges to that population matrix, so a strictly positive smallest population eigenvalue eventually rules out a rank-deficient sample, with probability one.

Definition and Assumptions

Let \(p\) be fixed, and let \(X_1,X_2,\ldots\) be iid random vectors in \(\mathbb{R}^p\). In a regression setting, \(X_i\) is the column vector of regressors for observation \(i\). Assume \(E[\|X_i\|^2]<\infty\), where \(\|\cdot\|\) is the Euclidean norm. Define the population Gram matrix \(Q\) and the empirical Gram matrix \(G_n\) as follows.

Definition: The population Gram matrix is \(Q=E[X_iX_i^{\mathsf T}]\). The empirical Gram matrix based on \(n\) observations is \(G_n=\frac{1}{n}\sum_{i=1}^n X_iX_i^{\mathsf T}\). If \(D_n\) is the \(n\times p\) matrix whose \(i\)th row is \(X_i^{\mathsf T}\), then \(G_n=D_n^{\mathsf T}D_n/n\).

Both matrices are symmetric and positive semidefinite: for any \(a\in\mathbb{R}^p\), \(a^{\mathsf T}Qa=E[(a^{\mathsf T}X_i)^2]\geq 0\), and \(a^{\mathsf T}G_na=\frac{1}{n}\sum_{i=1}^n(a^{\mathsf T}X_i)^2\geq 0\). The empirical Gram matrix is an uncentered second-moment matrix. It is not generally the sample covariance matrix, which subtracts a sample mean.

The moment assumption makes each entry of \(Q\) finite. Indeed, for coordinates \(j,k\), the Cauchy–Schwarz inequality gives

E[|X_{ij}X_{ik}|] \leq \sqrt{E[X_{ij}^2]E[X_{ik}^2]} <\infty.

This integrability is what permits a law of large numbers to be applied to each matrix entry.

Convergence of the Empirical Matrix

Theorem: If \(X_1,X_2,\ldots\) are iid in fixed dimension \(p\) and \(E[\|X_i\|^2]<\infty\), then \(G_n\xrightarrow{p}Q\). In fact, \(G_n\xrightarrow{a.s.}Q\). These convergences hold entrywise and, because \(p\) is fixed, in any matrix norm.

Proof. For each pair \(j,k\), the \((j,k)\) entry of \(G_n\) is the sample average of the iid random variables \(X_{ij}X_{ik}\). The inequality above shows that these variables have finite absolute expectation, and their expectation is \(Q_{jk}\). The weak law of large numbers therefore gives \((G_n)_{jk}\xrightarrow{p}Q_{jk}\). Since there are only \(p^2\) entries, entrywise convergence in probability implies convergence of the whole matrix in probability: for any \(\epsilon>0\), the probability that the maximum entrywise error exceeds \(\epsilon\) is at most the sum of the \(p^2\) probabilities for individual entries, and that finite sum tends to zero.

For almost-sure convergence, apply the strong law of large numbers to each integrable sequence \(X_{ij}X_{ik}\). Each entry converges to \(Q_{jk}\) almost surely. The intersection of the resulting \(p^2\) probability-one events still has probability one, so all entries converge simultaneously. In fixed dimension, entrywise convergence implies convergence in any matrix norm. For example, the Frobenius norm, the square root of the sum of squared entries, tends to zero when each of its finitely many entries does. This proves both assertions. \(\square\)

The fixed-dimension qualification matters: the finite collection of entries is essential to this argument. It does not, by itself, establish the same matrix-norm conclusion when the number of regressors grows with \(n\).

Worked Example: A Scalar Regressor That Is Zero Sometimes

Let \(p=1\), and suppose \(X_i\) is Bernoulli with \(P(X_i=1)=0.3\) and \(P(X_i=0)=0.7\). Then \(X_i^2=X_i\), so the population Gram matrix is the scalar \(Q=E[X_i^2]=0.3\). The empirical Gram matrix is

G_n=\frac{1}{n}\sum_{i=1}^n X_i^2 =\frac{1}{n}\sum_{i=1}^n X_i.

The law of large numbers gives \(G_n\xrightarrow{a.s.}0.3\), in agreement with the theorem. In one dimension, \(G_n\) has full rank exactly when it is positive, which happens as soon as at least one observed \(X_i\) equals 1. The probability that the first \(n\) observations are all zero is \(0.7^n\), which tends to zero. More directly, the probability of never observing a 1 is \(\lim_{n\to\infty}0.7^n=0\). Thus the scalar design is eventually full rank almost surely, even though some individual observations have a zero regressor.

Positive Definiteness and Eventual Full Rank

Theorem: Under the iid and finite-second-moment assumptions above, if \(Q\) is positive definite, then \(G_n\) is positive definite for all sufficiently large \(n\), almost surely. In particular, the design matrix \(D_n\) has full column rank eventually, almost surely. Consequently, \(P(G_n\text{ is positive definite})\to 1\).

Proof. Since \(Q\) is a fixed symmetric positive-definite matrix, its smallest eigenvalue \(\lambda_{\min}(Q)\) is strictly positive. For any symmetric matrices \(A\) and \(B\), the Rayleigh-quotient characterization of the smallest eigenvalue gives

\lambda_{\min}(A)=\inf_{\|v\|=1}v^{\mathsf T}Av, \qquad |\lambda_{\min}(A)-\lambda_{\min}(B)| \leq \|A-B\|_{\mathrm{op}},

where \(\|\cdot\|_{\mathrm{op}}\) is the operator norm. To see the inequality, for every unit vector \(v\), the absolute difference between \(v^{\mathsf T}Av\) and \(v^{\mathsf T}Bv\) is at most \(\|A-B\|_{\mathrm{op}}\). Taking infima in both directions gives the stated bound. By the almost-sure convergence just proved, \(\|G_n-Q\|_{\mathrm{op}}\to 0\) almost surely. Hence \(\lambda_{\min}(G_n)\to\lambda_{\min}(Q)>0\) almost surely. On every sample path where this convergence holds, there is a finite index after which \(\lambda_{\min}(G_n)>0\), so \(G_n\) is positive definite from then on.

Finally, \(G_n=D_n^{\mathsf T}D_n/n\). For any \(v\), \(v^{\mathsf T}G_nv=\|D_nv\|^2/n\). Thus \(G_n\) is positive definite exactly when \(D_nv\neq 0\) for every nonzero \(v\), which is equivalent to \(D_n\) having full column rank. Almost-sure eventual positive definiteness implies that the probability of positive definiteness tends to one: the events that \(G_n\) is positive definite are increasing in \(n\), because adding rows cannot reduce column rank, and their union has probability one. Therefore their probabilities tend to one. \(\square\)

The theorem gives a sufficient population condition, not a claim that every finite sample is full rank. A small sample can fail to span all \(p\) directions, even when \(Q\) is positive definite. The conclusion is that such failures do not persist as the sample grows.

Worked Example: An Intercept and a Normal Regressor

Let \(Z_i\) be iid \(N(0,1)\), and take \(X_i=(1,Z_i)^{\mathsf T}\). This is the regressor vector for a model with an intercept and one random regressor. Its second moment is finite, and

Q=E \begin{bmatrix} 1 & Z_i\\ Z_i & Z_i^2 \end{bmatrix} = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}.

The empirical matrix is

G_n= \begin{bmatrix} 1 & \bar Z_n\\ \bar Z_n & \frac{1}{n}\sum_{i=1}^n Z_i^2 \end{bmatrix}, \qquad \bar Z_n=\frac{1}{n}\sum_{i=1}^n Z_i.

The strong law gives \(\bar Z_n\to 0\) almost surely and \(\frac{1}{n}\sum_i Z_i^2\to 1\) almost surely, so \(G_n\to Q\) almost surely. The determinant is \(\frac{1}{n}\sum_i Z_i^2-\bar Z_n^2\), the sample variance with divisor \(n\). For \(n\geq 2\), it is positive whenever the observed \(Z_i\)'s are not all equal. Independent continuous normal observations are not all equal with probability one for \(n\geq 2\). Thus this example has full column rank almost surely for every \(n\geq2\), and its limiting matrix is positive definite, as the theorem requires.

Worked Example: A Singular Population Gram Matrix

Let \(U_i\) be iid \(N(0,1)\) and \(X_i=(U_i,2U_i)^{\mathsf T}\). These regressors have finite second moments, but the second coordinate is always twice the first. Since \(E[U_i^2]=1\),

Q=E[X_iX_i^{\mathsf T}] = \begin{bmatrix} 1 & 2\\ 2 & 4 \end{bmatrix}.

The vector \((-2,1)^{\mathsf T}\) is in the null space of \(Q\), so \(Q\) is singular. If \(c_n=\frac{1}{n}\sum_i U_i^2\), then

G_n=c_n \begin{bmatrix} 1 & 2\\ 2 & 4 \end{bmatrix}.

Every \(G_n\) is singular: the two columns of the design matrix are proportional, regardless of the sample size or the value of \(c_n\). Although \(c_n\to1\) almost surely, no amount of sampling creates variation in the direction that distinguishes the two regressors. This illustrates why convergence alone does not guarantee full rank when the population limit is singular.

Interpretation and a Common Pitfall

A positive-definite population Gram matrix means that every nonzero linear combination of the regressors has positive second moment: for each nonzero \(a\), \(E[(a^{\mathsf T}X_i)^2]>0\). The smallest eigenvalue quantifies the least-supported direction. When it is strictly positive, convergence ensures that the empirical matrix eventually retains positive variation in every direction. This is the design-side condition needed for stable identification in fixed-dimensional random-design regression; it is not a result about the convergence of an estimator.

Common mistake: “The empirical Gram matrix converges to \(Q\), so it must eventually have full rank.” That reasoning skips a necessary condition. If \(Q\) is singular, matrices converging to it may remain singular, as in the proportional-regressor example. The correction is to check that \(Q\) is positive definite and use convergence of its smallest eigenvalue. Also, the Gram matrix here is uncentered: replacing it with a sample covariance without accounting for the mean changes the matrix being studied.

Key takeaway: Finite second moments make the entries of \(G_n\) integrable, so the iid laws of large numbers give \(G_n\to Q\). If \(Q\) is positive definite and \(p\) is fixed, the smallest sample eigenvalue is eventually positive almost surely, and the random design eventually has full column rank.

Check Your Understanding

Use the definitions and conditions in this tutorial to answer the following questions.

Why does \(E[\|X_i\|^2]<\infty\) imply that \(E[|X_{ij}X_{ik}|]<\infty\) for every pair of coordinates?
What property of fixed dimension lets entrywise convergence imply convergence of the whole empirical Gram matrix?
State the condition on \(Q\) that guarantees almost-sure eventual full column rank, and explain the role of its smallest eigenvalue.
Can a positive-definite \(Q\) imply that \(D_n\) has full column rank for every \(n\)? Explain.
For \(X_i=(U_i,2U_i)^{\mathsf T}\), identify a nonzero vector in the null space of \(Q\) and explain why increasing \(n\) does not produce full rank.