Algorithmic Aspects of Machine Learning
Ankur Moitra@ Draft date March 30 2014
Contents
Contents
1
Preface
3
1Introduction
2 Nonnegative Matrix Factorization 5
2.1 Introduction . 52.2 Algebraic Algorithms 102.3 Stability and Separability 152.4 Topic Models 19
3 Tensor Methods 25
3.1 Basics253.2 Perturbation Bounds 303.4Community Detection 3.3 Phylogenetic Trees and HMMs . 343.5 Extensions to Mixed Models 40443.6 Independent Component Analysis 50
4 Sparse Recovery 53
4.1 Basics 534.2 Uniqueness and Uncertainty Principles 564.3 Pursuit Algorithms 59
ii CONTENTS
4.4 Prony’s Method 614.5Compressed Sensing 9
5 Dictionary Learning 71
5.1 Background 715.2 Full Rank Dictionaries5.3 Overplete Dictionaries 77
6 Gaussian Mixture Models 88
6.1 History. 886.2 Clustering-Based Algorithms . 866.3Discussion of Density Estimation 896.4 Clustering-Free Algorithms . 916.5 A Univariate Algorithm 966.6A View from Algebraic Geometry 101
7Matrix Completion 105
7.1 Background 1057.2Nuclear Norm 1077.3 Quantum Golfing 111
Bibliography 115
Preface
The monograph is based on the class “18.S996: Algorithmic Aspects of MachineLearning" taught at MIT in Fall 2013. Thanks to the scribes Adam Hesterberg.lary Finucane Matthew Johnson Kayhan Batmanghelich Gautam Kamath George Adrian Vladu Matt Coudron Jan-Christian Hitter Henry Yuen Yufei Zhao Hi-Chen Pratiksha Thaker Mohammad Bavarian Vlad Firoiu Madalina Persu CameronMusco Christopher Musco Jing Lin Timothy Chu Yin-Tat Lee Josh Alman Nathan Pinsker and Adam Bouland.
CONTENTS
