Linear Algebra and Optimization with Applications to Machine Learning

The following sections are included:

• Preface
• Contents

As we explained in the preface, this first volume covers “classical” linear algebra, up to and including the primary decomposition and the Jordan form. Besides covering the standard topics, we discuss a few topics that are important for applications. These include…

The following sections are included:

• Motivations: Linear Combinations, Linear Independence and Rank
• Vector Spaces
• Indexed Families; the Sum Notation ${\displaystyle {\sum }_{i\in I}ai}$
• Linear Independence, Subspaces
• Bases of a Vector Space
• Matrices
• Linear Maps
• Linear Forms and the Dual Space
• Summary
• Problems

The following sections are included:

• Representation of Linear Maps by Matrices
• Composition of Linear Maps and Matrix Multiplication
• Change of Basis Matrix
• The Effect of a Change of Bases on Matrices
• Summary
• Problems

In this chapter, we discuss two types of matrices that have applications in computer science and engineering:

• Haar matrices and the corresponding Haar wavelets, a fundamental tool in signal processing and computer graphics.
• Hadamard matrices which have applications in error correcting codes, signal processing, and low rank approximation.

The following sections are included:

• Direct Products
• Sums and Direct Sums
• The Rank-Nullity Theorem; Grassmann’s Relation
• Affine Maps
• Summary
• Problems

The following sections are included:

• Permutations, Signature of a Permutation
• Alternating Multilinear Maps
• Definition of a Determinant
• Inverse Matrices and Determinants
• Systems of Linear Equations and Determinants
• Determinant of a Linear Map
• The Cayley-Hamilton Theorem
• Permanents
• Summary
• Further Readings
• Problems

In this chapter we assume that all vector spaces are over the field ℝ. All results that do not rely on the ordering on ℝ or on taking square roots hold for arbitrary fields.

The following sections are included:

• Normed Vector Spaces
• Matrix Norms
• Subordinate Norms
• Inequalities Involving Subordinate Norms
• Condition Numbers of Matrices
• An Application of Norms: Solving Inconsistent Linear Systems
• Limits of Sequences and Series
• The Matrix Exponential
• Summary
• Problems

The following sections are included:

• Convergence of Sequences of Vectors and Matrices
• Convergence of Iterative Methods
• Description of the Methods of Jacobi, Gauss–Seidel, and Relaxation
• Convergence of the Methods of Gauss–Seidel and Relaxation
• Convergence of the Methods of Jacobi, Gauss–Seidel, and Relaxation for Tridiagonal Matrices
• Summary
• Problems

The following sections are included:

• The Dual Space E* and Linear Forms
• Pairing and Duality Between E and E*
• The Duality Theorem and Some Consequences
• The Bidual and Canonical Pairings
• Hyperplanes and Linear Forms
• Transpose of a Linear Map and of a Matrix
• Properties of the Double Transpose
• The Four Fundamental Subspaces
• Summary
• Problems

The following sections are included:

• Inner Products, Euclidean Spaces
• Orthogonality and Duality in Euclidean Spaces
• Adjoint of a Linear Map
• Existence and Construction of Orthonormal Bases
• Linear Isometries (Orthogonal Transformations)
• The Orthogonal Group, Orthogonal Matrices
• The Rodrigues Formula
• QR-Decomposition for Invertible Matrices
• Some Applications of Euclidean Geometry
• Summary
• Problems

The following sections are included:

• Orthogonal Reflections
• QR-Decomposition Using Householder Matrices
• Summary
• Problems

The following sections are included:

• Sesquilinear and Hermitian Forms, Pre-Hilbert Spaces and Hermitian Spaces
• Orthogonality, Duality, Adjoint of a Linear Map
• Linear Isometries (Also Called Unitary Transformations)
• The Unitary Group, Unitary Matrices
• Hermitian Reflections and QR-Decomposition
• Orthogonal Projections and Involutions
• Dual Norms
• Summary
• Problems

The following sections are included:

• Eigenvectors and Eigenvalues of a Linear Map
• Reduction to Upper Triangular Form
• Location of Eigenvalues
• Conditioning of Eigenvalue Problems
• Eigenvalues of the Matrix Exponential
• Summary
• Problems

This chapter is devoted to the representation of rotations in SO(3) in terms of unit quaternions. Since we already defined the unitary groups SU(n), the quickest way to introduce the unit quaternions is to define them as the elements of the group SU(2)…

The following sections are included:

• Introduction
• Normal Linear Maps: Eigenvalues and Eigenvectors
• Spectral Theorem for Normal Linear Maps
• Self-Adjoint, Skew-Self-Adjoint, and Orthogonal Linear Maps
• Normal and Other Special Matrices
• Rayleigh–Ritz Theorems and Eigenvalue Interlacing
• The Courant–Fischer Theorem; Perturbation Results
• Summary
• Problems

After the problem of solving a linear system, the problem of computing the eigenvalues and the eigenvectors of a real or complex matrix is one of most important problems of numerical linear algebra. Several methods exist, among which we mention Jacobi, Givens–Householder, divide-and-conquer, QR iteration, and Rayleigh–Ritz; see Demmel [Demmel (1997)], Trefethen and Bau [Trefethen and Bau III (1997)], Meyer [Meyer (2000)], Serre [Serre (2010)], Golub and Van Loan [Golub and Van Loan (1996)], and Ciarlet [Ciarlet (1989)]. Typically, better performing methods exist for special kinds of matrices, such as symmetric matrices…

In this chapter and the next we present some applications of linear algebra to graph theory. Graphs (undirected and directed) can be defined in terms of various matrices (incidence and adjacency matrices), and various connectivity properties of graphs are captured by properties of these matrices. Another very important matrix is associated with a (undirected) graph: the graph Laplacian. The graph Laplacian is symmetric positive definite, and its eigenvalues capture some of the properties of the underlying graph. This is a key fact that is exploited in graph clustering methods, the most powerful being the method of normalized cuts due to Shi and Malik [Shi and Malik (2000)]. This chapter and the next constitute an introduction to algebraic and spectral graph theory. We do not discuss normalized cuts, but we discuss graph drawings. Thorough presentations of algebraic graph theory can be found in Godsil and Royle [Godsil and Royle (2001)] and Chung [Chung (1997)]…

The following sections are included:

• Graph Drawing and Energy Minimization
• Examples of Graph Drawings
• Summary

The following sections are included:

• Properties of f* ○ f
• Singular Value Decomposition for Square Matrices
• Polar Form for Square Matrices
• Singular Value Decomposition for Rectangular Matrices
• Ky Fan Norms and Schatten Norms
• Summary
• Problems

The following sections are included:

• Least Squares Problems and the Pseudo-Inverse
• Properties of the Pseudo-Inverse
• Data Compression and SVD
• Principal Components Analysis (PCA)
• Best Affine Approximation
• Summary
• Problems

In this chapter all vector spaces are defined over an arbitrary field K…

In Section 6.7 we explained that if $f:E\to E$ is a linear map on a K-vector space E, then for any polynomial $p\left(X\right)=a_0{X}^d+a_1{X}^{d-1}+\cdots +a_d$ with coefficients in the field K, we can define the linear map $p\left(f\right):E\to E$ by…

The following sections are included:

• Bibliography
• Index