Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
Nvm the edit - it's null. –  DoubleJay Jul 20 '10 at 4:38

5 Answers 5

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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)

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.