The magic of Artificial Neural Network — Part 3

8 min readMay 22, 2024

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 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 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 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 satisified and c·L(v) is also a continuous function ]

Clearly, the conditions of vector space are all satisified 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 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∥

Linear functional in C(Im)

For any normed space, if we can find a linear subspace and a continuous linear functional defined on this subspace, the Hahn-Banach theorem for Normed Space can be applied.

NS4. Let (V, ∥·∥) be the normed space. For all v∈V, there exists a continuous linear functional L:V→ℝ such that L(v) = ∥v∥ and ∥L∥ = 1

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∥ [ By setting λ=1 ]
∥L∥ = ∥l∥ = sup { |l(λv)|/∥λv∥: λv∈N } = sup { |λ∥v∥|/|λ|∥v∥: λv∈N } = 1

Remember that in part 2, we have proved that for a normed space V having a closed linear subspace N with norm ∥[x]∥’ = inf { ∥x-z∥ | z∈N }, then (V/N, ∥·∥’) is a quotient space which is still a normed space but having no subspace. All points within N is mapped to point 0 in the quotient space. We will use this feature to prove this theorem.

NS5. Let (V, ∥·∥) be the normed space and N⊆V be the closed linear subspace in V. Then, 1) there exists a continuous linear functional L:V→ℝ such that 2) L(w) = 0 ∀ w∈N and 3) L(v) = inf { ∥v-z∥ | z∈N } ∀ v∈V\N

Proof
1)
N⊆V be the closed linear subspace in V
=> (V/N, ∥·∥’) is a normed space [ By NS2 ]
=> ∀[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)=∥[w]∥’=∥[0]∥’=0 [ Since [w] = [0] and then by N2 ]
3)
∀v ∈ V\N, L(v)=∥[v]∥’ = inf { ∥v-z∥ | z∈N } [ by N2 ]

C(Im) is a Normed Space and Cl(S) ⊂ C(Im) is a closed linear subspace
[ By CL2 Cl(S) is closed ]
⇒ Continuous Linear functional L on C(Im) exists s.t.
L(h) = 0 ∀h∈Cl(S)
L(h) > 0 ∀h∈C(Im)\Cl(S) [ By NS5 and inf { ∥v-z∥ | z∈N } > 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, a continuous linear functional L on C(Im) exists where
L(h) = 0 ∀h∈Cl(S)
L(h) ≥ 0 ∀h∈C(Im)\Cl(S)

In the next article, we will continue our journey and finish the proof of the Universal Approximation Theorem.

Your feedback is highly appreciated and will help me to continue my articles.