Join at slido.com�#3640956

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

3640956

Dimensionality Reduction

Lecture 3

PCA with a review of linear algebra, calculus, and optimization

EECS 189/289, Fall 2026 @ UC Berkeley

Joseph E. Gonzalez and Narges Norouzi

Recap

In Tuesday’s lecture we focused on Nearest Neighbor methods:

• Non-parametric Classification and Regression – use the labels of the k-nearest neighbors to estimate the test point.
• K-means clustering – grouping nearby points.

​

Today we will explore Principal Component Analysis (PCA)

• Dimensionality reduction – we will project high-dimensional data into a descriptive low-dimensional space.
• Parametric method – there will be a fixed set of parameters

​

We will review linear algebra, calculus, and optimization.

​

3640956

Taxonomy of�Machine Learning

Supervised Learning

Labeled Data

Quantitative�Label

Categorical�Label

3640956

Demo

Using PCA and scikit-learn to make sense of congressional votes.

Interpreting the demonstration

How does PCA construct this low-dimensional representation of the data?

3640956

Objective of Dimensionality Reduction

High-dimensional data (many columns) and can be difficult to visualize and model.

• Challenging to plot more than a few dimensions
• Some modeling techniques perform poorly in high-dimensions �(e.g., k-NN and k-Means)

​

3640956

The Curse of Dimensionality

3640956

Objective of Dimensionality Reduction

High-dimensional data (many columns) and can be difficult to visualize and model.

• Challenging to plot more than a few dimensions
• Some modeling techniques perform poorly in high-dimensions �(e.g., k-NN and k-Means)

Often high-dimensional data can be �compressed into a lower dimensional �space with minimal loss of information.�

Dimensionality reduction: take �high-dimensional data and map it to a �lower dimensional space that preserves �as much information as possible.

​

3640956

Formulating the Problem

The Rank of a Matrix

3640956

Simple Example

Suppose I have a large table of random rectangles along with properties of those rectangles:

​

​

​

​

​

​

What is the rank of this dataset?

​

width

height

area

perimeter

diagonal

3640956

What is the rank of the following dataset?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

3640956

Rank of the Rectangles Example

a linear combination of the �other two columns

not a linear combination

not a linear combination

5 columns, rank 4

the perimeter column is redundant, so the matrix is not full rank

How many dimensions (columns) are really needed?

3640956

How many dimensions are needed to fully describe this dataset?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

3640956

Intrinsic Dimension and Matrix Rank

The intrinsic dimension is the minimum number of variables needed to describe the data.

• Unlike rank, intrinsic dimension allows nonlinear relationships between variables.

5 columns, rank 4

the perimeter column is redundant, so the matrix is not full rank

Intrinsic Dimension is 2

every column is determined by w and h alone

Every column of that table is determined by the width w and the height h.

3640956

Real data is rarely exactly low rank

Measure the perimeter with a tape measure instead of computing it, and the exact relationship is destroyed 🡪 the rank returns to 5.

• Small amounts of noise can make data full rank.

Typically, datasets are nearly full rank but are often accurately approximated by a lower dimensional sub-space (close to the intrinsic dimension).

How do we find a lower dimensional representation that �accurately approximates the data?

3640956

Deriving PCA

The input Data Matrix

3640956

Dimensionality reduction as �Matrix Factorization

3640956

Interpretation of Z and W

Each row of W determines the basis of the subspace of X used to approximate the data. (These will become our Principal Components give the opt. problem.)

Each row of Z determines the “mix” of the rows of W used to reconstruct a row in the original data.

3640956

Which of these products can equal X exactly?

🤔

3640956

Suppose 𝐗∈ℝ^(3×3) is a any 3×3 matrix with full rank. Which factorizations could always exactly reconstruct X.

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

3640956

The rank of the product is bounded by k

Among all factorizations of rank k, which one is best?

rank(ZW) ≤ min(rank Z, rank W) ≤ k

• B and D can reproduce X exactly, but achieve no reduction
• A and C cannot (in general), since their inner dimension is smaller than the rank of X

​

3640956

Defining an objective function

X is assumed to be centered

​

that is, the mean of each column has been subtracted.

This is an optimization problem

​

The parameters are Z and W, and there is a single quantity to be minimized. It is the first of many such problems this semester.

3640956

Why we subtract the mean

The best fitting subspace always passes through the mean, �so we subtract the mean first.

3640956

The Factorization is Not Unique

3640956

The Full Optimization Problem

3640956

The Basic Stationary Point Method

• Differentiate with respect to each parameter
• Set the derivatives to zero and solve
• (Optional) verify that second derivative is positive.

This procedure applies when the objective is smooth and the resulting equations can be solved. All conditions hold today, and we obtain an exact solution.

3640956

Case k = 1 (Rank 1 Factorization)

Simplified Loss

3640956

3640956

3640956

The constraint is essential: it is what makes the problem well posed.

3640956

The Method of �Lagrange Multipliers

Gradients of the loss and scaled constraint violation should be parallel!

3640956

A Small Example

​

​

​

​

​

​

​

​

so x = y

3640956

Applying the Method of Lagrange Multipliers

3640956

Applying the Method of Lagrange Multipliers

🤔

What is this?

3640956

What does this equation (Σ𝐰^⊤=𝜆𝐰^⊤) say about w?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

3640956

The Eigenvector Equation

3640956

Subsequent Principal Components

3640956

Computing the Principal Components

U, S, Vt = np.linalg.svd(X, full_matrices=False)

3640956

Returning to the vote data

3640956

Matrix Factorization for �Content Recommendation

• R holds ratings: one row per user, one column per movie, and almost every entry is missing
• Netflix Prize: 8.5 billion user and movie pairs, of which about 1 in 85 was ever rated

Only the observed pairs Ω are part of the loss. �The learned factors are then used to fill in every rating that was never given.

Bonus

Drop unit vector constraint and add a penalty term.

3640956

Summary

Next week we turn to probability!

3640956

Dimensionality Reduction

Lecture 3

Credit: Joseph E. Gonzalez and Narges Norouzi

Reference Book Chapters:

• Linear Algebra, Matrix Calculus, and Eigenvectors: Appendix (A.1, A.3, A.4)
• Lagrange Multipliers: Appendix C
• PCA: Chapter 16.1

Have Fun!!!