Linear Algebra and Analysis

14.15 Least Squares And Singular Value Decomposition

The singular value decomposition also has a very interesting connection to the problem of least squares solutions. Recall that it was desired to find x such that

is as small as possible. Lemma 13.3.1 shows that there is a solution to this problem which can be found by solving the system A∗Ax = A∗y. Each x which solves this system solves the minimization problem as was shown in the lemma just mentioned. Now consider this equation for the solutions of the minimization problem in terms of the singular value decomposition.

Therefore, this yields the following upon using block multiplication and multiplying on the left by V ∗.

(14.29)

One solution to this equation which is very easy to spot is

(14.30)

Chapter August 25, 2018 1 Some Prerequisite Topics

1.1 Sets And Set Notation
1.2 The Schroder Bernstein Theorem
1.3 Equivalence Relations
1.4 Well Ordering And Induction
1.5 The Complex Numbers And Fields
1.6 Polar Form Of Complex Numbers
1.7 Roots Of Complex Numbers
1.8 The Quadratic Formula
1.9 The Complex Exponential
1.10 The Fundamental Theorem Of Algebra
1.11 Ordered Fields
1.12 Polynomials
1.13 Examples Of Finite Fields
1.13.1 Division Of Numbers
1.13.2 The Field ℤp
1.14 Some Topics From Analysis
1.14.1 lim sup and lim inf
1.15 Exercises

Part I  Linear Algebra For Its Own Sake

Chapter 2 Systems Of Linear Equations

2.1 Elementary Operations
2.2 Gauss Elimination
2.3 Exercises

Chapter 3 Vector Spaces

3.1 Linear Combinations Of Vectors, Independence
3.2 Subspaces
3.3 Exercises
3.4 Polynomials And Fields
3.4.1 The Algebraic Numbers
3.4.2 The Lindermannn Weierstrass Theorem And Vector Spaces
3.5 Exercises

Chapter 4 Matrices

4.1 Properties Of Matrix Multiplication
4.2 Finding The Inverse Of A Matrix
4.3 Matrices And Systems Of Equations
4.4 Block Multiplication Of Matrices
4.5 Elementary Matrices
4.6 Exercises

Chapter 5 Linear Transformations

5.1 ℒ(V,W) As A Vector Space
5.2 The Matrix Of A Linear Transformation
5.3 Rotations About A Given Vector∗
5.4 Exercises

Chapter 6 Direct Sums And Block Diagonal Matrices

6.1 A Theorem Of Sylvester, Direct Sums
6.2 Finding The Minimum Polynomial
6.3 Eigenvalues And Eigenvectors Of Linear Transformations
6.4 A Formal Derivative, Diagonalizability
6.5 Exercises

Chapter 7 Canonical Forms

7.1 Cyclic Sets
7.2 The Rational Canonical Form
7.3 Nilpotent Transformations and Jordan Canonical Form
7.4 Exercises
7.5 Companion Matrices and Uniqueness
7.6 Exercises

Chapter 8 Determinants

8.1 The Function sgn
8.2 The Definition Of The Determinant
8.3 A Symmetric Definition
8.4 Basic Properties Of The Determinant
8.5 Expansion Using Cofactors
8.6 A Formula For The Inverse
8.7 Rank Of A Matrix
8.8 Summary Of Determinants
8.9 The Cayley Hamilton Theorem
8.10 Exercises

Chapter 9 Modules And Rings ∗

9.1 Integral Domains And The Ring Of Polynomials
9.2 Modules And Decomposition Into Cyclic Sub-Modules
9.3 A Direct Sum Decomposition
9.4 Quotients
9.5 Cyclic Decomposition
9.6 Uniqueness
9.7 Canonical Forms
9.8 Exercises

Chapter 10 Related Topics

10.1 The Symmetric Polynomial Theorem
10.2 Transcendental Numbers
10.3 The Fundamental Theorem Of Algebra
10.4 More On Algebraic Field Extensions

Part II  Analysis And Geometry In Linear Algebra

Chapter 11 Normed Linear Spaces

11.1 Metric Spaces
11.1.1 Open And Closed Sets, Sequences, Limit Points, Completeness
11.1.2 Cauchy Sequences, Completeness
11.1.3 Closure Of A Set
11.1.4 Continuous Functions
11.1.5 Separable Metric Spaces
11.1.6 Compact Sets in Metric Space
11.1.7 Lipschitz Continuity And Contraction Maps
11.1.8 Convergence Of Functions
11.2 Connected Sets
11.3 Subspaces Spans And Bases
11.4 Inner Product And Normed Linear Spaces
11.4.1 The Inner Product In Fn
11.4.2 General Inner Product Spaces
11.4.3 Normed Vector Spaces
11.4.4 The p Norms
11.4.5 Orthonormal Bases
11.5 Equivalence Of Norms
11.6 Norms On ℒ(X,Y )
11.7 Limits Of A Function
11.8 Exercises

Chapter 12 Limits Of Vectors And Matrices

12.1 Regular Markov Matrices
12.2 Migration Matrices
12.3 Absorbing States
12.4 Positive Matrices
12.5 Functions Of Matrices
12.6 Exercises

Chapter 13 Inner Product Spaces And Least Squares

13.1 Orthogonal Projections
13.2 Riesz Representation Theorem, Adjoint Map
13.3 Least Squares
13.4 Fredholm Alternative
13.5 The Determinant And Volume
13.6 Exercises

Chapter 14 Matrices And The Inner Product

14.1 Schur’s Theorem, Hermitian Matrices
14.2 Quadratic Forms
14.3 The Estimation Of Eigenvalues
14.4 Advanced Theorems
14.5 Exercises
14.6 The Right Polar Factorization∗
14.7 The Square Root
14.8 An Application To Statistics
14.9 Simultaneous Diagonalization
14.10 Fractional Powers
14.11 Spectral Theory Of Self Adjoint Operators
14.12 Positive And Negative Linear Transformations
14.13 The Singular Value Decomposition
14.14 Approximation In The Frobenius Norm
14.15 Least Squares And Singular Value Decomposition
14.16 The Moore Penrose Inverse
14.17 The Spectral Norm And The Operator Norm
14.18 The Positive Part Of A Hermitian Matrix
14.19 Exercises

Chapter 15 Analysis Of Linear Transformations

15.1 The Condition Number
15.2 The Spectral Radius
15.3 Series And Sequences Of Linear Operators
15.4 Iterative Methods For Linear Systems
15.5 Exercises

Chapter 16 Numerical Methods, Eigenvalues

16.1 The Power Method For Eigenvalues
16.1.1 The Shifted Inverse Power Method
16.1.2 The Explicit Description Of The Method
16.2 Automation With Matlab
16.2.1 Complex Eigenvalues
16.2.2 Rayleigh Quotients And Estimates for Eigenvalues
16.3 The QR Algorithm
16.3.1 Basic Properties And Definition
16.3.2 The Case Of Real Eigenvalues
16.3.3 The QR Algorithm In The General Case
16.3.4 Upper Hessenberg Matrices
16.4 Exercises

Part III  Analysis Which Involves Linear Algebra

Chapter 17 The Derivative, A Linear Transformation

17.1 Basic Definitions
17.2 The Chain Rule
17.3 The Matrix Of The Derivative
17.4 A Mean Value Inequality
17.5 Existence Of The Derivative, C1 Functions
17.6 Higher Order Derivatives
17.7 Some Standard Notation
17.8 The Derivative And The Cartesian Product
17.9 Mixed Partial Derivatives
17.10 Newton’s Method
17.11 Exercises

Chapter 18 Implicit Function Theorem

18.1 Statement And Proof Of The Theorem
18.2 More Derivatives
18.3 The Case Of ℝn
18.4 Exercises
18.5 The Method Of Lagrange Multipliers
18.6 The Taylor Formula
18.7 Second Derivative Test
18.8 The Rank Theorem
18.9 The Local Structure Of C1 Mappings
18.10 Brouwer Fixed Point Theorem ℝn
18.10.1 Simplices And Triangulations
18.10.2 Labeling Vertices
18.10.3 The Brouwer Fixed Point Theorem
18.11 Invariance Of Domain∗
18.12 Tensor Products
18.12.1 The Norm In Tensor Product Space
18.12.2 The Taylor Formula And Tensors
18.13 Exercises

Chapter 19 Abstract Measures And Measurable Functions

19.1 Simple Functions And Measurable Functions
19.2 Measures And Their Properties
19.3 Dynkin’s Lemma
19.4 Measures And Regularity
19.5 When Is A Measure A Borel Measure?
19.6 Measures And Outer Measures
19.7 Exercises
19.8 An Outer Measure On P (ℝ)
19.9 Measures From Outer Measures
19.10 One Dimensional Lebesgue Stieltjes Measure
19.11 Exercises

Chapter 20 The Abstract Lebesgue Integral

20.1 Definition For Nonnegative Measurable Functions
20.1.1 Riemann Integrals For Decreasing Functions
20.1.2 The Lebesgue Integral For Nonnegative Functions
20.2 The Lebesgue Integral For Nonnegative Simple Functions
20.3 The Monotone Convergence Theorem
20.4 Other Definitions
20.5 Fatou’s Lemma
20.6 The Integral’s Righteous Algebraic Desires
20.7 The Lebesgue Integral, L1
20.8 The Dominated Convergence Theorem
20.9 Exercises

Chapter 21 Measures From Positive Linear Functionals

21.1 Lebesgue Measure On ℝn,Fubini’s Theorem
21.2 The Besicovitch Covering Theorem
21.3 Change Of Variables, Linear Map
21.4 Vitali Coverings
21.5 Change Of Variables
21.6 Exercises

Chapter 22 The Lp Spaces

22.1 Basic Inequalities And Properties
22.2 Density Considerations
22.3 Separability
22.4 Continuity Of Translation
22.5 Mollifiers And Density Of Smooth Functions
22.6 Fundamental Theorem Of Calculus For Radon Measures
22.7 Exercises

Chapter 23 Representation Theorems

23.1 Basic Theory
23.2 Radon Nikodym Theorem
23.3 Improved Change Of Variables Formula
23.4 Vector Measures
23.5 Representation Theorems For The Dual Space Of Lp
23.6 The Dual Space Of C0 (X)
23.7 Exercises

Part IV  Appendix

A.1 The Box Product
A.2 The Distributive Law For Cross Product
B.1 Functions Of Many Variables
B.2 Tietze Extension Theorem
C.1 The Hamel Basis
C.2 Exercises
Download PDFView PDF