Stat89a: Linear Algebra for Data Science

Instructor: Michael Mahoney ([email protected])

Assistants: TBA

Office Hours: TBA

Time and Location: Tue-Thu 9:30-11am, 103 Moffitt. Additional lab hours, TBA.

Prerequisite or corequisite: Foundations of Data Science (COMPSCI C8 / INFO C8 / STAT C8). One year of calculus.

Course Description: An introduction to linear algebra for data science. The course will cover introductory topics in linear algebra, starting with the basics; discrete probability and how probability can be used to understand high-dimensional vector spaces; matrices and graphs as popular mathematical structures with which to model data (e.g., as models for term-document corpora, high-dimensional regression problems, ranking/classification of web data, adjacency properties of social network data, etc.); and geometric approaches to eigendecompositions, least-squares, principal components analysis, etc.

Data Science Connector: During spring 16 and spring 17, this course was a two-unit connector. Going forward, this course will be expanded, covering similar topics in a more methodological man ner. In particular, it will serve as a comprehensive introduction to linear algebra, but presented in a way more appropriate for students of data science. The course remains a Data Science connector.

Course Requirements: The course evaluation will consist primarily of homeworks (ca. 50%)— split between pencil-and-paper (ca 30%) and computational (ca 20%) homeworks—a midterm (ca. 25%), and a final (ca. 25%).

Academic Honesty: This connector will follow the requirements from the main data science course.

Textbook: Online teaching materials (ca. 250 pages) from previous iterations of the class, expanded and supplemented by modified and updated computational notebooks.

Syllabus: The course will provide an introduction to linear algebra for data science. As such, the presentation and emphasis will be quite different than typical linear algebra classes that are more geared toward engineering, scientific computing, and related areas. The challenge is to convey the basic insights early in the course without getting delayed by extensive coverage of concepts that matter strongly in traditional numerical presentations of linear algebra, but that matter less for data science. To do this, we will focus on quadratic form structure, rather than the subspace structure, of the linear algebra, as well as connections with probability. The former is easier at the introductory level than subspaces, QR decompositions, etc., and is more intuitive as to how the results will generalize. The order of topics is also different. Linear equations will be covered, but at the end. More central is the role of least-squares approximations and principal components analysis, which pervade data science. After introducing basic concepts of Euclidean spaces, matrix multiplication, linear combination, span, etc. (to show that intuitive notions from low-dimensional Euclidean spaces can be generalized to high dimensions and can be used to model high-dimensional data), the course introduces the basics of discrete probability (to provide a model for high-dimensional spaces and to illustrate how high-dimensional spaces are very different than low-dimensional spaces). Then quadratic forms, eigenvalue decompositions of symmetric matrices, least squares regression, and principal components analysis are covered. Depending on time, the use of these methods for spectra clustering and ranking, solving linear equations, etc. will be covered.

Tentative week-by-week outline: Here is a tentative week-by-week outline.

• Week 1. Introduction, motivation, and overview: Representing data as flat tables versus matrices and graphs; Different ways probability/randomness/noise interacts with data; Prob ability and matrices/graphs in data science versus other areas; Trying to quantify the inference step.

• Week 2. Introduction to matrices, vectors, and R n : Ways to label points, elements, vectors, matrices, etc.; Basic properties of R n ; Norms and balls; Operations on matrices; Vector addition and scalar multiplication.

• Week 3. Vector spaces, matrices and operations on matrices, linear functions, and examples: Introduction to vector spaces and subspaces; Matrices and operations on matrices, includ ing matrix multiplication; Special types of matrices; Functions, linear functions, and linear transformations; Examples of matrices as transformations.

• Week 4. Geometry of R n , linear combinations, spans, etc.: dot products, angles, and perpen dicularity; Linear combinations, span, and linear independence; Bases, orthonormal bases, and projections.

• Week 5. Probability, Random Variables, etc.: Flipping coins, rolling dice, and throwing darts; Sample spaces and events; Some basic set theory; Basics of probability; Mass/Volume as an intuition; Conditional Probability; Independence.

• Week 6. Probability, Random Variables, etc., cont.: Bayes’ Theorem; Computing more com plex probabilities; Random Variables; Mean, variance, and moments of random variables; Properties of high dimensions versus low dimensions; Concentration in Flipping coins; Con centration in throwing darts; Two basic properties of expectations of random variables.

• Week 7. Probability, Random Variables, etc., cont.: Conditional expectation; More complex combinations: Covariances and correlations; Connections between probability theory and linear algebra; Large, small, and typical variability; Bounding deviations from the mean (weak bounds); A normal baseline to aim for; Bounding deviations from the mean (strong bounds); Examples and applications.

• Week 8. Eigendecompositions: Eigenvectors and Eigenvalues: Introduction to eigenvectors and eigenvalues; Some simple examples; Computing eigenvectors and eigenvalues; Basic prop erties of determinants; Using determinants to understand small eigendecompositions; Express ing matrices in terms of their eigendecompositions; A larger example.

• Week 9. Eigendecompositions, cont.: The Quadratic Forms Perspective: Two-dimensional conic sections; Quadratic forms and matrices; Some simple examples; Symmetric bi-linear functions; Connections with conic sections; Definiteness, indefiniteness, and quadratic forms as a sum/difference of squares; Two other topics.

• Week 10. The spectral decomposition of a symmetric matrix: Orthogonal subspaces; Finding the spectral decomposition; Many uses of the spectral decomposition.

• Week 11. Least-squares (LS) regression and Principal component analysis (PCA); Computing LS; Statistical aspects of LS; Regression diagnostics with LS; Computing PCA; Statistical aspects of PCA; Connections between PCA and LS; Extension to the SVD.

• Week 12. Solving linear equations: Linear equations; Geometry of linear equations; Gaus sian elimination; Row exchanges; Networks and incidence matrices; The four fundamental subspaces.

• Week 13. Solving linear equations, cont.: Basis transformations; Orthogonal bases; Gram Schmidt Orthogonalization; Direct versus indirect methods; Numerical issues.