Homework 6: more SVD

CS/ECE/ME 532
Homework 6: more SVD

1. Normal equations. Using the SVD, show that for any A ∈ R
m×n and b ∈ R
m, the normal equations
ATAx = ATb always have at least one solution. What is this solution?
2. Right inverses. A right inverse of A ∈ R
m×n
is a matrix B ∈ R
n×m such that AB = I.
a) Prove that if the rows of A are linearly independent, A has a right inverse.
b) Prove that if A has a right inverse, the rows of A are linearly independent.
c) Suppose A has linearly independent rows. Find a parameterization of all right inverses of A.
3. Recovering a blurred signal. Many sensing and imaging systems produce signals that may be
slightly distorted or blurred (e.g., an out-of-focus camera). In such situations, algorithms are needed
to deblur the data to obtain a more accurate estimate of the true signal. Suppose our true signal is
a vector x ∈ R
n
, and the blurring produces a new signal b ∈ R
n according to the model:
bi =
1
k

xi + xi−1 + · · · + xi−k+1

+ wi for i = 1, . . . , n
In other words, each bi
is the average of the past k values of xi
, plus some extra noise wi
. Note: in
the above formula, treat xj as zero when j < 1. The goal is to estimate x using b and A.
a) We can write the above equations in the more compact form: b = Ax + w. Write code that
generates the A ∈ R
n×n matrix as a function of n and k.
b) Suppose the true x is given in the file xsignal.csv. Generate b by using k = 30. To generate w,
make each wi normally distributed with standard deviation σ. For example, you can do this in
matlab via: w=sigma*randn(n,1). Plot x and b using σ = 0.01 and σ = 0.1.
c) Reconstruct x in the three following ways, and for each one plot the true x and its reconstruction.
(i) Ordinary least squares
(ii) Truncated SVD; only keep the largest m singular values of A and try different values of m.
(iii) Regularized (Tikhonov) least squares; try different values of the parameter λ.
d) Experiment with different averaging functions (i.e., different values of k in the code) and with
different noise levels (σ in the code). How do the blurring and noise level affect the value of the
regularization parameters that produce the best estimates?
1 of