Linear Algebra and Optimization for Machine Learning: A Textbook

Contents
Preface
Acknowledgments
Author Biography
1 Linear Algebra and Optimization: An Introduction
	1.1 Introduction
	1.2 Scalars, Vectors, and Matrices
		1.2.1 Basic Operations with Scalars and Vectors
		1.2.2 Basic Operations with Vectors and Matrices
		1.2.3 Special Classes of Matrices
		1.2.4 Matrix Powers, Polynomials, and the Inverse
		1.2.5 The Matrix Inversion Lemma: Inverting the Sum of Matrices
		1.2.6 Frobenius Norm, Trace, and Energy
	1.3 Matrix Multiplication as a Decomposable Operator
		1.3.1 Matrix Multiplication as Decomposable Row and ColumnOperators
		1.3.2 Matrix Multiplication as Decomposable Geometric Operators
	1.4 Basic Problems in Machine Learning
		1.4.1 Matrix Factorization
		1.4.2 Clustering
		1.4.3 Classification and Regression Modeling
		1.4.4 Outlier Detection
	1.5 Optimization for Machine Learning
		1.5.1 The Taylor Expansion for Function Simplification
		1.5.2 Example of Optimization in Machine Learning
		1.5.3 Optimization in Computational Graphs
	1.6 Summary
	1.7 Further Reading
	1.8 Exercises
2 Linear Transformations and Linear Systems
	2.1 Introduction
		2.1.1 What Is a Linear Transform?
	2.2 The Geometry of Matrix Multiplication
	2.3 Vector Spaces and Their Geometry
		2.3.1 Coordinates in a Basis System
		2.3.2 Coordinate Transformations Between Basis Sets
		2.3.3 Span of a Set of Vectors
		2.3.4 Machine Learning Example: Discrete Wavelet Transform
		2.3.5 Relationships Among Subspaces of a Vector Space
	2.4 The Linear Algebra of Matrix Rows and Columns
	2.5 The Row Echelon Form of a Matrix
		2.5.1 LU Decomposition
		2.5.2 Application: Finding a Basis Set
		2.5.3 Application: Matrix Inversion
		2.5.4 Application: Solving a System of Linear Equations
	2.6 The Notion of Matrix Rank
		2.6.1 Effect of Matrix Operations on Rank
	2.7 Generating Orthogonal Basis Sets
		2.7.1 Gram-Schmidt Orthogonalization and QR Decomposition
		2.7.2 QR Decomposition
		2.7.3 The Discrete Cosine Transform
	2.8 An Optimization-Centric View of Linear Systems
		2.8.1 Moore-Penrose Pseudoinverse
		2.8.2 The Projection Matrix
	2.9 Ill-Conditioned Matrices and Systems
	2.10 Inner Products: A Geometric View
	2.11 Complex Vector Spaces
		2.11.1 The Discrete Fourier Transform
	2.12 Summary
	2.13 Further Reading
	2.14 Exercises
3 Eigenvectors and Diagonalizable Matrices
	3.1 Introduction
	3.2 Determinants
	3.3 Diagonalizable Transformations and Eigenvectors
		3.3.1 Complex Eigenvalues
		3.3.2 Left Eigenvectors and Right Eigenvectors
		3.3.3 Existence and Uniqueness of Diagonalization
		3.3.4 Existence and Uniqueness of Triangulization
		3.3.5 Similar Matrix Families Sharing Eigenvalues
		3.3.6 Diagonalizable Matrix Families Sharing Eigenvectors
		3.3.7 Symmetric Matrices
		3.3.8 Positive Semidefinite Matrices
		3.3.9 Cholesky Factorization: Symmetric LU Decomposition
	3.4 Machine Learning and Optimization Applications
		3.4.1 Fast Matrix Operations in Machine Learning
		3.4.2 Examples of Diagonalizable Matrices in Machine Learning
		3.4.3 Symmetric Matrices in Quadratic Optimization
		3.4.4 Diagonalization Application: Variable Separationfor Optimization
		3.4.5 Eigenvectors in Norm-Constrained Quadratic Programming
	3.5 Numerical Algorithms for Finding Eigenvectors
		3.5.1 The QR Method via Schur Decomposition
		3.5.2 The Power Method for Finding Dominant Eigenvectors
	3.6 Summary
	3.7 Further Reading
	3.8 Exercises
4 Optimization Basics: A Machine Learning View
	4.1 Introduction
	4.2 The Basics of Optimization
		4.2.1 Univariate Optimization
			4.2.1.1 Why We Need Gradient Descent
			4.2.1.2 Convergence of Gradient Descent
			4.2.1.3 The Divergence Problem
		4.2.2 Bivariate Optimization
		4.2.3 Multivariate Optimization
	4.3 Convex Objective Functions
	4.4 The Minutiae of Gradient Descent
		4.4.1 Checking Gradient Correctness with Finite Differences
		4.4.2 Learning Rate Decay and Bold Driver
		4.4.3 Line Search
			4.4.3.1 Binary Search
			4.4.3.2 Golden-Section Search
			4.4.3.3 Armijo Rule
		4.4.4 Initialization
	4.5 Properties of Optimization in Machine Learning
		4.5.1 Typical Objective Functions and Additive Separability
		4.5.2 Stochastic Gradient Descent
		4.5.3 How Optimization in Machine Learning Is Different
		4.5.4 Tuning Hyperparameters
		4.5.5 The Importance of Feature Preprocessing
	4.6 Computing Derivatives with Respect to Vectors
		4.6.1 Matrix Calculus Notation
		4.6.2 Useful Matrix Calculus Identities
			4.6.2.1 Application: Unconstrained Quadratic Programming
			4.6.2.2 Application: Derivative of Squared Norm
		4.6.3 The Chain Rule of Calculus for Vectored Derivatives
			4.6.3.1 Useful Examples of Vectored Derivatives
	4.7 Linear Regression: Optimization with Numerical Targets
		4.7.1 Tikhonov Regularization
			4.7.1.1 Pseudoinverse and Connections to Regularization
		4.7.2 Stochastic Gradient Descent
		4.7.3 The Use of Bias
			4.7.3.1 Heuristic Initialization
	4.8 Optimization Models for Binary Targets
		4.8.1 Least-Squares Classification: Regression on Binary Targets
			4.8.1.1 Why Least-Squares Classification Loss Needs Repair
		4.8.2 The Support Vector Machine
			4.8.2.1 Computing Gradients
			4.8.2.2 Stochastic Gradient Descent
		4.8.3 Logistic Regression
			4.8.3.1 Computing Gradients
			4.8.3.2 Stochastic Gradient Descent
		4.8.4 How Linear Regression Is a Parent Problem in MachineLearning
	4.9 Optimization Models for the MultiClass Setting
		4.9.1 Weston-Watkins Support Vector Machine
			4.9.1.1 Computing Gradients
		4.9.2 Multinomial Logistic Regression
			4.9.2.1 Computing Gradients
			4.9.2.2 Stochastic Gradient Descent
	4.10 Coordinate Descent
		4.10.1 Linear Regression with Coordinate Descent
		4.10.2 Block Coordinate Descent
		4.10.3 K-Means as Block Coordinate Descent
	4.11 Summary
	4.12 Further Reading
	4.13 Exercises
5 Advanced Optimization Solutions
	5.1 Introduction
	5.2 Challenges in Gradient-Based Optimization
		5.2.1 Local Optima and Flat Regions
		5.2.2 Differential Curvature
			5.2.2.1 Revisiting Feature Normalization
		5.2.3 Examples of Difficult Topologies: Cliffs and Valleys
	5.3 Adjusting First-Order Derivatives for Descent
		5.3.1 Momentum-Based Learning
		5.3.2 AdaGrad
		5.3.3 RMSProp
		5.3.4 Adam
	5.4 The Newton Method
		5.4.1 The Basic Form of the Newton Method
		5.4.2 Importance of Line Search for Non-quadratic Functions
		5.4.3 Example: Newton Method in the Quadratic Bowl
		5.4.4 Example: Newton Method in a Non-quadratic Function
	5.5 Newton Methods in Machine Learning
		5.5.1 Newton Method for Linear Regression
		5.5.2 Newton Method for Support-Vector Machines
		5.5.3 Newton Method for Logistic Regression
		5.5.4 Connections Among Different Models and Unified Framework
	5.6 Newton Method: Challenges and Solutions
		5.6.1 Singular and Indefinite Hessian
		5.6.2 The Saddle-Point Problem
		5.6.3 Convergence Problems and Solutions with Non-quadraticFunctions
			5.6.3.1 Trust Region Method
	5.7 Computationally Efficient Variations of Newton Method
		5.7.1 Conjugate Gradient Method
		5.7.2 Quasi-Newton Methods and BFGS
	5.8 Non-differentiable Optimization Functions
		5.8.1 The Subgradient Method
			5.8.1.1 Application: L1-Regularization
			5.8.1.2 Combining Subgradients with Coordinate Descent
		5.8.2 Proximal Gradient Method
			5.8.2.1 Application: Alternative for L1-RegularizedRegression
		5.8.3 Designing Surrogate Loss Functions for CombinatorialOptimization
			5.8.3.1 Application: Ranking Support Vector Machine
		5.8.4 Dynamic Programming for Optimizing Sequential Decisions
			5.8.4.1 Application: Fast Matrix Multiplication
	5.9 Summary
	5.10 Further Reading
	5.11 Exercises
6 Constrained Optimization and Duality
	6.1 Introduction
	6.2 Primal Gradient Descent Methods
		6.2.1 Linear Equality Constraints
			6.2.1.1 Convex Quadratic Program with Equality Constraints
			6.2.1.2 Application: Linear Regression with EqualityConstraints
			6.2.1.3 Application: Newton Method with EqualityConstraints
		6.2.2 Linear Inequality Constraints
			6.2.2.1 The Special Case of Box Constraints
			6.2.2.2 General Conditions for Projected Gradient Descentto Work
			6.2.2.3 Sequential Linear Programming
		6.2.3 Sequential Quadratic Programming
	6.3 Primal Coordinate Descent
		6.3.1 Coordinate Descent for Convex Optimization Over Convex Set
		6.3.2 Machine Learning Application: Box Regression
	6.4 Lagrangian Relaxation and Duality
		6.4.1 Kuhn-Tucker Optimality Conditions
		6.4.2 General Procedure for Using Duality
			6.4.2.1 Inferring the Optimal Primal Solution from Optimal Dual Solution
		6.4.3 Application: Formulating the SVM Dual
			6.4.3.1 Inferring the Optimal Primal Solution from Optimal Dual Solution
		6.4.4 Optimization Algorithms for the SVM Dual
			6.4.4.1 Gradient Descent
			6.4.4.2 Coordinate Descent
		6.4.5 Getting the Lagrangian Relaxation of Unconstrained Problems
			6.4.5.1 Machine Learning Application: Dual of Linear Regression
	6.5 Penalty-Based and Primal-Dual Methods
		6.5.1 Penalty Method with Single Constraint
		6.5.2 Penalty Method: General Formulation
		6.5.3 Barrier and Interior Point Methods
	6.6 Norm-Constrained Optimization
	6.7 Primal Versus Dual Methods
	6.8 Summary
	6.9 Further Reading
	6.10 Exercises
7 Singular Value Decomposition
	7.1 Introduction
	7.2 SVD: A Linear Algebra Perspective
		7.2.1 Singular Value Decomposition of a Square Matrix
		7.2.2 Square SVD to Rectangular SVD via Padding
		7.2.3 Several Definitions of Rectangular Singular Value Decomposition
		7.2.4 Truncated Singular Value Decomposition
			7.2.4.1 Relating Truncation Loss to Singular Values
			7.2.4.2 Geometry of Rank-k Truncation
			7.2.4.3 Example of Truncated SVD
		7.2.5 Two Interpretations of SVD
		7.2.6 Is Singular Value Decomposition Unique?
		7.2.7 Two-Way Versus Three-Way Decompositions
	7.3 SVD: An Optimization Perspective
		7.3.1 A Maximization Formulation with Basis Orthogonality
		7.3.2 A Minimization Formulation with Residuals
		7.3.3 Generalization to Matrix Factorization Methods
		7.3.4 Principal Component Analysis
	7.4 Applications of Singular Value Decomposition
		7.4.1 Dimensionality Reduction
		7.4.2 Noise Removal
		7.4.3 Finding the Four Fundamental Subspaces in Linear Algebra
		7.4.4 Moore-Penrose Pseudoinverse
			7.4.4.1 Ill-Conditioned Square Matrices
		7.4.5 Solving Linear Equations and Linear Regression
		7.4.6 Feature Preprocessing and Whitening in Machine Learning
		7.4.7 Outlier Detection
		7.4.8 Feature Engineering
	7.5 Numerical Algorithms for SVD
	7.6 Summary
	7.7 Further Reading
	7.8 Exercises
8 Matrix Factorization
	8.1 Introduction
	8.2 Optimization-Based Matrix Factorization
		8.2.1 Example: K-Means as Constrained Matrix Factorization
	8.3 Unconstrained Matrix Factorization
		8.3.1 Gradient Descent with Fully Specified Matrices
		8.3.2 Application to Recommender Systems
			8.3.2.1 Stochastic Gradient Descent
			8.3.2.2 Coordinate Descent
			8.3.2.3 Block Coordinate Descent: Alternating Least Squares
	8.4 Nonnegative Matrix Factorization
		8.4.1 Optimization Problem with Frobenius Norm
			8.4.1.1 Projected Gradient Descent with Box Constraints
		8.4.2 Solution Using Duality
		8.4.3 Interpretability of Nonnegative Matrix Factorization
		8.4.4 Example of Nonnegative Matrix Factorization
		8.4.5 The I-Divergence Objective Function
	8.5 Weighted Matrix Factorization
		8.5.1 Practical Use Cases of Nonnegative and Sparse Matrices
		8.5.2 Stochastic Gradient Descent
			8.5.2.1 Why Negative Sampling Is Important
		8.5.3 Application: Recommendations with Implicit Feedback Data
		8.5.4 Application: Link Prediction in Adjacency Matrices
		8.5.5 Application: Word-Word Context Embedding with GloVe
	8.6 Nonlinear Matrix Factorizations
		8.6.1 Logistic Matrix Factorization
			8.6.1.1 Gradient Descent Steps for Logistic MatrixFactorization
		8.6.2 Maximum Margin Matrix Factorization
	8.7 Generalized Low-Rank Models
		8.7.1 Handling Categorical Entries
		8.7.2 Handling Ordinal Entries
	8.8 Shared Matrix Factorization
		8.8.1 Gradient Descent Steps for Shared Factorization
		8.8.2 How to Set Up Shared Models in Arbitrary Scenarios
	8.9 Factorization Machines
	8.10 Summary
	8.11 Further Reading
	8.12 Exercises
9 The Linear Algebra of Similarity
	9.1 Introduction
	9.2 Equivalence of Data and Similarity Matrices
		9.2.1 From Data Matrix to Similarity Matrix and Back
		9.2.2 When Is Data Recovery from a Similarity Matrix Useful?
		9.2.3 What Types of Similarity Matrices Are ``Valid''?
		9.2.4 Symmetric Matrix Factorization as an Optimization Model
		9.2.5 Kernel Methods: The Machine Learning Terminology
	9.3 Efficient Data Recovery from Similarity Matrices
		9.3.1 Nyström Sampling
		9.3.2 Matrix Factorization with Stochastic Gradient Descent
		9.3.3 Asymmetric Similarity Decompositions
	9.4 Linear Algebra Operations on Similarity Matrices
		9.4.1 Energy of Similarity Matrix and Unit Ball Normalization
		9.4.2 Norm of the Mean and Variance
		9.4.3 Centering a Similarity Matrix
			9.4.3.1 Application: Kernel PCA
		9.4.4 From Similarity Matrix to Distance Matrix and Back
			9.4.4.1 Application: ISOMAP
	9.5 Machine Learning with Similarity Matrices
		9.5.1 Feature Engineering from Similarity Matrix
			9.5.1.1 Kernel Clustering
			9.5.1.2 Kernel Outlier Detection
			9.5.1.3 Kernel Classification
		9.5.2 Direct Use of Similarity Matrix
			9.5.2.1 Kernel K-Means
			9.5.2.2 Kernel SVM
	9.6 The Linear Algebra of the Representer Theorem
	9.7 Similarity Matrices and Linear Separability
		9.7.1 Transformations That Preserve Positive Semi-definiteness
	9.8 Summary
	9.9 Further Reading
	9.10 Exercises
10 The Linear Algebra of Graphs
	10.1 Introduction
	10.2 Graph Basics and Adjacency Matrices
	10.3 Powers of Adjacency Matrices
	10.4 The Perron-Frobenius Theorem
	10.5 The Right Eigenvectors of Graph Matrices
		10.5.1 The Kernel View of Spectral Clustering
			10.5.1.1 Relating Shi-Malik and Ng-Jordan-Weiss Embeddings
		10.5.2 The Laplacian View of Spectral Clustering
			10.5.2.1 Graph Laplacian
			10.5.2.2 Optimization Model with Laplacian
		10.5.3 The Matrix Factorization View of Spectral Clustering
			10.5.3.1 Machine Learning Application: Directed LinkPrediction
		10.5.4 Which View of Spectral Clustering Is Most Informative?
	10.6 The Left Eigenvectors of Graph Matrices
		10.6.1 PageRank as Left Eigenvector of Transition Matrix
		10.6.2 Related Measures of Prestige and Centrality
		10.6.3 Application of Left Eigenvectors to Link Prediction
	10.7 Eigenvectors of Reducible Matrices
		10.7.1 Undirected Graphs
		10.7.2 Directed Graphs
	10.8 Machine Learning Applications
		10.8.1 Application to Vertex Classification
		10.8.2 Applications to Multidimensional Data
	10.9 Summary
	10.10 Further Reading
	10.11 Exercises
11 Optimization in Computational Graphs
	11.1 Introduction
	11.2 The Basics of Computational Graphs
		11.2.1 Neural Networks as Directed Computational Graphs
	11.3 Optimization in Directed Acyclic Graphs
		11.3.1 The Challenge of Computational Graphs
		11.3.2 The Broad Framework for Gradient Computation
		11.3.3 Computing Node-to-Node Derivatives Using Brute Force
		11.3.4 Dynamic Programming for Computing Node-to-Node Derivatives
			11.3.4.1 Example of Computing Node-to-Node Derivatives
		11.3.5 Converting Node-to-Node Derivatives into Loss-to-WeightDerivatives
			11.3.5.1 Example of Computing Loss-to-Weight Derivatives
		11.3.6 Computational Graphs with Vector Variables
	11.4 Application: Backpropagation in Neural Networks
		11.4.1 Derivatives of Common Activation Functions
		11.4.2 Vector-Centric Backpropagation
		11.4.3 Example of Vector-Centric Backpropagation
	11.5 A General View of Computational Graphs
	11.6 Summary
	11.7 Further Reading
	11.8 Exercises
Bibliography
Index