Homework 5: matrix norms and the SVD

CS/ECE/ME 532
Homework 5: matrix norms and the SVD

1. Induced norms. In class, we defined the induced 2-norm of a matrix A ∈ R
m×n as follows.
kAk = max
x6=0
kAxk2
kxk2
Prove that the induced 2-norm is indeed a norm.
2. Image of a circle. Plot the image of a unit circle in R
2 when each point is multiplied by A =

3 −2
−1 5

.
Also overlay the scaled left singular vectors σ1u1 and σ2u2 on your plot and verify that they line up
with the axes of the ellipse.
3. Dimension reduction. Load the file sdata.csv which contains a 1000 × 3 matrix of data. Each
row of the matrix is a point (xi
, yi
, zi) in R
3
. We will approximate this data set as an affine onedimensional space (a line that doesn’t pass through the origin).
a) Find the line that best approximates the data in the sense of minimizing the sum of the squares
of the projections of all points onto the line. Plot the line and the data on the same axes and
verify that the line approximates the points. Hint: before finding the line, shift every point so
that the data has zero mean. You can make 3D scatter plots in Matlab by using plot3.
b) Instead of using three numbers (xi
, yi
, zi) to describe each data point, we can now use a single
number wi
, which is the position along the line of the projected data point. Give a formula that
converts (x, y, z) to w and the reverse formula, which converts w to a point (x, y, z).
c) Convert the data set to wi coordinates, and plot a histogram of the {wi} to see how the points
are distributed. Use 20 equally spaced bins for the histogram.
4. Image compression. In this problem, we’ll use low-rank approximations to compress an image.
a) Load the file bucky.csv which contains a matrix A ∈ R
600×400 of grayscale values scaled to lie
between 0 and 1. Plot the image. In Matlab, you can do this via the commands:
A = csvread(’bucky.csv’);
figure; imagesc(A,[0 1])
colormap gray; axis image; axis off
b) Plot the singular values of A. What do you notice?
c) Approximate A as a rank r matrix by only keeping the r largest singular values and making the
rest zero. Try this for r ∈ {10, 20, 50, 100} and plot the corresponding compressed images.
d) Compare the space required to store the full A matrix with the space required to store the rank r
approximation of A; how many times smaller is the storage requirement for r ∈ {10, 20, 50, 100}?
You may assume that storage space requirements are proportional to the number of numbers
that must be stored. e.g. a 10 × 10 matrix contains 100 numbers.
1 of