Hsu | Notes

Here are some notes I've written. Some have not been subjected to any scrutiny whatsoever, so I welcome suggestions, corrections, and other comments.

Original notes

Note on Exact Reconstruction Principle and Linear Programming Duality: The paper "Decoding by linear programming" by Candes and Tao (2005) shows, among other things, that ERP and RIP are sufficient for sparse signal reconstruction by linear programming. This note gives a somewhat different proof of this fact.
General PECOC analysis: A generalization of probabilistic error correcting codes (Langford and Beygelzimer, 2005) for reductions to regression problems. Also see John's blog post for a more complete discussion on the subject. Dwork and Yekhanin (2008) use essentially the same method to attack statistical disclosure control mechanisms.
A note on the label complexity of the Cohn-Atlas-Ladner selective sampler: An analysis of the label complexity of the active learning strategy due to Cohn, Atlas, and Ladner (1994) in terms of Hanneke's disagreement coefficient (2007). This predates the analysis in my NIPS 2007 paper with Sanjoy and Claire, and the proof is somewhat different.

Approximating finite metrics by distributions over tree metrics: On the paper "A tight bound on approximating arbitrary metrics by tree metrics" by Fakcharoenphol, Rao, and Talwar (2003). Extra: On approximating the cycle.
Note on the Frank-Wolfe algorithm: On the paper "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm" by Clarkson (2008), which is a truly excellent paper.

The spectrum of the Laplacian: Facts about the (normalized) Laplacian of a graph. For Math 261A, Fall 2005. The lecture is by Fan Chung Graham. This note is part of a collection maintained by Paul Horn.
Pigeons, primes, and probabilistic algorithms: The "plentiful pigeons" technique as applied to verifying straight-line arithmetic programs. For CSE 203A, Spring 2006. The lecture is by Russell Impagliazzo.
PAC learning: Some elementary reductions in PAC learning. For CSE 291, Fall 2006. The lecture is by Sanjoy Dasgupta.
Uniform convergence: Handwritten (scanned) notes from an introductory learning theory course. For CSE 291, Fall 2006. The lecture is by Sanjoy Dasgupta.