Description
THEORY PROBLEMS
Problem 2.1 (Gram-Schmidt algorithm)
IALA Prob. 5.6.
Problem 2.2 (Computing projections in Euclidean space)
In this problem we use the notation ProjS
(x) to denote the projection of a vector x onto some set
S, which consists of vectors that are of same dimension as x. Consider the following vectors and
subspaces.
x1 =
”
3
−1
#
, b1 =
”
−1
1
#
, V1 = span (“1
2
#)
x2 =
2
1
−5
, b2 =
0
−3
−1
, V2 = span
0
0
−2
,
1
1
1
x3 =
3
0
−1
2
2
, b3 =
−1
0
1
−2
1
, V3 = span
0
1
2
0
0
,
1
3
0
1
0
,
0
1
5
0
1
(a) Compute ProjVi
(xi) for i = 1, 2, 3.
(b) Consider the affine set Ai = {v + bi
| v ∈ Vi}. Compute ProjAi
(xi) for i = 1, 2, 3.
(c) On a 2-d map, sketch the subspace V1 (a line through the origin) and clearly indicate x1 and
ProjV1
(x1). What is the point on V1 that is the closest to x1 in Euclidean sense? On the
same axes, sketch A1 (a line shifted from the origin) and indicate ProjA1
(x1).
(d) Compute an orthonormal basis B3 for the subspace V3 via Graham-Schmidt. Recompute
ProjV3
(x3) and ProjA3
(x3) using B3, and compare with your previous results.
Problem 2.3 (Taylor series expansion)
Consider the function f(x) = −
Pm
l=1 log(bl − a
T
l
x), where x ∈ R
n
, bl ∈ R and al ∈ R
n
. Compute
∇f(x) and ∇2f(x). Write down the first three terms of the Taylor series expansion of f(x) around
some x0.
Problem 2.4 (Distance between a pair of parallel hyperplanes)
Find the distance between the two parallel hyperplanes Hi
, i ∈ [2] where Hi = {x ∈ R
n
|a
T x = bi}.
Your solution should be expressed in terms of the problem parameters, i.e., the vector a ∈ R
n and
the scalars bi ∈ R. (Note: this problem is from “Convex Optimization”by Boyd and Vandenberghe.)
Problem 2.5 (Practice computing rank, range, nullspaces)
ECE367 Problem Sets © S. Draper, University of Toronto, 2021 page 3 of 10
University of Toronto ECE367 – Matrix Algebra & Optimization
(a) Find rank(A) and the dimension of, and a basis for, each of the four subspaces R(A), R(AT
),
N (A), N (AT
) when
A =
1 2 0 1
0 1 1 0
0 0 0 0
.
(b) Find rank(B) and the dimension of, and a basis for, each of the four subspaces R(B), R(BT
),
N (B), N (BT
) when
B =
1 2 0 1
0 1 1 0
1 2 0 1
.
(b) Find rank(C) and the dimension of, and a basis for, each of the four subspaces R(C), R(C
T
),
N (C), N (C
T
) when
C =
1 2 1 3
3 4 6 9
1 4 4 4
1 0 10 4
.
Problem 2.6 (Rank and nullspace)
OptM Problem 3.6.
Problem 2.7 (Linear dynamical systems)
OptM Problem 3.4.
APPLICATION PROBLEMS
Problem 2.8 (Approximating a square wave: The discrete-time Fourier series)
In this problem you will approximate a given discretized square wave signal using a sinusoidal
basis. The following MATLAB function produces the discrete approximation of two periods of a
period-10 square wave signal x(t) where t ∈ [0, 20], discretized in increments of 0.0001 seconds. In
addition, the script also produces 30 orthogonal basis vectors that we will later use to approximate
the given signal. The function returns two vectors time pos and sq wave, and a matrix B unnorm.
The vector sq wave consists of the signal output for each time position specified in time pos vector.
The matrix B unnorm includes 30 unnormalized row vectors that are of the same length as sq wave.
function [ time_pos , sq_wave , B_unnorm ] = generate_data
n_comps = 30; period = 10; fundFreq = 1/ period ;
time_pos = 0:0.0001:2* period ; harmonics = 2*(1: n_comps ) -1;
sq_wave = floor (0.9* sin (2* pi * fundFreq * time_pos ) ) +.5; % % generate the signal
B_unnorm = sin (2* pi * fundFreq *( harmonics ‘* time_pos ) ) /2; % % generate the basis
end
ECE367 Problem Sets © S. Draper, University of Toronto, 2021 page 4 of 10
University of Toronto ECE367 – Matrix Algebra & Optimization
(a) Plot the square wave signal sq wave against time pos.
(b) How would you numerically test for the orthogonality of the basis vectors (rows of B unnorm)?
Plot the first 6 and 30th basis vectors against time pos in separate sub-plots that share the
same time axis.
(c) Normalize the given basis vectors to obtain an orthonormal basis. Project the square wave
signal onto the normalized basis vectors using `2 projection and compute the projection coefficients. Arrange the basis vectors in the decreasing order of the magnitude of the projection
coefficients. Approximate the square wave using the first 1, 2, 3, 4, 5, 6, 30 basis vectors, and
plot the approximations in separate sub-plots that share the same time axis. Plot the original
signal on top of each approximation and compare.
Problem 2.9 (Projection with different norms)
Consider the vector x = [3, 2]T and the line defined by the set A = {v
(0) + tv | t ∈ R} where
v
(0) = [−2, −4]T and v = [−2, 5]T
. The projection of x on to the affine set A under `p norm, which
we denote by y
(p)
, is the minimizer of optimization problem
min
y
kx − ykp
subject to y ∈ A.
(a) Sketch the line A and indicate x on a 2-d map. Without solving for y
(2), sketch the smallest
norm ball under `2 norm that includes y
(2), and mark the position of y
(2)
.
(b) Write down the solution for y
(2) in closed-form and solve for y
(2)
.
(c) Repeat part (a) for p = 1 and p = ∞ cases.
(d) The solutions for y
(1) and y
(∞)
can not be expressed in closed-form, but they can be computed
using linear programs (LPs). In this part we use the software package CVX which runs in
MATLAB and is available at http://cvxr.com/cvx/. You may find the CVX package useful
throughout this course. For more information, please check the user guide available at the
above website.
As an example, after installing CVX, the following MATLAB function solves for y
(nrm)
. Execute the function with given parameters and verify your result obtained in part (b).
function [y , r ] = proj_cvx (x , v0 , v , nrm )% % x , v0 and v must be column vectors
objtv = @ ( y ) norm (x -y , nrm ) ; % % objective is L_2 norm
cvx_begin
variable y (2) % % 2 – d variable we are optimizing over
variable t (1) % % real valued parameter that defines
minimize ( objtv ( y ) ) % % defining the objective
subject to
v0 + t * v == y % % the projection y must be in set A
cvx_end
r = objtv ( y ) ; % % minimum value of the objective
end
(e) Use the given function to solve for y
(1) and y
(∞)
. Include your code (MATLAB, Python,
Julia) with the answers.
Problem 2.10 (First-order approximation of functions)
In this exercise you will write MATLAB (or Python, Julia, etc) code to plot linear approximations
each of three functions fi
: R
2 → R, i ∈ [3]. The three functions are defined pointwise as
f1(x, y) = 2x + 3y + 1,
f2(x, y) = x
2 + y
2 − xy − 5,
f3(x, y) = (x − 5) cos(y − 5) − (y − 5) sin(x − 5).
For each of the above function, do the following.
(a) Write down the gradient with respect to x and y in closed form. The gradient can be compactly
written in the form ∇fi =
h
∂fi
∂x
∂fi
∂y iT
for i = 1, 2, 3.
(b) For each function produce a 2-D contour plot indicating the level sets of each function in the
range −2 ≤ x, y ≤ 3.5 (i.e., make three plots). An example of a contour plot is illustrated in
Fig 2.28 of OptM (the second sub-figure). You may find meshgrid and contour commands in
MATLAB useful. Please refer the MATLAB documentation for further details. In addition,
compute the the gradient at the point (x, y) = (1, 0) for each function. On your contour plots
also plot the direction of the gradient and the tangent line to the level sets. Your resulting
plot should be analogous to Fig 2.29 of OptM.
(c) For the same point (x, y) = (1, 0) where, plot the 3-D linear approximation of the function.
Since we are considering only the first derivative, the approximation should be the tangent
plane at the specified point. Your plot for f2(x, y) should look something like Fig. 1. The
function approximation is plotted as a tangent plane to the surface plot of f2(x, y). You may
find meshgrid and meshc (or mesh) commands in MATLAB useful. Include your code for all
sections.
Note: We recommend you design these plotting scripts as functions (in MATLAB, Python, Julia)
so that you can reuse them for to plot approximations for different non-linear functions (or for
theses functions at different points). In either case make sure to attach your code.
-2 0 2
x
-2
-1
0
-20
-10
0
2
10
y
2
x
0
0
-2 -2
-2 0 2
x
-2
-1
0
-20
-10
0
2
y
10
2
x
0
0
-2 -2
-2 0 2
x
-2
-1
0
-20
0
2
y
2
20
x
0
0
-2 -2
Figure 1: Example plot and approximating tangent plane.
OPTIONAL PROBLEMS
Problem 2.11 (Inner products and projection in function spaces)
(Note: This problem can be solved analytically in closed-form or numerically. The former is
significantly more work. Both methods should yield the same final insight. Some tips about
numerical methods are given following the problem statement.)
While the focus of this course is on finite (and mostly real) vector spaces, notions of inner products
spaces and the approximation of a vector by its projection into a subspace, also hold for infinitedimensional vector spaces where each vector is a function f : R → R. In this problem let C[−π, π]
denote the set of continuous real-valued functions on [−π, π]. Observe that one can add and scale
functions pointwise, thereby defining C[−π, π] to be a vector space. We pick
hf, gi =
Z π
−π
f(x)g(x)dx (1)
to be the inner product of two functions f, g ∈ C[−π, π]. One can verify that all properties of an
inner product are satisfied by (1). The norm induced by this inner product is
kfk =
p
hf, fi =
sZ π
−π
(f(x))2dx.
In this problem you consider the the function g : [−π, π] → R defined pointwise as g(x) = sin(x).
Your task is to find the best approximation to g in the subspace of C[−π, π] that consists of polynomials with real coefficients and degree at most five. We denote this subspace as U = {u|u(x) =
α0 + α1x + α2x
2 + α3x
3 + α4x
4 + α5x
5
, αi ∈ R ∀ i ∈ {0, 1, . . . 5}}. By best we mean that the
optimizing u
∗
is
u
∗ = arg min
u∈U
kg − uk
2
.
where, to be explicit,
kg − uk
2 = hg − u, g − ui =
Z π
−π
(g(x) − u(x))2
dx =
Z π
−π
(sin(x) − u(x))2
dx.
In the following you are asked to apply the Gram-Schmidt procedure to produce an orthogonal
basis. You are welcome to do this either numerically or analytically. By “numerically” we mean
you are welcome to use a numerical integration technique to compute the integrations involved in
the inner products. The integrations can be computed analytically to produce closed-form solutions,
but it is a non-trivial amount of work. However you chose to do it, please do the following.
(a) First apply the Gram-Schmidt procedure using the inner production defined in (1) to the basis
{v
(0), v(1), v(2), v(3), v(4), v(5)} of U where, defined pointwise, v
(i)
(x) = x
i
, i ∈ {0, 1, 2, 3, 4, 5}
to produce an orthonormal basis {e
(0), e(1), e(2), e(3), e(4), e(5)} where each e
(i) ∈ C[−π, π].
(b) Next, using (1) and the formulas for `2 projection we developed in class (which apply again
here), compute α0, . . . , α5. (To check correctness note that, up to numerical precision, you
should find that α1 = 0.987862.)
(c) You should see a sensical pattern to the even coefficients α0, α2, α4. What is the pattern you
observe and why is it intuitively correct?
(d) Another often used polynomial approximation to the sin x function the Taylor approximation
sin x ‘ x −
x
3
3! +
x
5
5! .
Plot your approximation from part (b) against the Taylor approximation. You should observe
that your approximation looks much better over the entire interval [−π, π]. Where is the Taylor approximation accurate and where is it not accurate? What was it about the formulation
of the `2 projection problem that makes your approximation better in the regions where the
Taylor approximation is not good?
While you are welcome to use any method to perform the integration in 1, we describe below two numerical methods that you may use. The following MATLAB code snippet defines a few anonymous
functions that help us compute the inner product of two functions. We use anonymous functions
since they do not have to be defined in separate .m files. Please read MATLAB documentation for
further information about this type of functions. Executing the following piece of code will print
to console hsin, v(3)i and k sin k. The purpose of each line of code is explained in the comments.
% % divide the interval [ – pi , pi ] into 1000 small intervals
eps = 1000;
xi = – pi : pi / eps : pi ;
dx = pi / eps ;
% % utility functions
intgrt = @ (f , g ) dot ( f ( xi ) ,g ( xi ) ) * dx ; % discrete approx . of the continous integral
inprod = @ (f , g ) intgrt (f , g ) ; % compute inner product between f and g
normf = @ ( f ) sqrt ( inprod (f , f ) ) ; % compute the norm of f
% % test
sx = @ ( x ) sin ( x ) ;
v3 = @ ( x ) x .^3;
inprod ( sx , v3 ) % prints the inner product < sin ( x ) , x ^3 >
normf ( sx ) % prints the norm of sin ( x )
Alternatively, you may use MATLAB symbolic functions to implement g, v(0), . . . , v(5), and use the
built-in int command to perform the integration.
Problem 2.12 (The matrix of a linear map)
In the setup of this problem we prove that any linear map between vector spaces can be represented
by a matrix. You will then extend that reason to show that any linear function on a vector space
can be represented by a vector and you will show that the way matrix-matrix multiplication is
defined follows from the concatenation of any pair of compatible linear maps.
In this problem we work with a triplet of vector spaces V, W and U where dim(V) = n, dim(W) = m,
and dim(U) = p. Let {v
(i)}i∈[n] = basis(V), {w
(i)}i∈[m] = basis(W), and {u
(i)}i∈[p] = basis(U). We
first recall the definition of a linear map, e.g,. from V to W.
Definition 1. A map f : V → W is “linear” if for any two points x
(i) ∈ V, i ∈ [2], and scalings
αi, i ∈ [2]
f(α1x
(1) + α2x
(2)) = α1f(x
(1)) + α2f(x
(2)).
To introduce you to the perspectives we need in this problem we now show that any linear map f
can be fully specified by an m×n matrix of coefficients. First note that any x ∈ V can be expressed
in terms the the basis elements of V as x =
P
i∈[n] αiv
(i)
for some choice of the αi
. Next, we have
f(x) = f
Xn
i=1
αiv
(i)
!
(i)
=
Xn
i=1
αif(v
(i)
) (2)
(ii)
=
Xn
i=1
αi
“Xm
k=1
β
(i)
k w
(k)
#
, (3)
where (i) follows by the linearity of f and the β
(i)
k
in (ii) are the coefficients associated with the
basis elements of W that represent f(v
(i)
) ∈ W, the point in W to which the ith basis element of
V maps. (Note that this point need not itself be a basis element of W.) Expanding this out in
matrix form we find that
f(x) = h
w
(1)w
(2) . . . w(m)
i
β
(1)
1
β
(2)
1
. . . β(n)
1
β
(1)
2
β
(2)
2
. . . β(n)
2
.
.
.
.
.
.
.
.
.
β
(1)
m β
(2)
m . . . β(n)
m
α1
α2
.
.
.
αn
. (4)
Hence, any linear operator f can be represented by a matrix that relates the basis of the input
space to the basis of the output space. If one changes the linear operator then, naturally, the matrix
changes. However, one should also note that if one changes either the basis that represents the
input space or the basis that represents the output space the matrix will also change. Thus the
representation of a linear map by a matrix is not dependent solely on f but also on the bases used
to describe points in the input and output spaces. To make this dependence explicit, one therefore
denotes the matrix of the linear map f as M(f, {v
(1), . . . v(n)}, {w
(1), . . . , w(m)}). Most of the time
one writes down a matrix the bases are not specified which (typically) means that the standard
basis is being assumed. Indeed, often when introducing matrices in linear algebra it is not even
made explicit that one is using the standard basis to parameterize the input and output spaces
of the mapping that the matrix describes. The problem framing above makes that choice explicit
and, of course, and one need not have made that (perhaps unknowing) assumption.
The above was a bit hard to work into a problem for you to solve, so we simply provided the
framework, derivation, and discussion. Now for the work. In the next part you consider linear
functions (rather than maps) and then extend the above logic and see what happens when you
concatenate a pair of linear maps.
(a) Based on the logic above argue why any linear function can be represented by a vector. (Hint:
Yes, this part is as easy as it seems.)
(b) Now, let f : V → W be as in the problem introduction. In addition let g : W → U. Following
the same logic as in the problem introduction, find an expression for g(f(x)) of the form
g(f(x)) = Pp
l=1 ζlu
(l)
. (Note that g(f(x)) ∈ U and {u
(1), . . . u(p)} is a basis for U.) (Hint:
Your expression should contain three sums, one of n terms, one of m terms, and one of p
terms.)
(c) Look at your expressions for the ζl
from part (b) and rewrite in a form that involves two
vectors and two matrices. You should now see why matrix-matrix multiplication is defined
in the way that it is.
