6.454 - Graduate Seminar in Area I

6.454 - Graduate Seminar in Area I - Fall 2007

Course Information

Guidelines

Topics

Schedule

Sparsity and Compressed Sensing

Main papers:
- E. Candès, J. Romberg, and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information", IEEE Trans. on Information Theory, Vol. 52, No. 2, pp. 489-509, February 2006.
- D. Donoho, "Compressed sensing", IEEE Trans. on Information Theory, Vol. 52, No. 4, pp. 1289-1306, April 2006.
- E. Candès and T. Tao, "Near optimal signal recovery from random projections: Universal encoding strategies?", IEEE Trans. on Information Theory, Vol. 52, No. 12, pp. 5406-5425, December 2006.
- E. Candès, "Compressive sampling", Proc. International Congress of Mathematics, 3, pp. 1433-1452, Madrid, Spain, 2006.
- R. Baraniuk, "A Lecture on Compressive Sensing", IEEE Signal Processing Magazine, Vol. 24, No. 4, pp. 118-121, July 2007.
Related work:
- J. Wright, A. Ganesh, A. Yang, and Y. Ma, "Robust Face Recognition via Sparse Representation", UIUC Technical Report UILU-ENG-07-2205 DC-228, 2007.
- B. Recht, M. Fazel and P. A. Parrilo, "Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization", arXiv Preprint, arxiv.org/abs/0706.4138, 2007.
- D. L. Donoho and X. Huo, X., "Uncertainty principles and ideal atomic decomposition", IEEE Trans. on Information Theory, Vol. 47, No. 7, pp. 2845-2862, November 2001.
- D. M. Malioutov, M. Çetin, A. S. Willsky, "Homotopy continuation for sparse signal representation", IEEE ICASSP 2005, Vol. 5, pp. 733-736, Philadelphia, PA, March 2005.
- E. Candès and T. Tao, "Decoding by linear programming", IEEE Trans. on Information Theory, Vol. 51, No.12, pp. 4203-4215, December 2005.
Additional resources:
- Rice University.

Minimum Description Length

Main papers:
- A. Barron, J. Rissanen, and B. Yu, "The minimum description length principle in coding and modeling", IEEE Trans. on Information Theory, Vol. 44, No. 6, pp. 2743-2760, October 1998.
- P. Grünwald, "A tutorial introduction to the minimum description length principle", in Advances in Minimum Description Length: Theory and Applications, edited by P. Grünwald, I.J. Myung, M. Pitt, MIT Press, 2005.
Additional resources:
- mdl-research.org
- P. Grünwald, The Minimum Description Length Principle, MIT Press, 2007.

Distributed Computation and Communication Complexity

Main papers:
- A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209-213, 1979.
- A. Orlitsky and A. El Gamal, "Average and Randomized Communication Complexity", IEEE Trans. on Information Theory, Vol. 36, No. 1, pp. 3-16, January 1990.
- Z.-Q. Luo and J.N. Tsitsiklis, "On the Communication Complexity of Solving a Polynomial Equation", SIAM J. on Computing, Vol. 20, No. 5, pp. 936-950, October 1991.
Related work:
- N. Goyal, G. Kindler, and M. Saks, "Lower bounds for the noisy broadcast problem", Proc. of the 46th IEEE FOCS, pp. 40-49, 2005. Extended version, 2006.
Additional resources:
- A. Orlitsky and A. El Gamal, "Communication Complexity", in Complexity in Information Theory, edited by Y. S. Abu-Mostafa, Springer-Verlag, New York, 1988.
- E. Kushilevitz and N. Nisan, Communication complexity, Cambridge University Press, 1997.

Broadcast Channels

Main papers:
- T. Cover, "Broadcast channels", IEEE Trans. on Information Theory, Vol. 18, No.1, pp. 2-14, January 1972.
- P. Bergmans, "A simple converse for broadcast channels with additive white gaussian noise", IEEE Trans. on Information Theory, Vol. 20, No. 2, pp. 279-280, March 1974.
- G. Caire and S. Shamai, "On the achievable throughput of a multi-antenna gaussian broadcast channel", IEEE Trans. on Information Theory, Vol. 49, No. 7, pp. 1691-1706, July 2003.
- H. Weingarten, Y. Steinberg, S. Shamai, "The capacity region of the gaussian multiple-input multiple-output broadcast channel", IEEE Trans. on Information Theory, Vol. 52, No. 9, pp. 3936-3964, September 2006.