Description
1 Convexity
For any −→x , −→y ∈ R
n
and any t ∈ [0, 1], a function f is said to be convex if it satisfies any of these
conditions:
• f(t
−→x + (1 − t)
−→y ) ≤ tf(
−→x ) + (1 − t)f(
−→y )
• If f is differentiable: f(
−→y ) ≥ f(
−→x ) + ∇f(
−→x ) · (
−→y −
−→x )
• If f is twice differentiable: Hf(
−→x ) ≥ 0
a) Given x ∈ R and only using the definition of convex functions given above, prove that the
rectified linear unit function, ReLU(x) := max(x, 0), is convex.
b) Given a A ∈ R
n×n
,
−→x ∈ R
n
,
−→b ∈ R
n
, and λ ≥ 0, prove that f(
−→x ) =
A
−→x +
−→b
2
+
λ k
−→x k1
is convex. For this part, you may use the following properties of convex functions:
•
P
i wifi(
−→x ) is convex if fi are convex and wi ≥ 0
• For any A ∈ R
n×n
and
−→b ∈ R
n
, g(
−→x ) = f(A
−→x +
−→b ) is convex if f is convex
• g(f(
−→x )) is convex if f is convex and g is convex and non-decreasing
c) Given x ∈ R, prove that the logistic function f(x) = 1
1+e−x is neither convex nor concave
(i.e. −f(x) is also not convex).
2 Taylor Expansion and Quadratic Form
a) Given x ∈ R and y ∈ R, consider the following function
h(x, y) = − cos(x
2
) + e
xy − 2y
2
(i) Compute the Gradient and Hessian matrix of h
(ii) Find the second order Taylor expansion of h at the point (x = x0, y = y0)
(iii) Simplify the equation from (b) at the point (x0 = 0, y0 = 0)
(iv) Use result from (c), determine the definiteness for the Hessian of h around the point
(x0 = 0, y0 = 0).
b) (i) Let −→x ,
−→b ∈ R
n
and M ∈ R
n×n be a symmetric and invertible matrix, prove the
following equation:
(
−→x − M−1−→b )
>M(
−→x − M−1−→b ) = −→x
>M−→x − 2
−→b
>−→x +
−→b
>M−1−→b
2
CMPT 726: Assignment 1 (Fall 2021) Instructor: Mo Chen
(ii) Given −→x ∈ R
n
, A, B ∈ R
n×n
,
−→µ ,
−→θ ∈ R
n
, let f(
−→x ) be the sum of two quadratic
forms:
f(
−→x ) = (−→x −
−→µ )
>A(
−→x −
−→µ ) + (−→x −
−→θ )
>B(
−→x −
−→θ )
Show that f can be written as a single quadratic form plus some constant term. (Hint:
use (i))
3 SVD and Eigendecomposition
a) Given a matrix A =
4 1
1 4
, find an analytical expression of An
. Show your work. (You are
allowed to use a computer to help you compute the eigenvalues/vectors for this part)
b) Consider the following matrix:
A =
1+4√
3
4
√
2
4−
√
3
4
√
2
4
√
3−1
4
√
2
4+√
3
4
√
2
!
(i) Show that the following is a Singular Value Decomposition of A:
√
2
2 −
√
2
√
2
2
2
√
2
2
!
2 0
0 1/2
√
3
2 −
1
2
1
2
√
3
2
!>
(ii) A matrix R ∈ R
2×2
is a 2D rotation matrix if it has the following form:
Rθ =
cos(θ) − sin(θ)
sin(θ) cos(θ)
where θ ∈ R
Geometrically speaking, Rθ
−→v rotates −→v counterclockwise by angle θ, for any −→v ∈ R
2
,
as shown in Figure 1.
Figure 1: In this case, −→x = (1, 0) and −→y = (0, 1) are both rotated by θ =
π
4
3
CMPT 726: Assignment 1 (Fall 2021) Instructor: Mo Chen
Show that U =
√
2
2 −
√
2
√
2
2
2
√
2
2
!
and V
> =
√
3
2 −
1
2
1
2
√
3
2
!>
are both rotation matrices, and
find their corresponding rotational angles θU and θV .
(iii) Give an explanation for all geometric transformations performed by the SVD of A. In
what order are the transformations performed?
(iv) The unit circle shown in Figure 2 has been transformed by a number of different 2D
transformations. The transformation results are shown in Figure 3.
Figure 2: unit circle and plane basis −→x , −→y
(a) (b)
4
CMPT 726: Assignment 1 (Fall 2021) Instructor: Mo Chen
(c) (d)
Figure 3: unit circle after different 2D transforms
Consider the geometric interpretation of the SVD for A. Which of the images from
Figure 3 correctly shows the transformation of the unit circle by A? (i.e. Which of the
matrices in the figure, A1, A2, A3, A4, is equal to A?) Please explain your choice.
5
