IFT 6760A - Winter 2019
Matrix and tensor factorization techniques for machine learning

[new] Notes for lecture 9 on tensors and CP decomposition are available.
[new] Notes for lecture 7-8 on spectral learning of weighted automata are available.
[new] ~15 papers added to the class bibliography (marked with the [new] tag).


The goal of this course is to present an overview of linear and multilinear algebra techniques for designing/analyzing ML algorithms and models, and to engage students with new research in the area.
- Fundamental notions of linear and multilinear algebra.
- Old and new ML methods leveraging matrix and tensor decomposition: PCA/CCA, collaborative filtering, spectral graph clustering, spectral methods for HMM, K-FAC, spectral normalization, tensor method of moments, NN/MRF compression, tensor regression/completion, etc.
- Open problems.

Class Info

When: Tuesdays 12:30-2:30PM and Thursdays 11:30-1:30PM
Where: Mila auditorium, 6650 St-Urbain street
Instructor: Guillaume Rabusseau, Office: 3151.André-Aisenstadt @ UdeM / D.15 @ Mila.
Office hours: Tuesdays after class


Class project (50%) + Paper presentation (30%) + Scribing (10%) + Class participation (10%)

The latex template for scribing can be found in this overleaf project.

Tentative list of topics (to be updated as we go along)


January 8

Class introduction. [slides] [quiz]

January 10 [lecture 1 notes] [latex sources (overleaf)]

Linear algebra refresher.
  • Vector space, subspaces, span, linear independence, basis, orthogonality, etc.
  • The four fundamental spaces of a matrix, matrix rank, rank nullity theorem
Reading suggestions:

January 15 [lecture 2 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • Orthogonality, projections
  • Singular value decomposition
Reading suggestions:

January 17 [lecture 3 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • QR decomposition
  • Basics about matrix inverse and determinant
  • Moore-Penrose pseudo-inverse
  • Eigenvalues / eigenvectors definition
Reading suggestions:

January 22 [lecture 4 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • Diagonalizability, spectral theorem, Schur decomposition, Jordan canonical form
  • Proof of the SVD
Reading suggestions:

January 24 [lecture 5 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • Matrix norms
  • Low rank approximation (Eckart-Young-Mirsky theorem)
  • Variational characterization of eigenvalues (Rayleigh quotient), Min-max theorem
Reading suggestions:

January 29 [lecture 6 notes] [latex sources (overleaf)]

Dimensionality reduction
  • Principal component analysis (PCA)
  • Canonical correlation analysis (CCA)
  • Locally linear embedding (LLE)
Reading suggestions:

January 31 [lecture 7-8 notes] [latex sources (overleaf)]

Spectral learning of HMMs and related models

Reading suggestions:

February 5th

Spectral learning of HMMs and related models (cont'd)

February 7th [lecture notes] [latex sources (overleaf)]

Introduction to tensor decomposition
  • Basic tensor operations, Kronecker product, ...
  • Notions of tensor rank
  • CP and Tucker decomposition
  • Jennrich's algorithm and Alternating Least Squares (ALS) for CP and Tucker decomposition
Reading suggestions:

February 12th

Tensor networks and SVD based tensor decomposition algorithms
  • Introduction to tensor networks
  • Tensor Train (TT), Tensor Ring (TR), Hierarchical Tucker (HT) decomposition
  • SVD based decompostion algorithms for Tucker and TT
Reading suggestions:

February 14th

Guest lecture by Jacob Miller:
  • Tensor Train (TT) decomposition
  • Parametrization of ML models with the TT format
  • DMRG-like algorithms for optimization in TT format
Reading suggestions:

February 19th

More on the tensor train decomposition and tensor networks
  • SVD-based and DMRG-like algorithms for optimization in TT format
  • Beyond TT: PEPS, tensor ring, hierarchical Tucker...
Reading suggestions:

February 21st

Learning latent variable models via tensor decomposition
  • Single topic model and mixture of Gaussians
  • Method of moments and tensor decomposition
  • Power method for matrix and tensor decomposition
Reading suggestions:


Linear Algebra

Tensor Decomposition

Class Bibliography


Spectral Clustering

Spectral Learning

Tensor Decomposition

Tensor Networks

Model Compression

Latent Variable Models

Neural Network Analysis with Tensors

Tensor Completion

Various Applications of Tensor Methods