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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Nvm the edit - it's null. $\endgroup$– DoubleJayCommented Jul 20, 2010 at 4:38
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
You can try An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi, it's an excellent book.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Jul 20, 2010 at 11:32
$\begingroup$
$\endgroup$
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)
answered Jul 21, 2010 at 8:55
$\begingroup$
$\endgroup$
I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.
