M6-T8 — Principal Component Analysis

Learning objectives

After this lesson, you should be able to:

• Compute the sample covariance of a point set and its principal axes and variances.
• Show that PCA directions are the eigenvectors of the covariance and equal the right singular vectors of the centred data matrix.
• Use the eigenvalue pattern to classify local geometry (plane, line, volume) and to extract surface normals.
• Explain the effects of centring, scaling and outliers, and choose how many components to keep.

Introduction and motivation

A LiDAR scan is an unorganised cloud of thousands of 3D points. To find walls, floors and poles we look at small neighbourhoods and ask: do these points lie on a plane, a line or neither? The eigen-decomposition of the neighbourhood covariance answers that in microseconds, and it is the first step in many scan-matching, mapping and feature-extraction pipelines (point-to-plane ICP needs the normals). The same idea compresses high-dimensional sensor data to the few directions that matter.

The intuition

Centre the data on its mean, then ask: in which direction is the cloud longest? That is the first principal component. In the direction perpendicular to it, in which is it longest? That is the second, and so on. Because variance in direction u is uᵀCu for the covariance C, the answer is the eigenvector of C with the largest eigenvalue, and the eigenvalue is the variance along it.

Geometric and physical interpretation

Geometric view. The covariance ellipse (or ellipsoid) (x − μ)ᵀ C⁻¹ (x − μ) = 1 encloses the cloud; its axes are the principal components and its half-lengths are √λᵢ. Physical view. For a patch of a wall, points scatter along the wall but hardly at all through it, so the thinnest direction is the wall normal. For a rotating 3D scan of a pole, one direction has large spread (its axis) and two have tiny spread.

The mathematics

xᵢ

the data points, i = 1 … N, each a vector in ℝᵈ.

μ

the mean, (1/N) Σ xᵢ.

X̃

the centred data matrix with rows (xᵢ − μ)ᵀ, size N × d.

C

the sample covariance, X̃ᵀX̃/(N − 1), a d × d symmetric positive semi-definite matrix.

vₖ, λₖ

the k-th principal direction (unit eigenvector of C) and its variance.

The covariance and its eigen-decomposition

C = (1/(N−1)) Σᵢ (xᵢ − μ)(xᵢ − μ)ᵀ = V Λ Vᵀ,    λ₁ ≥ λ₂ ≥ … ≥ λd ≥ 0

What it means. The columns of V are the principal axes and the eigenvalues are the variances along them. Because C is symmetric positive semi-definite, the eigenvalues are real and non-negative.

PCA by SVD

X̃ = U Σ Vᵀ   ⇒   C = V (Σ²/(N−1)) Vᵀ,    λₖ = σₖ²/(N−1)

What it means. The right singular vectors of the centred data are the principal axes, and the variances are the squared singular values divided by N − 1. This avoids forming C and keeps accuracy.

Reduction and explained variance

z = Vkᵀ (x − μ)        explained = (λ₁ + … + λₖ)/(λ₁ + … + λd)

What it means. Coordinates in the top k axes, and the fraction of total variance retained. Choosing k so the fraction exceeds a target, say 95 %, gives the best k-dimensional approximation in the least-squares sense.

Centre, form the covariance, take eigenvectors: those are the axes, their eigenvalues the variances. The smallest-variance axis of a patch is its normal.

Step-by-step derivation: why the eigenvectors maximise variance

First component. The variance of the data projected on a unit vector u is

1. Var(u) = (1/(N−1)) Σᵢ (uᵀ(xᵢ − μ))² = uᵀ C u.
2. Maximise uᵀCu subject to uᵀu = 1. With a Lagrange multiplier L = uᵀCu − λ(uᵀu − 1), setting the gradient to zero gives C u = λ u.
3. So a stationary direction is an eigenvector, and there uᵀCu = λ; the maximum is the largest eigenvalue, attained at v₁.

Later components. Maximise uᵀCu over unit vectors perpendicular to v₁; the same argument (and the orthogonality of eigenvectors of a symmetric matrix) gives v₂ with variance λ₂, and so on. The components are uncorrelated: the covariance of the projected data is diag(λ₁, …, λ_d).

Link to the SVD. With X̃ = UΣVᵀ, X̃ᵀX̃ = VΣ²Vᵀ, so C = V Σ²Vᵀ/(N−1): the eigenvectors of C are the right singular vectors, the eigenvalues σ²/(N−1).

Best low-dimensional approximation. By the Eckart-Young theorem, X̃ₖ = Σₖ UₖΣₖVₖᵀ minimises the total squared reconstruction error among all rank-k matrices, and the error is Σ_{i>k} σᵢ²: the discarded variance (times N − 1).

Surface normal. For points on a plane with unit normal n, nᵀ(xᵢ − μ) = 0 for every i, so C n = 0: the normal is the eigenvector for the zero eigenvalue. With noise the smallest eigenvalue is small but non-zero, and its eigenvector is the least-squares normal. Its sign is ambiguous and is fixed by orienting it towards the sensor.

Centring matters. Without subtracting the mean, the first direction mostly points from the origin to the cloud centre, not along the cloud's own spread.

A worked example: a 2D cloud and a 3D plane patch

2D cloud. Points (−2, −1.5), (−1, −0.5), (0, 0), (1, 0.5), (2, 1.5).

• Mean and centring. The mean is (0, 0), so the data is already centred.
• Covariance (N − 1 = 4). Σx² = 10, Σxy = 3 + 0.5 + 0 + 0.5 + 3 = 7, Σy² = 2.25 + 0.25 + 0 + 0.25 + 2.25 = 5. So C = [[2.5, 1.75], [1.75, 1.25]].
• Eigenvalues. Trace 3.75, determinant 3.125 − 3.0625 = 0.0625, so λ = (3.75 ± √(14.0625 − 0.25))/2 = 3.7333, 0.0167.
• Axes. For 3.7333: (C − λI)v = 0 gives v₁ = (0.8174, 0.5760), an angle of arctan(0.576/0.8174) = 35.2°; v₂ = (−0.5760, 0.8174).
• Explained variance. 3.7333/3.75 = 99.6 %: the cloud is essentially one-dimensional along 35.2°.

3D plane patch. Points on z = 0.1x + 0.2y: (0, 0, 0), (1, 0, 0.1), (0, 1, 0.2), (1, 1, 0.3).

• Centre. Mean = (0.5, 0.5, 0.15). Centred points: (−0.5, −0.5, −0.15), (0.5, −0.5, −0.05), (−0.5, 0.5, 0.05), (0.5, 0.5, 0.15).
• Smallest direction. The SVD of the centred 4 × 3 matrix has a smallest singular value of 0 (exactly planar data) with right singular vector ±(−0.1, −0.2, 1)/√1.05 = ±(−0.0976, −0.1952, 0.9759), the plane normal, matching the cross-product calculation in Module 1.
• Planarity. The two other singular values are 1.025 and 1.000 (the in-plane spread), so the pattern is plane-like: σ₃ = 0 against two values near 1.

Robotics application

Surface normals for point-to-plane ICP. For each point, take its k nearest neighbours, compute their covariance, and use the eigenvector of the smallest eigenvalue as the normal; see point cloud preprocessing, ICP fundamentals and LiDAR point clouds.

Feature extraction. The ratios of the three eigenvalues give linearity (λ₁−λ₂)/λ₁, planarity (λ₂−λ₃)/λ₁ and sphericity λ₃/λ₁, which classify edges, planes and clutter; see feature extraction.

Ground and wall removal. A fitted plane through ground points uses the same decomposition; a ground vehicle's tilt comes from that normal. Fitting a plane to GNSS or barometer-checked ground points is common on UAVs; see attitude representations.

Dimensionality reduction. Image descriptors, IMU windows or spectra can be reduced to a handful of principal components before classification, filtering out noise directions.

Engineering implications and limitations

Practical rules

• Always subtract the mean first. Uncentred PCA reports the direction to the data, not along it. The mean of a neighbourhood must be recomputed per patch.
• Use enough neighbours. Three points always make a plane, so normals from tiny neighbourhoods are noise. Typically 10 to 30 points, with a radius matched to the sensor spacing.
• Resolve the normal sign. v₃ and −v₃ are both eigenvectors. Flip the normal so that it points towards the sensor origin.
• Outliers dominate. The covariance squares distances, so one stray point can rotate the axes (see the figure). Use a robust estimator, trim outliers, or RANSAC planes first (see robust optimisation).
• Scale features first. When variables have different units (metres versus radians), standardise to unit variance, otherwise the large-unit variable wins by construction.
• Use the SVD of centred data for accuracy. Forming C squares the condition number; for a thin patch the smallest eigenvalue would be lost in rounding.
• Repeated eigenvalues mean undefined axes. A spherical cloud has no preferred direction and the output axes are arbitrary.

Limits

PCA captures linear, second-order structure only. Curved surfaces, multimodal clusters, or features that matter because they are rare rather than variable are poorly described by principal components.

Common misconceptions

Engineering takeaways

1. PCA axes are the eigenvectors of the covariance of centred data; the eigenvalues are the variances.
2. Equivalently they are the right singular vectors of the centred data matrix, with λ = σ²/(N−1); use the SVD for accuracy.
3. The smallest-variance axis of a point patch is its surface normal; the eigenvalue pattern separates planes, lines and volumes.
4. Choose k components by the explained-variance fraction; the best rank-k approximation is the truncated SVD.
5. Centre the data, scale unlike units, fix signs, and beware outliers.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lecture on PCA and the covariance matrix
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): clustering and data-matrix chapters where PCA is discussed; the site did not load when we last checked
• Mathematics for Machine Learning: chapter 10, Dimensionality Reduction with Principal Component Analysis
• UCSD ECE276A: Sensing and Estimation in Robotics: PCA for surface normals and point-set registration

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Module 6 gave you the tools that describe any matrix: eigenvalues for symmetric ones, the SVD for all. Module 7 turns to the matrices that move robots: rotations and rigid-body transformations, starting with coordinate frames.

Related content

Nothing below is required to finish this lesson.

• Before
  M6-T7: The Moore-Penrose Pseudoinverse

  Build the pseudoinverse from the SVD and use it to solve rank-deficient and underdetermined systems.

• Before
  M6-T5: Singular Value Decomposition

  Write any matrix as rotation, stretch and rotation, and read the geometry from the singular values.

• Lab
  M6-L1: Point Cloud PCA

  Find the surface normal and principal axes of a point cloud with the SVD, and tell planes, edges and volumes apart.