Question

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.

Answer 1

I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.

Answer 2

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)

Answer 3

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.

Answer 4

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.

Answer 5

You can try An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi, it's an excellent book.