### Comments and Announcements about course on Spectral Methods - Fall 2010, Technion

 The course is taught by Prof Eli Ben Sasson and Dr. Ariel Gabizon at Taub 8 , Tuesdays 10:30-12:30.The course mostly follows the notes of Dan Spielman:http://www.cs.yale.edu/homes/spielman/561/

posted Jan 11, 2011, 4:47 AM by Ariel Gabizon

#### Last HW assignment

posted Jan 11, 2011, 4:46 AM by Ariel Gabizon

 For the third and last HW assignment in this course please submit by the end of the semester problem 1 in problem set 3 and problems 1-3 in problem set 4 on Dan's course website:http://www.cs.yale.edu/homes/spielman/561/

#### Lectures in December

posted Dec 22, 2010, 9:40 AM by Ariel Gabizon   [ updated Dec 22, 2010, 10:03 AM ]

 In previous recent meetings Eli Discussed efficient approximation for linear equations, followinglectures 15-16 of Spielman.The lecture this Tuesday Dec 21st was based on the following paperhttp://arxiv.org/abs/0808.0163We continue reviewing this paper next Tuesday.p.s.- will probably return ex. 1 next Tuesday

#### 5th lecture - Novemeber 16th

posted Nov 16, 2010, 10:07 AM by Ariel Gabizon   [ updated Nov 16, 2010, 10:09 AM ]

 Eli covered Lecture 5 in the notes.Here is the link to the talk of Dan Spielman Eli mentionedhttp://techtalks.tv/focs/2010/talks.php#TOP

#### Third Lecture - November 2nd

posted Nov 2, 2010, 8:47 AM by Ariel Gabizon

 I discussed the Perron-Frobenius Theorem. A simpler proof  in my opinion for positive matrices, without subtle analysis points, can befound here http://www.stanford.edu/class/ee363/lectures/pf.pdf starting from slide 19.Eli followed Lectures 12-13 from a different course by Spielman, this one: http://www.cs.yale.edu/homes/spielman/462/The first homework set, due in two weeks (Nov 16) is Problem set 1 from Dan's course, here's a link:http://www.cs.yale.edu/homes/spielman/561/ps1-09.pdf

 The material we covered is the second half of Lecture 2 and first half of Lecture 3 in Spielman's notes.-(note that below I use C(i,j) for the (i,j)'th entry in the matrix C, as opposed to class where I used subscripts)1. We proved Feidler's Theorem that for a Laplacian of a weighted path, an eigenvector of the k'th smallest eigenvalue changes sign *at most* times.I stated this as *exactly* k times, but as was noted in class this does not make sense when the eigenvalue has multiplicity>1. So what is correct is the at most' statement,and the exactly' statement is true only when the k'th smallest eigenvalue has multiplicity one.2. I had a problem with the proof of the above theorem at the following point: We had a symmetric matrix C such that for any vector x  x^T*C*x = \sum_i lambda_i *(x_i)^2.I  wanted to say that this implies the lambda_i's are eigenvalues of C. This is true since in the bilinear form x^T*C*x, for a symmetric C, the coefficient of x_i*x_j is 2*C(i,j) , so the equality above implies C is a diagonal matrix with C(i,i) =lambda_i in the diagonal. What I claimed about certain unit vectors being eigenvectors was not true.