Compute Covariance Matrix

Linear Algebra · Data Processing

Easy

Problem

Theory

A covariance matrix captures how multiple variables change together. For a dataset with D features, the covariance matrix is a D \times D symmetric matrix where each entry (i, j) represents the covariance between feature i and feature j. The diagonal entries contain the variances of individual features.

Why Covariance Matters

Understanding Relationships: Covariance reveals whether variables move together (positive covariance), move oppositely (negative covariance), or are independent (zero covariance).

Dimensionality Reduction: Principal Component Analysis (PCA) uses the covariance matrix eigendecomposition to find directions of maximum variance.

Multivariate Statistics: Many statistical tests and models assume multivariate normal distributions characterized by mean vectors and covariance matrices.

Portfolio Theory: In finance, the covariance matrix of asset returns determines portfolio risk and optimal allocation strategies.

Mathematical Definition

For a dataset X with N samples and D features, the covariance between features i and j is:

\text{Cov}(X_i, X_j) = \frac{1}{N-1} \sum_{k=1}^{N} (x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)

Where:

• x_{ki} is the value of feature i for sample k
• \bar{x}_i is the mean of feature i across all samples
• N-1 is used for unbiased estimation (Bessel's correction)

Special case - Variance: When i = j:

\text{Var}(X_i) = \text{Cov}(X_i, X_i) = \frac{1}{N-1} \sum_{k=1}^{N} (x_{ki} - \bar{x}_i)^2

Matrix Formulation

Given a centered data matrix \tilde{X} (where each column has mean zero):

\Sigma = \frac{1}{N-1} \tilde{X}^T \tilde{X}

Steps to compute:

1. Compute the mean of each feature (column)
2. Subtract the mean from each column to center the data
3. Compute \tilde{X}^T \tilde{X} (matrix multiplication)
4. Divide by N-1

Properties of Covariance Matrices

Symmetry: \Sigma_{ij} = \Sigma_{ji} because \text{Cov}(X_i, X_j) = \text{Cov}(X_j, X_i)

Positive Semi-Definite: For any vector v, v^T \Sigma v \geq 0. This means all eigenvalues are non-negative.

Diagonal Elements: Always non-negative (variances cannot be negative)

Dimensions: For D features, the matrix is D \times D with D(D+1)/2 unique values

Interpreting Covariance Values

Positive covariance (\Sigma_{ij} > 0):

• When feature i increases, feature j tends to increase
• Example: Height and weight in humans

Negative covariance (\Sigma_{ij} < 0):

• When feature i increases, feature j tends to decrease
• Example: Study hours and exam errors

Zero covariance (\Sigma_{ij} = 0):

• No linear relationship between features i and j
• Note: Does not imply independence (could have non-linear relationships)

Magnitude interpretation:

• Covariance magnitude depends on variable scales
• Variables measured in large units have large covariances
• For scale-independent comparison, use correlation instead

Sample vs Population Covariance

Population covariance (divide by N):

• Used when you have the entire population
• Gives the true covariance parameter

\Sigma_{pop} = \frac{1}{N} \sum_{k=1}^{N} (x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)

Sample covariance (divide by N-1):

• Used when data is a sample from a larger population
• Bessel's correction produces an unbiased estimator
• More commonly used in practice

\Sigma_{sample} = \frac{1}{N-1} \sum_{k=1}^{N} (x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)

Worked Example

Dataset (3 samples, 2 features: Height in cm and Weight in kg):

• Sample 1: Height = 170, Weight = 65
• Sample 2: Height = 180, Weight = 75
• Sample 3: Height = 175, Weight = 70

Step 1 - Calculate means:

\bar{Height} = \frac{170 + 180 + 175}{3} = 175

\bar{Weight} = \frac{65 + 75 + 70}{3} = 70

Step 2 - Center the data (subtract means):

• Sample 1: Height - 175 = -5, Weight - 70 = -5
• Sample 2: Height - 175 = 5, Weight - 70 = 5
• Sample 3: Height - 175 = 0, Weight - 70 = 0

Step 3 - Compute covariances:

\text{Var(Height)} = \frac{(-5)^2 + 5^2 + 0^2}{3-1} = \frac{50}{2} = 25

\text{Var(Weight)} = \frac{(-5)^2 + 5^2 + 0^2}{3-1} = \frac{50}{2} = 25

\text{Cov(Height, Weight)} = \frac{(-5)(-5) + (5)(5) + (0)(0)}{3-1} = \frac{50}{2} = 25

Step 4 - Assemble the covariance matrix:

\Sigma = \begin{bmatrix} 25 & 25 \\ 25 & 25 \end{bmatrix}

Interpretation: Perfect positive covariance - height and weight move together proportionally in this dataset.

Covariance vs Correlation

Covariance is scale-dependent:

• Height in cm vs meters gives different covariance values
• Hard to compare covariances across different variable pairs

Correlation is normalized covariance:

\rho_{ij} = \frac{\text{Cov}(X_i, X_j)}{\sigma_i \sigma_j}

• Always between -1 and +1
• Scale-independent
• Easier to interpret and compare

Numerical Stability Considerations

Catastrophic cancellation: When values are large but differences are small, floating-point precision can cause errors. Computing (x - \bar{x}) for large x and \bar{x} may lose significant digits.

Two-pass vs one-pass algorithms:

• Two-pass: First compute means, then compute covariances (more stable)
• One-pass: Update running statistics (faster but less stable)

Welford's algorithm: Numerically stable online algorithm for computing variance/covariance incrementally

Where Covariance Matrices Show Up

• Principal Component Analysis (PCA): Eigendecomposition of the covariance matrix finds principal components

• Linear Discriminant Analysis (LDA): Uses within-class and between-class covariance matrices

• Gaussian Mixture Models: Each component has its own mean and covariance matrix

• Multivariate Normal Distribution: Fully specified by mean vector \mu and covariance matrix \Sigma

• Mahalanobis Distance: Uses inverse covariance matrix to measure distances accounting for correlations

• Kalman Filters: Track state covariance through prediction and update steps

• Portfolio Optimization: Mean-variance optimization requires the covariance matrix of asset returns

• Whitening/Decorrelation: Transform data to have identity covariance matrix

• Regularization: Ridge regression, Tikhonov regularization add to diagonal of covariance matrix

• Feature Selection: High covariance between features indicates redundancy

Examples

Hints

1. Use X - np.mean(X, axis=0) to center every feature.
2. Use centered.T @ centered before dividing by X.shape[0] - 1.

Requirements

• Center each feature independently
• Divide by N minus 1 for sample covariance
• Do not use np.cov
• Return a NumPy array of shape (D,D)

Constraints

• X is a rectangular numeric list with shape (N,D)
• 2 \le N \le 10{,}000
• Use NumPy only

Starter Code

import numpy as np

def covariance_matrix(X: list) -> np.ndarray:
    """
    Returns the covariance matrix as a NumPy array.
    """
    # Write code here
    pass

Test Cases