## 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 $\mathbf{x}$ has a $k$-sparse representation in the columns of $\Phi$.

Today’s material was from Anna Gilbert’s Lecture 5+6 notes.

As I mentioned at the end of the lecture, the proof that Jitendra will present uses properties of the marix norm. Again, the wikipedia page on the matrix norm has the relevant results (we’ll use what is called “Induced Norm” on that page).