Linear Regression Using Normal Equation

Problem

Implement linear regression using the Normal Equation: theta = (X^T X)^(-1) X^T * y. Given feature matrix X and target vector y, return the parameter vector theta.

Solution

import numpy as np

def linear_regression_normal_equation(X: list[list[float]], y: list[float]) -> list[float]:
    X = np.array(X, dtype=float)
    y = np.array(y, dtype=float)
    # theta = (X^T X)^(-1) X^T y
    XTX = X.T @ X
    XTy = X.T @ y
    theta = np.linalg.inv(XTX) @ XTy
    # Round to 4 decimal places
    return np.round(theta, 4).tolist()

Explanation

1. Convert inputs to numpy arrays.
2. Compute X^T X (the Gram matrix) and X^T y.
3. Invert X^T X and multiply by X^T y to get the optimal parameter vector.
4. This is the closed-form solution that minimizes the sum of squared residuals.

Complexity

• Time: O(n * f^2 + f^3) where n is the number of samples and f is the number of features
• Space: O(f^2) for the matrix computations