The magic of Artificial Neural Network — Part 3
This is my third article on the magic of the Artificial Neural Network. I have sketched the proof of the Universal Approximation Theorem and introduce the Hahn-Banach theorem in part 2. Let’s continue our journey into the territory of Function Analysis…
Hahn-Banach theorem for the Vector Space
By using the Hahn-Banach Theorem, the linear functional defined on a vector subspace of some vector space can be extended to the whole space when the linear functional is dominated by a Sublinear Function. So, what is a Sublinear Function ?
A Sublinear Function p on a real vector space V is a function p:V→ℝ, which satisfies the following properties:
∀v, w∈V, c∈ℝ
SF1. p(v+w) ≤ p(v)+p(w)
SF2. c·p(v) = p(c·v) where c > 0
Below is the description of Hahn-Banach Theorem for vector space:
HA. Let V be the vector space and S⊆V be the linear subspace in V. Let l:S→ℝ be a linear functional defined on S. Let p:V→ℝbe a sublinear function defined on V such that l(v) ≤ p(v) ∀v∈S. Then, 1) there is a linear functional L:V→ℝ s.t. 2) L(v)=l(v) ∀ v∈S and 3) L(v) ≤ p(v) ∀v∈V.
Proof
Please read this article if you are interested in the proof.
Linear functional in the Normed Space
For the linear functional in the normed space V, since V is also a topological space, we can define the condition where the functional is continuous or bounded. For the detail definition of continuous function, you can read this article.
A Linear Functional L on a real vector space V is a function L:V→ℝ, which satisfies the following properties:
∀v, w∈V, c∈ℝ
LF1. L(v+w)=L(v)+L(w)
LF2. c·L(v)=L(c·v)
LF3. A linear functional L:V→ℝ is said to be continuous at v0 ∈ V if
∀ε>0, ∃δ>0 such that |L(v)−L(v0)| < ε whenever ∥v−v0∥ < δ where v ∈ V
LF4. A linear functional L:V→ℝ is said to be continuous if it is continuous at v0 ∀v0 ∈ V
LF5. A linear functional L:V→ℝ is said to be bounded if
∃K > 0 such that ∀v ∈ V, |L(v)| ≤ K ∥v∥
LF6. Linear functional L is bounded iff L is continuous
Proof
(only if)
∀v0, v ∈ V, ε>0
=> |L(v-v0)| ≤ K ∥v-v0∥ [ since v-v0 ∈ V ]
=> |L(v)-L(v0)| ≤ K ∥v-v0∥ < ε whenever ∥v-v0∥ < ε/K where ε/K > 0
=> L is continuous at v0 => L is continuous [ Since v0 can be any point ]
(if)
L is continuous => L is continuous at 0
=> ∀ε>0, v ∈ V, |L(v)-L(0)| < ε whenever ∥v-0∥ < δ for some δ > 0
=> |L(v)| < 1 whenever ∥v∥ < δ for some δ > 0 [ since L(0) = 0 and put ε = 1 ]
Let w = (δ/2) (v/∥v∥) with v ≠ 0
∥w∥ = ∥ (δ/2) (v/∥v∥) ∥ = (δ/2)(1/∥v∥)∥v∥ = δ/2 < δ
=> |L(w)| < 1
=> |L((δ/2) (v/∥v∥))| < 1
=> (δ/2)(1/∥v∥) |L(v)| < 1 => |L(v)| < 2/δ ∥v∥
=> |L(v)| ≤ 2/δ ∥v∥ where 2/δ > 0 [ for v = 0, |L(v)| = 2/δ ∥v∥ ]
=> L is bounded
Norm of the Continuous Linear Functional
Can the set of all continuous linear functional defined on the normed space V form a new vector space? The answer is Yes if we define the operations + and · as follows:
Let V be the normed space and V* be the set of all continuous linear functional defined on V.
For any continuous linear functionals L,G: V → R, and any c in R :
(L+G)(v) = L(v) + G(v), (c·L)(v) = c·L(v) ∀ v∈V
The above operation definition is valid, L+G and c·L are still continuous linear functional
Proof
∀L, G ∈ V*
LF1:
∀v, w∈V
(L+G)(v+w)=L(v+w)+G(v+w)
=L(v)+L(w)+G(v)+G(w)=L(v)+G(v)+L(w)+G(w)
=(L+G)(v)+(L+G)(w)
LF2:
∀v∈V, c∈ℝ
c·(L+G)(v)=c·(L(v)+G(v))
=c·L(v)+c·G(v)=L(c·v)+G(c·v)
=(L+G)(c·v)
=> L+G ∈ V* [ Since LF1, LF2 are satisified and L(v)+G(v) is also a continuous function ]
∀L∈V*, a∈ℝ
LF1:
∀v, w∈V
(a·L)(v+w)=a·L(v+w)
=a·(L(v)+L(w))=a·L(v)+a·L(w)
=(a·L)(v)+(a·L)(w)
LF2:
∀v∈V, c∈ℝ
c·(a·L)(v)=c·(a·L(v))=(c·a)·L(v)=a·L(c·v)
=(a·L)(c·v)
=> a·L ∈ V* [ Since LF1, LF2 are satisfied and c·L(v) is also a continuous function ]
Clearly, the conditions of vector space are all satisfied since continuous linear functional is just a continuous function. Therefore, the set V* is a Vector Space.
Now, we define the norm for this vector space V* as follows:
Define ∥·∥: V* → ℝ, for any L ∈ V*
∥L∥ = sup { |L(v)|/∥v∥ | v ∈ V and v ≠ 0 }
∥·∥ is a norm.
Proof
∀L ∈ V*
=> L is continuous => L is bounded [ By LF6 ]
=> ∃ K>0 s.t. |L(v)| ≤ K∥v∥ ∀v∈V
=> ∀v∈V and v ≠ 0, ∃ K>0 s.t. |L(v)|/∥v∥ ≤ K
=> ∥L∥ = sup{ |L(v)|/∥v∥ | v∈V and v ≠ 0 } exists and thus well defined [ By Greatest Lower Bound Property ]
N1: ∥L∥ ≥ 0 [ Since |L(v)|/∥v∥ > 0 ∀v∈V and v ≠ 0 ]
N2: ∥L∥ = 0 iff L(v) = 0 ∀v∈V
N3: ∥c·L∥ = sup { |c·L(v)| | v ∈ V and v ≠ 0 }
= sup { |c|·|L(v)|/∥v∥ | v ∈ V and v ≠ 0 }
= |c| sup { |L(v)|/∥v∥ | v ∈ V and v ≠ 0 }
= |c| ∥L∥
N4: ∥L+G∥ = sup { |(L+G)(v)|/∥v∥ | v ∈ V and v ≠ 0 }
= sup { |(L+G)(v)|/∥v∥ | v ∈ V and v ≠ 0 }
= sup { |L(v)+G(v)|/∥v∥ | v ∈ V and v ≠ 0 }
≤ sup { |L(v)|/∥v∥ + |G(v)|/∥v∥ | v ∈ V and v ≠ 0 }
≤ sup { |L(v)|/∥v∥ | v ∈ V and v ≠ 0 } + sup { |G(v)|/∥v∥ | v ∈ V and v ≠ 0 }=∥L∥+∥G∥
=> ∥·∥ is a norm, thus (V*, ∥·∥) is a normed space
Hahn-Banach theorem for the Normed Space
For the linear functional defined on a linear subspace of the normed space, it can be extended to the whole space when it is continuous. No dominating Sublinear Function is required in this case. Below is the description of Hahn-Banach Theorem for normed space:
NS3. Let (V, ∥·∥) be the normed space and N⊆V be the subspace in V. Let l:N→ℝ be a continuous linear functional defined on N. Then, there is a continuous linear functional L:V->ℝ such that l(v) = L(v) ∀ v∈N and ∥l∥ = ∥L∥
Proof
1)Let’s find the sublinear function p and then apply the Hahn-Banach theorem:
l:N→ℝ is a continuous linear functional on N
=> l is bounded [ By LF6 ]
=> l(v) ≤ |l(v)| ≤ ∥l∥∥v∥ ∀v∈N [ Since ∥l∥ = sup { |l(v)|/∥v∥ | v ∈ V and v ≠ 0 } ]
Let p(v) = ∥l∥∥v∥ ∀ v∈V
∀v, w∈V, c∈ℝ and c > 0
SF1:
p(v+w) = ∥l∥∥v+w∥ ≤ ∥l∥(∥v∥+∥w∥) = ∥l∥∥u∥ + ∥l∥∥v∥ = p(u)+p(v)
SF2:
p(cv) = ∥l∥∥cv∥ = |c|∥l∥∥v∥ = cp(v)
=> p is sublinear function defined on V and l(v) ≤ p(v) ∀v∈N
=> There is a linear functional L:V→ℝ such that L(v)=l(v) ∀ v∈N and L(v) ≤ p(v) ∀v∈V [ By HA ]
2)L is bounded:
L(-v)≤ p(-v) => -L(v) ≤ p(v) => L(v) ≥ -p(v)
=> |L(v)| ≤ p(v) = ∥l∥∥v∥ ∀ v∈V
3)∥L∥ = ∥l∥
{ |L(v)|/∥v∥ | v∈N } ⊆ { |L(v)|/∥v∥ | v∈V }
=> { |l(v)|/∥v∥ | v∈N } ⊆ { |L(v)|/∥v∥ | v∈V } [ By L(v)=l(v) ∀ v∈N ]
=> sup{ |l(v)|/∥v∥ | v∈N } ≤ sup{ |L(v)|/∥v∥ | v∈V }
=> ∥l∥ ≤ ∥L∥
∀v∈V, |L(v)|/∥v∥ ≤ ∥l∥
=> sup{ |L(v)|/∥v∥ | v∈V } ≤ ∥l∥ [ By Greatest Lower Bound Property ]
=> ∥L∥ ≤ ∥l∥
=> ∥l∥ = ∥L∥
A Vector in the Normed Space
For any vector in the normed space, we can always find a continuous linear functional which has nice property on this vector.
NS4. Let (V, ∥·∥) be the normed space. For v∈V and v≠0, there exists a continuous linear functional L:V→ℝ such that L(v) = ∥v∥ and ∥L∥ = 1 [Note that v is fixed]
Proof
Let’s find the linear subspace and the corresponding linear functional.
Let N = { λv | λ ∈ ℝ}
∀ λ, μ ∈ ℝ, λv, μv ∈ N
λv+μv = (λ+μ)v ∈ N, λ(μv) = (λμ)v ∈ N
=> N is a linear subspace spanned by v ∈V
Let l: N→ℝ with
l(λv) = λ∥v∥ where λv ∈ N for some λ ∈ ℝ
∀ λ, μ ∈ ℝ, λv, μv ∈ N
LF1:
l(λv+μv)=l((λ+μ)v) = (λ+μ)∥v∥ = λ∥v∥+μ∥v∥ = l(λv)+l(μv)
LF2:
l(λ(μv))=(λμ)∥v∥ = λ(μ∥v∥) = λl(μv)
=> l is a continuous linear functional [ Since λ∥v∥ is a continuous function of λ, please refer to this article for details ]
=> There is a continuous linear functional L:V→ℝ such that
l(w)=L(w) ∀ w∈N and ∥l∥ = ∥L∥ [ By NS3 ]
=> L(v)=l(v)= ∥v∥ [ Consider when λ=1 ]
∥L∥ = ∥l∥ = sup { |l(λv)|/∥λv∥: λv∈N } = sup { |λ∥v∥|/|λ|∥v∥: λv∈N } = sup {1} = 1
NS5. Let (V, ∥·∥) be the normed space. For v1,v2∈V, v1≠v2, there exists a continuous linear functional L:V→ℝ such that L(v1)≠L(v2) [ Note that v1 and v2 are fixed ]
Proof
v1≠v2 => v1-v2 ≠ 0
=> There exists a continuous linear functional L:V→ℝ s.t. L(v1-v2) = ∥v1-v2∥ [ By NS4 ]
=> L(v1)-L(v2)=L(v1-v2)=∥v1-v2∥ ≠ 0
=> L(v1)≠L(v2)
A Closed Linear Subspace in the Normed Space
Suppose there is a linear subspace in the normed space. What will happen when it is closed ? Remember that in part 2, we have proved the following theorem:
NS2. Let V be a normed space and N⊆V be the closed linear subspace in V.
Then (V/N, ∥·∥’) is a normed space.
We will use this feature to prove this theorem.
NS6. Let (V, ∥·∥) be the normed space, N⊆V be the closed linear subspace in V and v∈V\N. Then, 1) there exists a continuous linear functional L:V→ℝ such that 2) L(w) = 0 ∀ w∈N and 3) L(v) ≠ 0 [ Note that v is fixed ]
Proof
1)
N⊆V be the closed linear subspace in V
=> (V/N, ∥·∥’) is a normed space [ By NS2 ]
=> For [v] ∈ V/N, there exists a continuous linear functional L’:V/N→ℝ such that L’([v])=∥[v]∥’ [ By NS4 ]
Let L:V→ℝ with
L(v) = L’([v]) where v∈V
L is clearly well defined. Next is to prove that it is continuous and linear.
L’ is continuous
=> L’ is bounded [ By LF6 ]
=> ∃K > 0 s.t. ∀[v] ∈ V/N, |L(v)| = |L’([v])| ≤ K ∥[v]∥’ = K inf { ∥v-z∥ | z∈N }
=> |L(v)|/K ≤ inf { ∥v-z∥ | z∈N } ≤ ∥v-0∥ [ By Greatest Lower Bound Property and z=0 ∈ N ]
=> |L(v)| ≤ K ∥v∥
=> L is bounded => L is continuous [ By LF6 ]
∀v, w∈V, c∈ℝ
LF1. L(v+w)=L’([v+w])=L’([v]+[w])=L’([v])+L’([w])=L(v)+L(w)
LF2. c·L(v)=c·L’([v])=L’(c*[v])=L’([c·v])=L(c·v)
=> L is a continuous linear functional
2)
∀w ∈ N, L(w)=L’([w])=L’([0])=L(0)=0 [ L(0) = L(0+0) = L(0) + L(0), L(0)=0 ]
3)
v ∈ V\N, 0∈N => [v] ≠ [0] => L’([v]) ≠ L’([0]) [ By NS5 ]
=> L(v) ≠ L(0)
=> L(v) ≠ 0
C(Im) is a Normed Space and Cl(S) ⊂ C(Im) is a closed linear subspace
[ By CL2 Cl(S) is closed ]
⇒ For h∈C(Im)\Cl(S), there exists Continuous Linear functional L on C(Im) such that
L(w) = 0 ∀w∈Cl(S)
L(h) ≠ 0 [ By NS6 ]
A Dense set in the Normed Space
Suppose there is a linear subspace in the normed space. What will happen when it is dense ?
NS7. Let (V, ∥·∥) be the normed space, N⊆V be the linear subspace in V.
N is dense in V iff for every continuous linear functional L:V→ℝ,
L(w) = 0 ∀w∈N => L=0
Proof
(only if)
N is dense in V
=> ∀ v∈V, e > 0, o(v, e)∩N ≠ ø [ o(v, e) is a neighbourhood of v and by DS3 ]
=> ∃v0 ∈ o(v,e)∩N s.t. v0 ∈ N and ∥v0-v∥ < e [ By the definition of o(v, e) ]
=> L(v0) = 0 [ Since v0 ∈ N ]
L is continuous
=> ∃ K > 0 s.t. |L(v)| ≤ K ∥v∥ [ By LF6 and then LF5 ]
=> |L(v0-v)| = |L(v0)-L(v)| ≤ K ∥v0-v∥ < Ke [ By LF1 and LF2 ]
=> |0-L(v)| < Ke => |L(v)| < Ke for any e
=> |L(v)| < Ke for any e > 0
Suppose |L(v)| > 0
=> ∃ n ∈ N s.t. Ke / |L(v)| < n [ By Archimedean Property ]
=> |L(v)| > K(e/n) where e/n > 0 => contradiction
=> |L(v)| = 0 => L=0
(if)
Suppose Cl(N) ⊂ V
Cl(N) is closed [ By CL2 ]
=> For any v ∈ V\N, there exists a continuous linear functional L:V→ℝ s.t. L(w) = 0 ∀ w∈N and L(v) ≠ 0 [ By NS6 ]
=> L(v) ≠ 0 contradict L(v)= 0
Conclusion
In this post, the Hahn-Banach theorem for normed space is proved and its application on the C(lm) having the closed linear subspace Cl(S) has been discussed. We find that under this condition, for h∈C(Im)\Cl(S), there is a continuous linear functional L on C(Im) such that
L(w) = 0 ∀w∈Cl(S)
L(h) ≠ 0
Your feedback is highly appreciated and will help me to continue my articles.
Please give this post a clap if you like this post. Thanks!!
Reference:
“https://en.wikipedia.org/wiki/Vector_space”
“https://en.wikipedia.org/wiki/Linear_subspace”
“https://en.wikipedia.org/wiki/Functional_analysis”
“https://en.wikipedia.org/wiki/Hahn_Banach_theorem”
“https://www.proofwiki.org/wiki/Definition:Linear_Functional”
“https://en.wikipedia.org/wiki/Infimum_and_supremum”