Linear Algebra and Probability for Computer Science Applications

✍ Scribed by Ernest Davis

• Publisher: CRC Press
• Year: 2012
• Tongue: English
• Leaves: 430
• Edition: 1
• Category: Library

✦ Synopsis

Features

Focuses on mathematical techniques that are most relevant to computer scientists
Assumes as little mathematical background as possible
Covers applications from computer graphics, web search, machine learning, cryptography, and a host of other computer science areas
Includes MATLAB functions, MATLAB programming assignments, and problems in each chapter
Offers MATLAB code at www.cs.nyu.edu/faculty/davise/MathTechniques/index.html

Based on the author’s course at NYU, Linear Algebra and Probability for Computer Science Applications gives 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 Assignments
The 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 Problems
Comprehensive problem sections include traditional calculation exercises, thought problems such as proofs, and programming assignments that involve creating MATLAB functions.

Download Updates of this Book (More Exercises, Problems & Programmes) from the following Link:

http://www.cs.nyu.edu/faculty/davise/MathTechniques/MoreAssigs/MoreAssigs.html

✦ Table of Contents

Cover

S Title

Linear Algebra and Probability for Computer Science Applications

© 2012 by Taylor & Francis Group, LLC
ISBN 978-1-4665-0159-1 (eBook - PDF)

Dedication

Contents

Preface

Chapter 1 MATLAB
1.1 Desk Calculator Operations
1.2 Booleans
1.3 Nonstandard Numbers
1.4 Loops and Conditionals
1.5 Script File
1.6 Functions
1.7 Variable Scope and Parameter Passing
Problem
Programming Assignments

I: Linear Algebra

 Chapter 2  Vectors
      2.1 Definition of Vectors
      2.2 Applications of Vectors
           2.2.1 General Comments about Applications
      2.3 Basic Operations on Vectors
           2.3.1 Algebraic Properties of the Operations
           2.3.2 Applications of Basic Operations
      2.4 Dot Product
           2.4.1 Algebraic Properties of the Dot Product
           2.4.2 Application of the Dot Product: Weighted Sum
           2.4.3 Geometric Properties of the Dot Product
           2.4.4 Metacomment: How to Read Formula Manipulations
           2.4.5 Application of the Dot Product: Similarity of Two Vectors
           2.4.6 Dot Product and Linear Transformations
      2.5 Vectors in MATLAB: Basic Operations
           2.5.1 Creating a Vector and Indexing
           2.5.2 Creating a Vector with Elements in Arithmetic Sequence
           2.5.3 Basic Operations
           2.5.4 Element-by-Element Operations
           2.5.5 Useful Vector Functions
           2.5.6 Random Vectors
           2.5.7 Strings: Arrays of Characters
           2.5.8 Sparse Vectors
      2.6 Plotting Vectors in MATLAB
      2.7 Vectors in Other Programming Languages
      Exercises
      Problems
      Programming Assignments

 Chapter 3  Matrices
      3.1 Definition of Matrices
      3.2 Applications of Matrices
      3.3 Simple Operations on Matrices
      3.4 Multiplying a Matrix Times a Vector
           3.4.1 Applications of Multiplying a Matrix Times a Vector
      3.5 Linear Transformation
      3.6 Systems of Linear Equations
           3.6.1 Applications of Systems of Linear Equations
      3.7 Matrix Multiplication
      3.8 Vectors as Matrices
      3.9 Algebraic Properties of Matrix Multiplication
           3.9.1 Matrix Exponentiation
      3.10 Matrices in MATLAB
           3.10.1 Inputting Matrices
           3.10.2 Extracting Submatrices
           3.10.3 Operations on Matrices
           3.10.4 Sparse Matrices
           3.10.5 Cell Arrays
      Problems
      Programming Assignments

 Chapter 4  Vector Spaces
      4.1 Fundamentals of Vector Spaces
           4.1.1 Subspaces
           4.1.2 Coordinates, Bases, Linear Independence
           4.1.3 Orthogonal and Orthonormal Basis
           4.1.4 Operations on Vector Spaces
           4.1.5 Null Space, Image Space, and Rank
           4.1.6 Systems of Linear Equations
           4.1.7 Inverses
           4.1.8 Null Space and Rank in MATLAB
      4.2 Proofs and Other AbstractMathematics (Optional)
           4.2.1 Vector Spaces
           4.2.2 Linear Independence and Bases
           4.2.3 Sum of Vector Spaces
           4.2.4 Orthogonality
           4.2.5 Functions
           4.2.6 Linear Transformations
           4.2.7 Inverses
           4.2.8 Systems of Linear Equations
      4.3 Vector Spaces in General (Very Optional)
           4.3.1 The General Definition of Vector Spaces
      Exercises
      Programming Assignments

 Chapter 5  Algorithms
      5.1 Gaussian Elimination: Examples
      5.2 Gaussian Elimination: Discussion
           5.2.1 Gaussian Elimination on Matrices
           5.2.2 Maximum Element Row Interchange
           5.2.3 Testing on Zero
      5.3 Computing a Matrix Inverse
      5.4 Inverse and Systems of Equations in MATLAB
      5.5 Ill-Conditioned Matrices
      5.6 Computational Complexity
           5.6.1 Viewpoints on Numerical Computation
           5.6.2 Running Times
      Exercises
      Programming Assignments

 Chapter 6  Geometry
      6.1 Arrows
      6.2 Coordinate Systems
      6.3 Simple Geometric Calculations
           6.3.1 Distance and Angle
           6.3.2 Direction
           6.3.3 Lines in Two-Dimensional Space
           6.3.4 Lines and Planes in Three-Dimensional Space
           6.3.5 Identity, Incidence, Parallelism, and Intersection
           6.3.6 Projections
      6.4 Geometric Transformations
           6.4.1 Translations
           6.4.2 Rotation around the Origin
           6.4.3 Rigid Motions and the Homogeneous Representation
           6.4.4 Similarity Transformations
           6.4.5 Affine Transformations
           6.4.6 Image of a Distant Object
           6.4.7 Determinants
           6.4.8 Coordinate Transformation on Image Arrays
           6.4.8 Coordinate Transformation on Image Arrays
      Exercises
      Problems
      Programming Assignments

 Chapter 7  Change of Basis, DFT, and SVD
      7.1 Change of Coordinate System
           7.1.1 Affine Coordinate Systems
           7.1.2 Duality of Transformation and Coordinate Change; Handedness
           7.1.3 Application: Robotic Arm
      7.2 The Formula for Basis Change
      7.3 Confusion and How to Avoid It
      7.4 Nongeometric Change of Basis
      7.5 Color Graphics
      7.6 Discrete Fourier Transform (Optional)
           7.6.1 Other Applications of the Fourier Transform
           7.6.2 The Complex Fourier Transform
      7.7 Singular Value Decomposition
           7.7.1 Matrix Decomposition
           7.7.2 Proof of Theorem 7.4 (Optional)
      7.8 Further Properties of the SVD
           7.8.1 Eigenvalues of a Symmetric Matrix
      7.9 Applications of the SVD
           7.9.1 Condition Number
           7.9.2 Computing Rank in the Presence of Roundoff
           7.9.3 Lossy Compression
      7.10 MATLAB
           7.10.1 The SVD in MATLAB
           7.10.2 The DFT in MATLAB
      Exercises
      Problems
      Programming Assignments

II: Probability

 Chapter 8  Probability
      8.1 The Interpretations of Probability Theory
      8.2 Finite Sample Spaces
      8.3 Basic Combinatorial Formulas
           8.3.1 Exponential
           8.3.2 Permutations of n Items
           8.3.3 Permutations of k Items out of n
           8.3.4 Combinations of k Items out of n
           8.3.5 Partition into Sets
           8.3.6 Approximation of Central Binomial
           8.3.7 Examples of Combinatorics
      8.4 The Axioms of Probability Theory
      8.5 Conditional Probability
      8.6 The Likelihood Interpretation
      8.7 Relation between Likelihood and Sample Space Probability
      8.8 Bayes’ Law
      8.9 Independence
           8.9.1 Independent Evidence
           8.9.2 Application: Secret Sharing in Cryptography
      8.10 Random Variables
      8.11 Application: Naive Bayes Classification
      Exercises
      Problems
      Programming Assignments

 Chapter 9  Numerical Random Variables
      9.1 Marginal Distribution
      9.2 Expected Value
      9.3 Decision Theory
           9.3.1 Sequence of Actions: Decision Trees
      9.4 Variance and Standard Deviation
      9.5 Random Variables over Infinite Sets of Integers
      9.6 Three Important Discrete Distributions
           9.6.1 The Bernoulli Distribution
           9.6.2 The Binomial Distribution
           9.6.3 The Zipf Distribution
      9.7 Continuous Random Variables
      9.8 Two Important Continuous Distributions
           9.8.1 The Continuous Uniform Distribution
           9.8.2 The Gaussian Distribution
      9.9 MATLAB
      Exercises
      Problems
      Programming Assignments

 Chapter 10  Markov Models
      10.1 Stationary Probability Distribution
           10.1.1 Computing the Stationary Distribution
      10.2 PageRank and Link Analysis
           10.2.1 The Markov Model
           10.2.2 Pages with No Outlinks
           10.2.3 Nonuniform Variants
      10.3 Hidden Markov Models and the K-Gram Model
           10.3.1 The Probabilistic Model
           10.3.2 Hidden Markov Models
           10.3.3 The Viterbi Algorithm
           10.3.4 Part of Speech Tagging
           10.3.5 The Sparse Data Problem and Smoothing
      Exercises
      Problems
      Programming Assignments

 Chapter 11  Confidence Intervals
      11.1 The Basic Formula for Confidence Intervals
      11.2 Application: Evaluating a Classifier
      11.3 Bayesian Statistical Inference (Optional)
      11.4 Confidence Intervals in the Frequentist Viewpoint (Optional)
      11.5 Hypothesis Testing and Statistical Significance
      11.6 Statistical Inference and ESP
      Exercises
      Problems

 Chapter 12  Monte Carlo Methods
      12.1 Finding Area
      12.2 Generating Distributions
      12.3 Counting
      12.4 Counting Solutions to a DNF Formula (Optional)
      12.5 Sums, Expected Values, and Integrals
      12.6 Probabilistic Problems
      12.7 Resampling
      12.8 Pseudorandom Numbers
      12.9 Other Probabilistic Algorithms
      12.10 MATLAB
      Exercises
      Programming Assignments

 Chapter 13  Information and Entropy
      13.1 Information
      13.2 Entropy
      13.3 Conditional Entropy and Mutual Information
      13.4 Coding
           13.4.1 Huffman Coding
      13.5 Entropy of Numeric and Continuous Random Variables
      13.6 The Principle of Maximum Entropy
           13.6.1 The Principle of Maximum Entropy
           13.6.2 Consequences of the Maximum Entropy Principle
      13.7 Statistical Inference
      Exercises
      Problem

 Chapter 14  Maximum Likelihood Estimation
      14.1 Sampling
      14.2 Uniform Distribution
      14.3 Gaussian Distribution: Known Variance
      14.4 Gaussian Distribution: Unknown Variance
      14.5 Least Squares Estimates
           14.5.1 Least Squares in MATLAB
      14.6 Principal Component Analysis
      14.7 Applications of Principal Component Analysis
           14.7.1 Visualization
           14.7.2 Data Analysis
           14.7.3 Bounding Box
           14.7.4 Surface Normals
           14.7.5 Latent Semantic Analysis
      Exercises
      Problems
      Programming Assignments

References

Notation

Back Cover