## Problem

Previewing page
*1*
of
actual document.

**View the full content.**View Full Document

0 0 17 views

**Unformatted text preview:**

15 496 859X Computer Science Theory for the Information Age Carnegie Mellon University Spring 2012 V Guruswami R Kannan Problem Set 2 Due by 6 pm Friday February 17 Instructions You should think about each problem by yourself for at least 30 minutes before choosing to collaborate with others You are allowed to collaborate with fellow students taking the class in solving the problems in groups of at most 3 people for each problem In fact this is encouraged so that you interact with and learn from each other However you must write up your solutions on your own If you collaborate in solving problems you should clearly acknowledge your collaborators for each problem Reference to any external material besides the course text and material covered in lecture is not allowed In particular you are not allowed to search for answers or hints on the web You are encouraged to contact the instructors or the TA for a possible hint if you feel stuck on a problem and require some assistance Solutions typeset in LATEX are preferred Feel free to email the instructors or the TA if you have any questions or would like any clarifications about the problems You are urged to start work on the problem set early 1 10 points Let A be an n d matrix for n d with orthogonal columns w1 w2 wd of positive lengths 1 2 d no two of which are equal What is the Singular Value Decomposition of A Justify your answer 2 10 points Let A be a square n n matrix whose rows are orthonormal Prove that the columns of A must also be orthonormal Is this necessarily true for m n matrices when m n 3 15 points Suppose you are given an overdetermined system of linear equations Ax b where A is an m n matrix with m n and b Rm which we would like to solve for x Rn That is we have more equations m than variables n so there may be no solution to the system Thus a natural goal is to find a solution x that minimizes the error kAx bk2 a First let us assume that A has rank n Show that the x that minimizes kAx bk2 is unique and given by AT A 1 AT b b P Now consider the general case when the rank r of A may be less than n Let A r T i 1 i ui vi be a SVD of A with nonzero singular values 1 2 r Prove that x r X hb ui i i 1 satisfies kAx bk2 minx Rn kAx bk2 i vi 4 20 points In this problem we will explore a different way to decompose matrices focusing on square matrices for concreteness Along the way we will encounter the very important notion of positive semidefiniteness a A real symmetric matrix M Rn n is said to be positive semidefinite psd if all its eigenvalues 1 2 n are non negative What are the singular values of such a positive semidefinite matrix M b Prove that a real symmetric matrix M Rn n is positive semidefinite if and only if xT M x 0 for all x Rn c Prove that if a real symmetric matrix M is positive semidefinite then so is V M V T for any n n matrix V d Prove that every n n matrix A can be decomposed as A W P for n n matrices W P satisfying the conditions i W T W W W T I and ii P is real symmetric and positive semidefinite 5 15 points Let G V E be a d regular simple undirected graph1 with V 1 2 n Define the n n matrix L as follows if i j d 1 i j E Lij 0 otherwise a By definition L is a real symmetric matrix Prove that L is positive semidefinite Hint Expand the quadratic form xT Lx for x Rn b What is the smallest eigenvalue of L Is L invertible c Prove that kLk2 2d When is equality attained 1 This means there are no loops or multiple edges and each vertex is adjacent to exactly d other vertices