Linear Algebra and Probability for Computer Science Applications

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