L4_ProxGrad.pdf

Proximal Gradient Methods

Vuong Phan
University of Southampton, UK



April 24, 2023






,I. Some preliminaries






,Real vector space. A vector space E over R is a set of elements
(which are called “vectors”) such that:
(A) For any x, y ∈ E, there corresponds a “sum” x + y that
satisfies the following properties
▶ x + y = y + x for any x, y ∈ E.
▶ x + (y + z) = (x + y) + z for any x, y, z ∈ E.
▶ There exists a unique “zero vector” 0 in E such that x + 0 = x
for any x.
▶ For any x ∈ E, there exists −x ∈ E such that x + (−x) = 0.
(B) For any scalar (real number) a ∈ R and x ∈ E, there
corresponds a “scalar multiplication” ax satisfying the
following properties
▶ a(bx) = (ab)x for any a, b ∈ R, x ∈ E.
▶ 1x = x for any x ∈ E.
(C) The summation and scalar multiplication satisfy the following
properties
▶ a(x + y) = ax + ay for any a ∈ R, x, y ∈ E.
▶ (a + b)x = ax + bx for any a, bR, x ∈ E.



, Basis. A basis of a vector space E is a set of linearly independent
vectors {v1 , v2 , . . . , vn } that spans E: for any x ∈ E, there exists
β1 , . . . , βn ∈ R such that
n
X
x= βi vi .
i=1

Dimension. The dimension of a vector space E is the number of
vectors in a basis of E.

Norms. A norm ∥ · ∥ on a vector space E is a function
∥ · ∥ : E → R satisfying the following properties:
▶ (nonnegativity) ∥x∥ ≥ 0 for any x ∈ E and ∥x∥ = 0 if and
only if x = 0.
▶ (positive homogeneity) ∥ax∥ = |a|∥x∥ for any x ∈ E and
a ∈ R.
▶ (triangle inequality)∥x + y∥ ≤ ∥x∥ + ∥y∥ for any x, y ∈ E.