Matrix and tensor factorization techniques for machine learning

- 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.

- 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

Linear algebra refresher.

- Vector space, subspaces, span, linear independence, basis, orthogonality, etc.
- The four fundamental spaces of a matrix, matrix rank, rank nullity theorem

- Linear Algebra done Right (abridged), Chapters 1, 2 and 3.{A,B,C}
- Essence of linear algebra videos, episodes 1-4, (5,6), 7
- Lecture notes on linear algebra by David Lerner, chapter 10-15

Linear algebra refresher (cont'd).

- Orthogonality, projections
- Singular value decomposition

- Linear Algebra done Right (abridged), chapter 6
- Lecture notes on linear algebra by David Lerner, chapter 17-20

Linear algebra refresher (cont'd).

- QR decomposition
- Basics about matrix inverse and determinant
- Moore-Penrose pseudo-inverse
- Eigenvalues / eigenvectors definition

- Essence of linear algebra videos, episodes 5, 6, 12, 13
- Lecture notes on linear algebra by David Lerner, chapters 7, 8, 16
- Notes on the Moore-Penrose pseudo-inverse from UCLA linear algebra and application course (Math 33A)
- Linear Algebra done Right (abridged), chapters 3.D and 5

Linear algebra refresher (cont'd).

- Diagonalizability, spectral theorem, Schur decomposition, Jordan canonical form
- Proof of the SVD

- Sections 2.1, 2.2 and 3 in ECE 712 Course Notes by Prof. James Reilly.
- Lecture 3 and Lecture 5 notes from ENGG 5781 Matrix Analysis and Computations course by Prof. Wing-Kin (Ken) Ma.

Linear algebra refresher (cont'd).

- Matrix norms
- Low rank approximation (Eckart-Young-Mirsky theorem)
- Variational characterization of eigenvalues (Rayleigh quotient), Min-max theorem

- Sections 2.3 and 3.7 in ECE 712 Course Notes by Prof. James Reilly.
- Lecture 4 notes from ENGG 5781 Matrix Analysis and Computations course by Prof. Wing-Kin (Ken) Ma.

Dimensionality reduction

- Principal component analysis (PCA)
- Canonical correlation analysis (CCA)
- Locally linear embedding (LLE)

- A Hitchhiker’s Guide to PCA and CCA by Karl Stratos
- An Introduction to Locally Linear Embedding, L. K. Saul and S. T. Roweis
- Appendix E in Bishop's book for a refresher on Lagrange multipliers

Spectral learning of HMMs and related models

Reading suggestions:

Reading suggestions:

- Spectral Learning of Weighted Automata: A Forward-Backward Perspective (Balle et al., 2014)
- A Spectral Algorithm for Learning Hidden Markov Models (Hsu et al, 2009)
- Slides (sections 1 and 2) of the EMNLP tutorial on spectral learning for weighted automata from B. Balle, A. Quattoni and X. Carreras
- Karl Stratos' slides from his course on Spectral Techniques for Machine Learning at TTIC.

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

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

- (Kolda and Bader, 2009), sections 1,2 and 3.
- Introduction to Tensor Decompositions and their Applications in Machine Learning, focus on sections 3 and 4.1

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

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

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...

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

- Tensor decompositions for learning latent variable models (Anandkumar et al., 2014)
- Talk from Animashree Anandkumar at the Simons institute, slides from Daniel Hsu and another deck of slides from Sham Kakade.

- The matrix cookbook: a very useful collection of matrix identities
- 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.
- Gilbert Strang's Linear Algebra course from MIT opencourseware.
- Linear Algebra done Right (abridged)
- 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.
- Some lecure notes I used for the preparation of the Linear Algebra refresher lectures:
- Lecture notes on linear algebra by Prof. David Lerner from University of Kansas
- ENGG 5781 Matrix Analysis and Computations course by Prof. Wing-Kin (Ken) Ma at the Chines University of Hong-Kong
- ECE 712 Course Notes by Prof. James Reilly at McMaster University.
- Numerical Methods for Solving Large Scale Eigenvalue Problems course by Prof. Peter Arbenz at ETH Zürich.

- Two surveys:
- (Kolda and Bader, 2009): very good introductory survey
- (Grasedyck, Kressner and Tobler, 2013): contains a long list of references and pointers

- Multi-View Regression via Canonical Correlation Analysis (Kakade and Foster, 2007)
- Deep Canonical Correlation Analysis (Andrew et al., 2013)
- Multi-View Clustering via Canonical Correlation Analysis (Chaudhuri et al., 2009)
- Beyond CCA: Moment Matching for Multi-View Models (Podosinnikova et al., 2016)
- Tensor Canonical Correlation Analysis for Multi-view Dimension Reduction (Luo et al., 2015)
- [new] A statistical model for tensor PCA (Richard and Montanari, 2014)
- [new] Tensor Subspace Analysis (He et al., 2006)
- [new] Multilinear independent components analysis (Vasilescu and Terzopoulos, 2005)

- A Tutorial on Spectral Clustering (von Luxburg, 2007)
- On Spectral Clustering: Analysis and an algorithm (Ng, Jordan and Weiss, 2002)
- [new] Tensor Spectral Clustering for Partitioning Higher-order Network Structures (Benson et al, 2015)

- Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning (Rabusseau et al., 2018)
- Local loss optimization in operator models: A new insight into spectral learning (Balle et al., 2012)
- Spectral Learning of Sequence Taggers over Continuous Sequences (Recasens and Quattoni, 2013)
- Spectral Learning of Latent-Variable PCFGs (Cohen et al., 2012)
- Closing the Learning-Planning Loop with Predictive State Representations (Boots et al, 2011)
- Completing State Representations using Spectral Learning (Jiang et al., 2018)
- Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices (Kandasamy et al., 2016)
- [new] Efficient Learning and Planning with Compressed Predictive States (Hamilton et al., 2014)

- Polynomial-time Tensor Decompositions with Sum-of-Squares (Ma et al., 2016)
- Tensor Factorization via Matrix Factorization (Kuleshov et al., 2015)
- On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm (Imaizumi et al., 2017)
- Most Tensor Problems are NP-hard (Hillar and Lim, 2013)
- Tensor Decompositions via Two-Mode Higher-Order SVD (Wang and Song, 2017)
- Spectral tensor-train decomposition (Bigoni et al., 2014)
- Statistical mechanics of low-rank tensor decomposition (Kadmon and Ganglui 2018)

- Supervised Learning with Quantum-Inspired Tensor Networks (Stoudenmire and Schwab, 2016)
- Exponential Machines (Novikov et al., 2016)
- Learning Relevant Features of Data with Multi-scale Tensor Networks (Stoudenmire, 2018)
- Unsupervised Generative Modeling Using Matrix Product States (Han et al., 2017)
- Supervised learning with generalized tensor networks (Glasser et al., 2018)
- Duality of Graphical Models and Tensor Networks (Robeva and Seigal, 2017)
- Spectral Methods from Tensor Networks (Moitra and Wein, 2019)
- [new] Tensor Ring Decomposition (Zhao et al., 2016)

- Tensorizing Neural Networks (Novikov et al, 2015)
- Tensor-Train Recurrent Neural Networks for Video Classification (Yang et al., 2017)
- Learning compact recurrent neural networks with block-term tensor decomposition (Ye et al., 2018)
- Putting MRFs on a Tensor Train (Novikov et al., 2014)

- Tensor decompositions for learning latent variable models (Anandkumar et al., 2014)
- [new] Provable tensor methods for learning mixtures of generalized linear models (Sedghi et al., 2016)
- [new] Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods (Janzamin et al., 2015)
- [new] Tensor Analyzers (Tang et al., 2013)

- Expressive power of recurrent neural networks (Khrulkov et al., 2018)
- Generalized Tensor Models for Recurrent Neural Networks (Khrulov et al., 2019)
- On the Expressive Power of Deep Learning: A Tensor Analysis (Cohen et al., 2016)

- Tensor completion for estimating missing values in visual data (Liu et al., 2013)
- Low-rank tensor completion by Riemannian optimization (Kressner et al., 2014)
- [new] A Three-Way Model for Collective Learning on Multi-Relational Data (Nickel et al.. 2011)
- [new] Canonical Tensor Decomposition for Knowledge Base Completion (Lacroix et al., 2018)
- [new] SimplE Embedding for Link Prediction in Knowledge Graphs (Kazemi and Poole, 2018)
- [new] Efficient Low Rank Tensor Ring Completion (Wang et al., 2017)

- Clustering Patients with Tensor Decomposition (Ruffini et al., 2017)
- Higher-Order Partial Least Squares (HOPLS): A Generalized Multi-Linear Regression Method (Zhao et al., 2013)
- Fast Multivariate Spatio-Temporal Analysis via Low-Rank Tensor Learning (Bahadori et al., 2014)

- Neural Word Embedding as Implicit Matrix Factorization (Levi and Goldberg, 2014)
- Understanding Composition of Word Embeddings via Tensor Decomposition (Frandsen and Ge, 2019)
- Incremental Truncated LSTD (Gehring et al., 2016)
- Boosted Sparse and Low-Rank Tensor Regression (He et. al, 2018)
- Learning from Multiway Data: Simple and Efficient Tensor Regression (Yu and Liu, 2016)
- Multi-Dimensional Causal Discovery (Schaechtle et al., 2013)
- Learning to Reason with Third-Order Tensor Product (Schlag and Schmidhuber, 2018)
- [new] Optimizing Neural Networks with Kronecker-factored Approximate Curvature (Martens and Grosse,2015)
- [new] Fast Approximate Natural Gradient Descent in a Kronecker Factored Eigenbasis (George et al., 2018)
- [new] Spectral Normalization for Generative Adversarial Networks (Miyaot et al., 2018)
- [new] Multilinear PageRank (Gleich et al., 2015)
- [new] Multilinear Dynamical Systems for Tensor Time Series