# IFT 6760A - Winter 2019

Matrix and tensor factorization techniques for machine learning

## Description

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.

*More infos coming soon...*
## Class Info

**When:**
Tuesdays 12:30-2:30PM and Thursdays 11:30-1:30PM

**Where:** (very likely) at Mila (6666 St-Urbain street)

**Instructor:** Guillaume Rabusseau, Office 3151, AndrĂ©-Aisenstadt

**Office hours:** Tuesdays after class

## Evaluation

Class project + Paper presentation + Scribing + Class participation

*(this is subject to change but there will definitely be no closed room exam)*
## Tentative list of topics (to be updated as we go along)

- Linear algebra fundamentals
- Vector spaces, linear maps, matrices, rank, change of basis, Hilbert spaces (orthogonality), etc.
- Matrix decomposition: eigenvalues/eigenvectors, diagonalizability (Jordan canonical form), Gram-Schmidt algorithm, QR decomposition, singular value decomposition.

- Linear algebra and matrix factorization techniques for ML
- Linear algebra is everywhere: PCA, CCA, LLE, ...
- Spectral graph clustering
- Spectral learning of HMMs, PCFGs and related models
- Collaborative filtering, matrix completion and low rank matrix recovery

- Multilinear algebra and tensor factorization techniques for ML:
**Tensors are the new matrices!** (quoting David Steurer)
- Presentation of several tensor decomposition formats: CanDecomp/ParaFac (CP), Tucker, Tensor Train (TT), etc.
- Tensor networks: a unifying tool
- Some tensor decomposition algorithms: alternating least squares, SVD based algorithms (HOSVD, TT-SVD), DMRG like algorithms, etc.
- Tensor method of moments: consistent estimators from observable tensors
- Algorithms for CP decomposition of symmetric tensors: Jenrich's algorithm, tensor power method, sum of squares hierarchy...
- Multilinear extensions: tensor completion, tensor recovery, tensor regression, ...
- Compressing ML models (e.g. NN, MRF) with tensor factorization

## Schedule

## Resources

### Linear Algebra

- Essence of linear algebra video series by Grant Sanderson (3blue1brown): a must watch, both as a refresher and to gain some geometric intuition on linear algebra.
- Matrix Analysis by Horn and Johnson: goes in considerably more depth than what we will need in the course but a standard reference to know about.

### Tensor Decomposition

- Two very good surveys: (Kolda and Bader, 2009), (Grasedyck, Kressner and Tobler, 2013)