Homework 0 solutions
CS229T/STATS231
1. Linear algebra (0 points)
a (dual norm of L1 norm) The L1 norm k · k1 of a vector v 2 Rn is defined as
kvk1 =
nX i
=1
jvij: (1)
The dual norm k · k∗ of a norm k · k is defined as
kvk∗ = sup
kwk≤1
(v · w): (2)
Compute the dual norm of th...
homework 0 solutions cs229tstats231 1 linear algebra 0 points a dual norm of l1 norm the l1 norm k · k1 of a vector v 2 rn is defined as kvk1 nx i 1 jvij 1 the dual norm k · k∗ of a norm
Written for
Stanford University
STATS 231
All documents for this subject (4)
Seller
Follow
Themanehoppe
Reviews received
Content preview
Homework 0 solutions
CS229T/STATS231 (Fall 2018–2019)
Note: please do not copy or distribute.
Due date: 10/03/2018, 11pm
This is a diagnostic homework and will not count towards your grade (but the bonus points do count).
It should give you an idea of the types of concepts and skills required for the course, and also give you an
opportunity to practice some things in case you’re rusty. It also will allow you to see how we grade.
1. Linear algebra (0 points)
a (dual norm of L1 norm) The L1 norm k · k1 of a vector v ∈ Rn is defined as
n
X
kvk1 = |vi |. (1)
i=1
The dual norm k · k∗ of a norm k · k is defined as
kvk∗ = sup (v · w). (2)
kwk≤1
Compute the dual norm of the L1 norm. (Here v · w denotes the inner product between v and w: v · w ,
P n
i=1 vi wi )
Solution:
We will prove that
sup (v · w) = max vi = kvk∞ (3)
kwk1 ≤1 i∈[n]
which implies that the dual norm of L1 norm is L∞ norm.
Towards proving (3), we first observe that
n
X n
X
v·w = vi w i ≤ |vi | · |wi | (4)
i=1 i=1
Xn
≤ kvk∞ · |wi | (5)
i=1
= kvk∞ kwk1 (6)
(7)
Therefore,
sup (v · w) ≤ kvk∞ (8)
kwk1 ≤1
1
, We argue equality can be attained: let i? be such that vi? = arg maxi |vi | = kvk∞ , then setting w = ei?
(where ei denotes the vector with 1 on the i-th coordinate and 0 elsewhere) gives (v · w) = kvk∞ . Thus we
complete the proof of equation (3).
Remarks: dual norms are useful to bound inner products: u · v ≤ kukkvk∗ , which follows directly from the
definition of the dual norm. This is a generalization of the Cauchy-Schwartz inequality (which is for the L2
norm).
In general, the Lp norm and the Lq norm are dual when 1/p + 1/q = 1.
Pnb (trace is sum of singular values) The nuclear norm of a matrix A ∈ Rn×n is defined as
i=1 |σi (A)|, where the σ1 (A), . . . , σn (A) are the singular values of A. Show
Pn that the nuclear norm of a
symmetric positive semi-definite matrix A is equal to its trace (tr(A) = i=1 Aii ). (For this reason, the
nuclear norm is sometimes called the trace norm.) (Hint: use the fact that tr(AB) = tr(BA).)
Solution:
As A is PSD, the SV D of A has the form A = U SU > . Using the trace rotation trick,
X X
tr(A) = tr(U SU > ) = tr(U > U S) = tr(IS) = σi (A) = |σi (A)|. (9)
i i
The last equality used that singular values are non-negative.
c. (3 bonus points) (trace is bounded by nuclear norm) Show that the trace of a square matrix
A ∈ Rn×n is always less than or equal to its nuclear norm.
Solution:
Suppose the SVD decomposition of A is A = U ΣV > . Using the trace rotation trick,
tr(A) = tr(V > U Σ) (10)
Let R = V > U . Let Ui and Vi denote the i-th column of U and V respectively. Since Ui and Vi are unit
vectors by the property of SVD, we have |Rii | = | hUi , Vi i | ≤ 1. Therefore,
n
X
tr(A) = tr(RΣ) = Rii Σii (because Σ is a diagonal matrix)
i=1
n
X
≤ |Σii | (because |Rii | ≤ 1)
i=1
= kAk?
Remark: The equality is achieved when the left and right singular subspaces are aligned (Ui = Vi ) —
which is exactly the case in part (b).
SVD is generally a very powerful tool to deal with various linear algebraic quantities.
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Themanehoppe. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £7.67. You're not tied to anything after your purchase.
