Homework 2: Norms and Least Squares

CS/ECE/ME 532
Homework 2: Norms and Least Squares
1. Define the mapping Φ : R
n → R as
Φ(x) = max
1≤i≤n
i|xi
|.
Is Φ(x) a norm?
2. Equivalence of norms. For each case below find positive constants a and b (possibly
different in each case) so that for every x ∈ R
n
(i) akxk1 ≤ kxk2 ≤ bkxk1 (HINT: Use Cauchy-Schwarz inequality, which states that
for any vectors u, v, we have: u
T v ≤ kuk2kvk2 and a vector of all ones.)
(ii) akxk1 ≤ kxk∞ ≤ bkxk1
3. Let
A =



1 1 1
1 1 0
1 0 0


 .
a) What is the rank of A?
b) Suppose that y = Ax. Derive an explicit formula for x in terms of y.
4. Answer the following questions. Make sure to explain your reasoning.
a) Are the columns of the following matrix linearly independent?
A =





+0.92 +0.92
−0.92 +0.92
+0.92 −0.92
−0.92 −0.92





b) Are the columns of the following matrix linearly independent?
A =



+1 +1 +1
−1 +1 −1
+1 −1 −1



c) Are the columns of the following matrix linearly independent?
A =



1 2 2
3 4 5
5 6 8



1 of 3
d) What is the rank of the following matrix?
A =



+5 +2
−5 +2
+5 −2



e) Suppose the matrix in part c is used in the least squares optimization minx kb − Axk2.
Does a unique solution exist?
5. Consider the following matrix and vector:
A =



1 0
1 −1
0 1


 , b =



−1
2
1


 .
a) Find the solution xb to minx kb − Axk2.
b) Make a sketch of the geometry of this particular problem in R
3
, showing the columns of
A, the plane they span, the target vector b, the residual vector and the solution bb = Axb.
6. Polynomial fitting. Suppose we observe pairs of points (ai
, bi), i = 1, . . . , m. Imagine these
points are measurements from a scientific experiment. The variables ai are the experimental
conditions and the bi correspond to the measured response in each condition. Suppose we
wish to fit a degree d < m polynomial to these data. In other words, we want to find the
coefficients of a degree d polynomial p so that p(ai) ≈ bi for i = 1, 2, . . . , m. We will set this
up as a least-squares problem.
a) Suppose p is a degree d polynomial. Write the general expression for p(ai) = b.
b) Express the i = 1, . . . , m equations as a system in matrix form Ax = b. Specifically,
what is the form/structure of A in terms of the given ai
.
c) Write a Matlab or Python script to find the least-squares fit to the m = 30 data points
in
polydata.mat. Plot the points and the polynomial fits for d = 1, 2, 3.
7. Recall the cereal calorie prediction problem discussed in class. The data matrix for this
problem is
A =



25 0 1
20 1 2
40 1 6


 .
Each row contains the grams/serving of carbohydrates, fat, and protein, and each row corresponds to a different cereal (Frosted Flakes, Grape-Nuts, Teenage Mutant Ninja Turtles).
2 of 3
The total calories for each cereal are
b =



110
110
210


 .
a) Write a small program (e.g., in Matlab or Python) that solves the system of equations
Ax = b. Recall the solution x gives the calories/gram of carbohydrate, fat, or protein.
What is the solution?
b) The solution may not agree with the known calories/gram, which are 4 for carbs, 9 for
fat and 4 for protein. We suspect this may be due to rounding the grams to integers,
especially the fat grams. Assuming the true value for calories/gram is
x
? =



4
9
4


 ,
and that the total calories, grams of carbs, and grams of protein are correctly reported
above, determine the “correct” grams of fat in each cereal.
c) Now suppose that we predict total calories using a more refined breakdown of carbohydrates, into total carbohydrates, complex carbohydrates and sugars (simple carbs).
So now we will have 5 features to predict calories (the three carb features + fat and
protein). So let’s suppose we measure the grams of these features in 5 different cereals
to obtain this data matrix
A =








25 15 10 0 1
20 12 8 1 2
40 30 10 1 6
30 15 15 0 3
35 20 15 2 4








,
and the total calories in each cereal
b =








104
97
193
132
174








.
Can you solve Ax = b? Carefully examine the situation in this case. Is there a solution
that agrees with the true calories/gram?
3 of 3