n-widths and  Kolmogorov's entropy  Most of the authors of research papers in compressed sensing use  n-widths and Kolmogorov's entropy extensively, which are kind of hard for me to understand. Any suggestion on books  or expository articles about these will be highly appreciated.
 A: You can try An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi, it's an excellent book.
A: Not quite what you asked for, but possibly useful if you haven't yet read it, is Baraniuk et al, A Simple Proof of the Restricted Isometry Property for Random Matrices. This was one of the most readable introductions that I found when I was learning about CS.
For the basics of Kolmogorov Complexity you could do worse than Cover and Thomas, Elements of Information Theory.
A: Nothing can surpass the Li and Vitányi book in both readability and comprehensiveness,
but that is a significant undertaking, and you might need alternatives.
"A Short Introduction to Kolmogorov Complexity" by Volker Nannen, true to its title, is only 7 pages long. The Wikipedia page on Kolmogorov Complexity is quite good.
Gregory Chaitin's Exploring Randomness is a fun, quirky, personalized view of the field, emphasizing his own work and LISP programs. Caveat: his philosophical musings are quite controversial.
In fact, reading the balanced Notices of the AMS review of his book by Panu Raatikainen might serve as a useful introduction to the area.
A: The book that is my reference (and also the reference I found in a lot of excellent papers on the subjects) is the book by Pinkus:
n-Widths in Approximation Theory, Springer-Verlag, Berlin (1985)
A: I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.
