代写 Module 1-1: Linear Space

Module 1-1: Linear Space
Inner Product Space Linear Control Systems (2019)
Ding Zhao
Assistant Professor College of Engineering School of Computer Science
Carnegie Mellon University
Ding Zhao (CMU)
M1-1: Linear Space 1 / 29

Table of Contents
1 Inner product and norm
2 Orthogonal Bases (Gram-Schmidt Process)
3 Orthogonal Space
Ding Zhao (CMU) M1-1: Linear Space 2 / 29

Table of Contents
1 Inner product and norm
2 Orthogonal Bases (Gram-Schmidt Process)
3 Orthogonal Space
Ding Zhao (CMU) M1-1: Linear Space 3 / 29

Inner Products
Let(X,C)beavectorspace,afunction⟨·,·⟩:X ×X →Cisaninnerproductif 1 Conjugate symmetry:
2 Linearity in the first argument:
⟨x, y⟩ = ⟨y, x⟩
⟨ax, y⟩ = a⟨x, y⟩
⟨x + y, z⟩ = ⟨x, z⟩ + ⟨y, z⟩
⟨x,x⟩ ≥ 0
⟨x, x⟩ = 0 ⇔ x = 0 .
3 Positive definiteness:
A vector space with
a well-defined inner product is called an inner product (vector) space, denoted as (X , F , 􏰅⟨, ⟩)
Ding Zhao (CMU) M1-1: Linear Space 4 / 29

Standard Inner Product
In general, we consider the following definitions as inner products on: (Rn,R) and (Cn,C) with (Rn,R), ⟨x,y⟩ = ⟨y,x⟩ = xTy = 􏰄ni=1 xiyi
with (Cn, C), ⟨x, y⟩ = xH · y = 􏰄ni=1 x ̄iyi, where the H is called Hermitian (conjugate transpose).
Ding Zhao (CMU) M1-1: Linear Space 5 / 29

Angle between Vectors and Orthogonal
Inspired from the geometric space, the angle between two vectors is defined as: ⟨x, y⟩
∠ (x, y) = arccos 􏰅⟨x, x⟩􏰅⟨y, y⟩
For x, y ∈ V , we say that x and y are orthogonal if ∠(x, y) = 90◦
⟨x, y⟩ = cos(90◦) = 0 A set of vectors x = {x1, . . . , xn} is called orthonormal if
􏰉⟨xi,xj⟩=0, ∀i̸=j ⟨xi,xi⟩=1, 1􏰙i􏰙n
Ding Zhao (CMU) M1-1: Linear Space 6 / 29

Orthogonal Implies Linear Independency
If x = {x1, . . . , xn} is orthogonal, xi are linearly independent Proof:
Let α1×1 + α2×2 + · · · + αnxn = 0
⟨x1,·⟩⇒α1 =0 . .
⟨xn,·⟩⇒αn =0
Ding Zhao (CMU)
M1-1: Linear Space 7 / 29

Norm and Normed Space
A linear space (X , F ) is called normed if any real-valued function of x ∈ X , denoted by ∥x∥, can be defined with the following properties:
1 Positive definiteness:
∥x∥ is non-negative for every x and ∥x∥= 0 if and only if x = 0
2 Absolute homogeneity: ∥αx∥ = |α| ∥x∥, for any real α
3 Triangular inequality: ∥x1 + x2∥ ≤ ∥x1∥ + ∥x2∥
Ding Zhao (CMU) M1-1: Linear Space 8 / 29

Normed Space Examples: p-norm
Every inner product (X , F , 􏰅⟨, ⟩) generates a norm space: eg. (Rn,R) : x = (x1,…,xn)T
􏰕􏰄n 2􏰖1 1 ||x||2 = i=1 |xi| 2 = ⟨x, x⟩2
||x|| = (􏰄n |x |p)1 = ⟨x, x⟩1 pi=1ip p
||x||1 = 􏰄ni=1 |xi| ||x||∞ = max |xi|
Euclidean norm – Distance
Ding Zhao (CMU)
M1-1: Linear Space 9 / 29

Norm Space Examples: Ball and Cone
Define a “ball” as “Unit ball” as
Define a ”cone” as
Visualization in 2-D:
Br(a)={x∈V :||x−a||=r} B1(0)={x∈V :||x||=1}
{(x,r)∈Rd+1 |∥x∥≤r,x∈Rd,r∈R}
Ding Zhao (CMU)
M1-1: Linear Space 10 / 29

Recap: Inner Products
Let(X,C)beavectorspace,afunction⟨·,·⟩:X ×X →Cisaninnerproductif 1 Conjugate symmetry:
2 Linearity in the first argument:
3 Positive definiteness:
⟨x, y⟩ = ⟨y, x⟩
⟨ax, y⟩ = a⟨x, y⟩
⟨x + y, z⟩ = ⟨x, z⟩ + ⟨y, z⟩
(1)
⟨x,x⟩ ≥ 0
⟨x, x⟩ = 0 ⇔ x = 0 .
(3) A vector space with a well-defined inner product is called an inner product (vector) space,
denoted as (X ,F,􏰅⟨,⟩)
Ding Zhao (CMU) M1-1: Linear Space
11 / 29
(2)

Recap: Angle between Vectors and Orthogonal
Inspired from the geometric space, the angle between two vectors is defined as: ⟨x, y⟩
∠ (x, y) = arccos 􏰅⟨x, x⟩􏰅⟨y, y⟩ For x, y ∈ V , we say that x and y are orthogonal if ∠(x, y) = 90◦
⟨x, y⟩ = cos(90◦) = 0 A set of vectors x = {x1, . . . , xn} is called orthonormal if
􏰉⟨xi,xj⟩=0, ∀i̸=j ⟨xi,xi⟩=1, 1􏰙i􏰙n
Ding Zhao (CMU) M1-1: Linear Space 12 / 29

Recap: Norm and Normed Space
A linear space (X , F ) is called normed if any real-valued function of x ∈ X , denoted by ∥x∥, can be defined with the following properties:
1 Positive definiteness:
∥x∥ is non-negative for every x and ∥x∥= 0 if and only if x = 0
2 Absolute homogeneity: ∥αx∥ = |α| ∥x∥, for any real α
3 Triangular inequality: ∥x1 + x2∥ ≤ ∥x1∥ + ∥x2∥
Ding Zhao (CMU) M1-1: Linear Space 13 / 29

Recap: p-norm, Ball, and Cone
p-norm
􏰌 􏰍1 np
||x||= 􏰑|x|p =⟨x,x⟩1 pip
i=1 ||x||=􏰄n |x|22=⟨x,x⟩1
􏰕 􏰖1 2i=1i 2
||x||1 = 􏰄ni=1 |xi| ||x||∞ = max |xi|
Ball: Cone:
Ding Zhao (CMU)
Br(a)={x∈V :||x−a||=r}
{(x,r)∈Rd+1 |∥x∥≤r,x∈Rd,r∈R}
M1-1: Linear Space 14 / 29

Module 1-1: Linear Space
Orthogonality
Linear Control Systems (2019)
Ding Zhao
Assistant Professor College of Engineering School of Computer Science
Carnegie Mellon University
Ding Zhao (CMU)
M1-1: Linear Space 15 / 29

Table of Contents
1 Inner product and norm
2 Orthogonal Bases (Gram-Schmidt Process)
3 Orthogonal Space
Ding Zhao (CMU) M1-1: Linear Space 16 / 29

Table of Contents
1 Inner product and norm
2 Orthogonal Bases (Gram-Schmidt Process)
3 Orthogonal Space
Ding Zhao (CMU) M1-1: Linear Space 17 / 29

Gram-Schmidt Process
Given a basis {y1, …, yn} find a new basis {v1, …, vn} that is orthonormal and is a basis for span {y1, …, yn}.
1 v1=y1
2 v2 =y2−a21v1 andchoosea21 suchthat⟨v1,v2⟩=0
0=⟨v1,v2⟩=⟨v1,y2⟩−a ⟨v1,v1⟩,a =⟨v1,y2⟩ =⟨v1,y2⟩
21 21 ⟨v1,v1⟩ ∥v1∥2
3 v3 = y3 −a31v1 −a32v2 and choose a31,and a32 such that ⟨v1,v3⟩ = 0 and ⟨v2,v3⟩ = 0 0=⟨v1,v3⟩=⟨v1,y3⟩−a ⟨v1,v1⟩−a ⟨v1,v2⟩⇒a = ⟨v1,y3⟩
31 32 31 ∥v1∥2 0=⟨v2,v3⟩=⟨v2,y3⟩−a ⟨v2,v1⟩−a ⟨v2,v2⟩⇒a = ⟨v2,y3⟩
Ding Zhao (CMU)
31 32 32 ∥v2∥2
M1-1: Linear Space 18 / 29

Gram-Schmidt Process (General Form)
Given a basis {y1, …, yn} find a new basis {v1, …, vn} that is orthonormal and is a basis for span {y1, …, yn}.
1 Generally: vk = yk − 􏰄k−1 ⟨vj,yk⟩ · vj j=1 ∥vj∥2
2 Normalize {v1,…,vn} as { v1 , v2 ,…, vn } to obtain an orthonormal set. ∥v2∥ ∥v2∥ ∥vn∥
Ding Zhao (CMU) M1-1: Linear Space 19 / 29

Example (OTB)
Ding Zhao (CMU) M1-1: Linear Space 20 / 29

QR Decomposition
Orthornormal basis spanning A = {y1, …, yn}
can be computed using Gram-Schmidt process
v1 =y1
v2=y2−⟨v1,y2⟩v1 ∥v1 ∥2
q1 = v1 ∥v1∥
q2= v2 ∥v2 ∥
The yis can be expressed over the newly computed orthonormal basis as
y1 =􏰓q1,y1􏰔q1 y2=􏰓q1,y2􏰔q1+􏰓q2,y2􏰔q2 y3=􏰓q1,y3􏰔q1+􏰓q2,y3􏰔q2+􏰓q3,y3􏰔q3
.
k
q =∥vk∥ yk=􏰑k 􏰗qj,yk􏰘qj
v3=y3−⟨v1,y3⟩v1−⟨v2,y3⟩v2 q3= v3
.
∥v1 ∥2 ∥v2 ∥2 k k 􏰄k−1 ⟨vj,yk⟩
.
∥v3 ∥ vk
v =y − j=1 ∥vj∥2
This can be written in matrix form as A = QR where
Q= q1 ··· qn Ding Zhao (CMU)
j=1
 􏰓q1,y1􏰔 􏰓q1,y2􏰔 􏰓q1,y3􏰔 ··· 
􏰈  0 􏰓q2,y2􏰔 􏰓q2,y3􏰔 ···  R= 0 0 􏰓q3,y3􏰔 … 
. . … ….
M1-1: Linear Space
􏰇
21 / 29

Table of Contents
1 Inner product and norm
2 Orthogonal Bases (Gram-Schmidt Process)
3 Orthogonal Space
Ding Zhao (CMU) M1-1: Linear Space 22 / 29

Orthogonal Complement Space
Ding Zhao (CMU) ”Interstellar” 23 / 29

Orthogonal Complement Space
Let (V ,F,􏰅⟨,⟩) be an inner product space. Let U ⊆ V be a subspace. U ⊥ = v ∈ V is the orthogonal complement of U , such that
∀u ∈ U , ⟨v, u⟩ = 0
Ding Zhao (CMU) M1-1: Linear Space 24 / 29

Sum of Spaces and Orthogonal Direct Sum
We can claim:
U⊥ ⊆V isasubspace
V =U 􏰎U⊥ =U 1 U⊥,where􏰎iscalledsumofspacesand 1 U⊥ iscalled orthogonal direct sum i.e.
∀x ∈ V , ∃x1 ∈ U , ∃x2 ∈ U ⊥, x = x1 + x2, and Dim(V ) = Dim(U ) + Dim(U ⊥)
􏰎􏰎
Ding Zhao (CMU) M1-1: Linear Space 25 / 29

Orthogonal Complement Examples

 􏰂10􏰃
 U = Span 0 , 1
 00 1⊥
   􏰂0􏰃


 
0
1
 􏰂 1 0 􏰃
U
 00 􏰎
= Span 0 , 1 
􏰂1􏰃


W = Span

⇒V=U W
1

0 1
⇒V =U􏰎U
Letx=x1,…,xn beabasisof V,V=Rn
􏰉
U = Span{x1,…,xk}
W =Span{xk+1,…,xn}


U ⊥ = Span
⇒V=U􏰎W
Ding Zhao (CMU)
M1-1: Linear Space
26 / 29

Orthogonal Projections
LetU beasubspaceofV withDimU