Mathematical Foundations of Machine Learning

Last time

• Last class: Monday October 7, 2024
  • We wrapped up our discussion of RKHS
  • Homework 4 will reinforce the concepts
  • We started going back to matrix concepts
• Today: We will talk about the spectral theorem

• To be effectively prepared for today's class, you should have:
  1. Relaxed a bit over the fall break
  2. Gone over slides
• Logistics: use office hours to prepare for Homework 4
  • Jack Hill office hours: Wednesday 11:30am-12:30pm in TSRB and hybrid
  • Anuvab Sen office hours: Thursday 12pm-1pm in TSRB and hybrid
  • Dr. Bloch: Sunday October 20, 2024 11am-12pm.
• Homework 4: due Sunday October 20.
  • Don't start accumulating delays, homework 5 is coming
  • However, the pace of subsequent homework will be faster (~1/week)

Midterm

• Grading not started
  • We'll get the grades back before the withdrawal date
  • Withdrawal deadline: Saturday October 26, 2024 at 4:00 pm
• Candid feedback I've received
  • Too long given allotted time (5 mins/question)
  • Too different from homework
• Good opportunity to reflect
  • Is your use of additional resources (ChatGPT, StackOverflow, etc.) helping
  • Are you making good use of resources available to you?
    • In-person lecture time
    • Hybrid office hours
    • Q&A on Piazza

Change of basis

• Consider the canonical basis ${\{e_i\}}_{i=1}^n$ for ${\mathbb{R}}^n$; every vector can be viewed as coefficients ${\{{\alpha }_i\}}_{i=1}^n$, $$\mathbf{x}=\sum _{i=1}^n{\alpha }_i{e}_i={\left[\begin{array}{cccc}{\alpha }_1& {\alpha }_2& \cdots & {\alpha }_n\end{array}\right]}^{⊺}$$

• How do we find the representation of $\mathbf{x}$ in another basis ${\{v_i\}}_{i=1}^n$? Write $e_i=\sum _{j=1}^n{\beta }_{ij}{v}_j$

• Regroup the coefficients $$\mathbf{x}=\cdots +\left(\sum _{i=1}^n{\beta }_{ij}{\alpha }_i\right)v_j+\cdots$$

• In matrix form $${\mathbf{x}}_{\text{new}}=\left[\begin{array}{cccc}{\beta }_{11}& {\beta }_{21}& \cdots & {\beta }_{n1}\\ {\beta }_{12}& {\beta }_{22}& \cdots & {\beta }_{n2}\\ ⋮& ⋮& ⋮& ⋮\\ {\beta }_{1n}& {\beta }_{2n}& \cdots & {\beta }_{nn}\end{array}\right]\mathbf{x}$$

Similarity

• A change of basis matrix $\mathbf{P}$ is full rank (basis vectors are linearly independent)

• Any full rank matrix $\mathbf{P}$ can be viewed as a change of basis

• ${\mathbf{P}}^{-1}$ takes you back to the original basis

• Warning: the columns of $\mathbf{P}$ describe the old coordinates as a function of the new ones

• Intuition: similar matrices are the same up to a change of basis

• Not all matrices are diagonalizable!

Spectral theorem

• Note that if $\mathbf{A}=\mathbf{V}\mathbf{D}{\mathbf{V}}^{†}$ then $\mathbf{A}=\sum _{i=1}^n{\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^{†}$

• How about real-valued matrices $\mathbf{A}\in {\mathbb{R}}^{n\times n}$?

Symmetric positive definite matrices

• Convention: ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$

• Variational form of extreme eigenvalues for symmetric positive definite matrices $\mathbf{A}$ $${\lambda }_1=\underset{\mathbf{x}\in {\mathbb{R}}^n:{\Vert \mathbf{x}\Vert }_2=1}{max}{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}=\underset{\mathbf{x}\in {\mathbb{R}}^n}{max}\frac{{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}}{{\Vert \mathbf{x}\Vert }_2^2}{\lambda }_n=\underset{\mathbf{x}\in {\mathbb{R}}^n:{\Vert \mathbf{x}\Vert }_2=1}{min}{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}=\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}\frac{{\mathbf{x}}^{⊺}\mathbf{A}\mathbf{x}}{{\Vert \mathbf{x}\Vert }_2^2}$$

System of symmetric definite equations

• Consider the system $\mathbf{y}=\mathbf{A}\mathbf{x}$ with $\mathbf{A}$ symmetric positive definite

• Assume that there exists some observation error $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{e}$
  • $\mathbf{e}$ is unknown
  • we try to reconstruct $\mathbf{x}$ as $\tilde{\mathbf{x}}$ by applying ${\mathbf{A}}^{-1}$

• What about the average case?

Next time

• Next class: Monday October 21, 2024

• To be effectively prepared for next class, you should:
  1. Go over today's slides and read associated lecture notes here
  2. Submit Homework 4 on Gradescope
• Optional
  • Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)