Lecture Notes

Recent Posts
Archives
Categories
Monthly Archives: February 2012
Lect 10: Analysis of OMP
In today’s lecture, we setup things for Jitendra’s presentation next Wednesday, where he will prove that the OMP algorithm computes the optimal solution, when has a sparse representation in the columns of . Today’s material was from Anna Gilbert’s Lecture … Continue reading
Posted in Spring 2012
Leave a comment
Lect 9: OMP Algorithm
On Wednesday, we saw the Orthogonal Matching Pursuit (OMP) algorithm. We also looked at the least squares problem. The Wikipedia page on the least squares problem has the derivation I did in class (and more). Rest of the material was … Continue reading
Posted in Spring 2012
Leave a comment
Lect 8: Coherence
In the lecture on Friday, Feb 10, we saw the notion of approximation algorithms and the notion of coherence of a redundant dictionary. The material were from Lectures 4 and 5 from Anna Gilbert’s notes.
Posted in Spring 2012
Leave a comment
Next Week and (Optional) HW
A gentle reminder that we will not have class next week (i.e. Feb 15, 17). As “makeup” I encourage you to try and work out problems in HW 1 from Anna Gilbert’s course. Please do not submit the HW– this … Continue reading
Posted in Spring 2012
Leave a comment
Lect 7: NPHardness of the EXACT Problem
On Wednesday, we finished the reduction from X3C to the decision version of EXACT. The material was from Lecture 4 from Anna Gilbert’s notes.
Posted in Spring 2012
Leave a comment
Lect 6: Hardness of Sparse Approximation problems
In today’s lecture, we saw an algorithm to solve the ERROR problem for the case of orthogonal matrices. Then we saw an overview of NPCompleteness. The stuff on ERROR is from Lecture 3 from Anna Gilbert’s notes. For a more … Continue reading
Posted in Spring 2012
Leave a comment
Lect 5: Sparse Approximation for Orthogonal matrices
We saw how to solve the EXACT and SPARSE problem for the case when is orthogonal. The material is from Lecture 3 from Anna Gilbert’s notes.
Posted in Spring 2012
Leave a comment