Linear Algebra and Probability for Computer Science Applications

Based on the author’s course at NYU, Linear Algebra and Probability for Computer Science Applicationsgives an introduction to two mathematical fields that are fundamental in many areas of computer science. The course and the text are addressed to students with a very weak mathematical background. Most of the chapters discuss relevant MATLAB® functions and features and give sample assignments in MATLAB; the author’s website provides the MATLAB code from the book.

After an introductory chapter on MATLAB, the text is divided into two sections. The section on linear algebra gives an introduction to the theory of vectors, matrices, and linear transformations over the reals. It includes an extensive discussion on Gaussian elimination, geometric applications, and change of basis. It also introduces the issues of numerical stability and round-off error, the discrete Fourier transform, and singular value decomposition. The section on probability presents an introduction to the basic theory of probability and numerical random variables; later chapters discuss Markov models, Monte Carlo methods, information theory, and basic statistical techniques. The focus throughout is on topics and examples that are particularly relevant to computer science applications; for example, there is an extensive discussion on the use of hidden Markov models for tagging text and a discussion of the Zipf (inverse power law) distribution.

Examples and Programming AssignmentsThe examples and programming assignments focus on computer science applications. The applications covered are drawn from a range of computer science areas, including computer graphics, computer vision, robotics, natural language processing, web search, machine learning, statistical analysis, game playing, graph theory, scientific computing, decision theory, coding, cryptography, network analysis, data compression, and signal processing.

Homework ProblemsComprehensive problem sections include traditional calculation exercises, thought problems such as proofs, and programming assignments that involve creating MATLAB functions.

Ernest Davis is a computer science professor in the Courant Institute of Mathematical Sciences at New York University. He earned a Ph.D. in computer science from Yale University. Dr. Davis is a member of the American Association of Artificial Intelligence and is a reviewer for many journals. His research primarily focuses on spatial and physical reasoning.

MATLABDesk calculator operations Booleans Nonstandard numbers Loops and conditionals Script file Functions Variable scope and parameter passing

I: Linear Algebra Vectors Definition of vectors Applications of vectorsBasic operations on vectorsDot productVectors in MATLAB: Basic operationsPlotting vectors in MATLABVectors in other programming languages

Matrices Definition of matrices Applications of matrices Simple operations on matrices Multiplying a matrix times a vector Linear transformation Systems of linear equations Matrix multiplication Vectors as matrices Algebraic properties of matrix multiplication Matrices in MATLAB

Vector Spaces Subspaces Coordinates, bases, linear independenceOrthogonal and orthonormal basis Operations on vector spaces Null space, image space, and rank Systems of linear equations Inverses Null space and Rank in MATLABVector spaces Linear independence and bases Sum of vector spacesOrthogonality Functions Linear transformations Inverses Systems of linear equations The general definition of vector spaces

Algorithms Gaussian elimination: Examples Gaussian elimination: DiscussionComputing a matrix inverse Inverse and systems of equations in MATLAB Ill-conditioned matrices Computational complexity

Geometry Arrows Coordinate systems Simple geometric calculationsGeometric transformations

Change of Basis, DFT, and SVD Change of coordinate systemThe formula for basis change Confusion and how to avoid it Nongeometric change of basis Color graphics Discrete Fourier transform (Optional)Singular value decompositionFurther properties of the SVDApplications of the SVDMATLAB

II: Probability Probability The interpretations of probability theory Finite sample spaces Basic combinatorial formulas The axioms of probability theoryConditional probability The likelihood interpretation Relation between likelihood and sample space probability Bayes’ law IndependenceRandom variables Application: Naive Bayes’ classification

Numerical Random Variables Marginal distribution Expected value Decision theoryVariance and standard deviation Random variables over infinite sets of integers Three important discrete distributionsContinuous random variables Two important continuous distributionsMATLAB

Markov Models Stationary probability distribution PageRank and link analysisHidden Markov models and the k-gram model

Confidence Intervals The basic formula for confidence intervals Application: Evaluating a classifier Bayesian statistical inference (Optional) Confidence intervals in the frequentist viewpoint: (Optional) Hypothesis testing and statistical significance Statistical inference and ESP

Monte Carlo Methods Finding area Generating distributions Counting Counting solutions to DNF (Optional) Sums, expected values, integrals Probabilistic problems Resampling Pseudo-random numbers Other probabilistic algorithmsMATLAB

Information and Entropy Information Entropy Conditional entropy and mutual information Coding Entropy of numeric and continuous random variables The principle of maximum entropyStatistical inference

Maximum Likelihood Estimation Sampling Uniform distribution Gaussian distribution: Known variance Gaussian distribution: Unknown variance Least squares estimates Principal component analysis Applications of PCA

References
Notation
Index