Most of the authors of research papers in compressed sensing use nwidths 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.

$\begingroup$ Nvm the edit  it's null. $\endgroup$– DoubleJayJul 20, 2010 at 4:38
5 Answers
You can try An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi, it's an excellent book.
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.
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.
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: nWidths in Approximation Theory, SpringerVerlag, Berlin (1985)
I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.