most recent 30 from http://mathoverflow.net 2013-05-22T01:32:50Z http://mathoverflow.net/feeds/question/32588 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy man basnet 2010-07-20T03:47:39Z 2012-11-08T14:58:48Z

<p>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.</p>

http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/32591#32591 Yuval Filmus 2010-07-20T04:22:33Z 2010-07-20T04:22:33Z

<p>You can try <i>An Introduction to Kolmogorov Complexity and Its Applications</i> by Ming Li and Paul Vit&aacute;nyi, it's an excellent book.</p>

http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/32604#32604 Bob Durrant 2010-07-20T07:56:36Z 2010-07-20T07:56:36Z

<p>Not quite what you asked for, but possibly useful if you haven't yet read it, is Baraniuk et al, <a href="http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/JL_RIP.pdf" rel="nofollow">A Simple Proof of the Restricted Isometry Property for Random Matrices</a>. This was one of the most readable introductions that I found when I was learning about CS.</p> <p>For the basics of Kolmogorov Complexity you could do worse than Cover and Thomas, Elements of Information Theory.</p>

http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/32618#32618 Joseph O'Rourke 2010-07-20T11:32:06Z 2010-07-20T12:05:25Z

<p>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 href="http://arxiv.org/abs/1005.2400" rel="nofollow">A Short Introduction to Kolmogorov Complexity</a>" by Volker Nannen, true to its title, is only 7 pages long. The <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">Wikipedia page on Kolmogorov Complexity</a> is quite good. Gregory Chaitin's <em><a href="http://books.google.com/books?id=SypgS22V-TgC&amp;printsec=frontcover&amp;dq=Exploring+Randomness&amp;source=bl&amp;ots=JQwAIn-qga&amp;sig=kpmpXyagWkLI5-24mkXzhwvMA0g&amp;hl=en&amp;ei=34ZFTPv-N4H68Abou7zmBA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=2&amp;ved=0CCAQ6AEwAQ#v=onepage&amp;q&amp;f=false" rel="nofollow">Exploring Randomness</a></em> 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 <a href="http://www.ams.org/notices/200109/rev-panu.pdf" rel="nofollow">Notices of the AMS review</a> of his book by Panu Raatikainen might serve as a useful introduction to the area.</p>

http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/32764#32764 robin girard 2010-07-21T08:55:59Z 2010-07-21T08:55:59Z

<p>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)</p>

http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/111818#111818 dima 2012-11-08T14:58:48Z 2012-11-08T14:58:48Z

<p>I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.</p>