Graphical models and Markov random fields

  • N. Santhanam and M. J. Wainwright. Information-theoretic limits of graphical model selection in high dimensions. To appear in International Symposium on Information Theory (ISIT), Toronto, Canada. July, 2008

  • P. Ravikumar, A. Agarwal and M. J. Wainwright. Message-passing for graph-structured linear programs: Proximal projections, convergence, and rounding schemes. To appear in International Conference on Machine Learning (ICML), Helsinki, Finland. July, 2008.

  • E. B. Sudderth, M. J. Wainwright, and A. S. Willsky Loop series and Bethe variational bounds in attractive graphical models. Proceedings of the NIPS conference, Vancouver, Canada. December 2007. Full Text (152K  pdf) .

  • P. Ravikumar, M. J. Wainwright and J. Lafferty. High-dimensional graphical model selection using $\ell_1$-regularized logistic regression. Department of Statistics, Technical Report 750, April 2008. Full Text (260K  pdf)
    Preliminary version:
  • M. J. Wainwright, P. Ravikumar and J. Lafferty. High-dimensional graphical model selection using $\ell_1$-regularized logistic regression. Advances in Neural Information Processing Systems, December 2006. Vancouver. Canada. Full Text (138K  pdf)

  • M. J. Wainwright. Estimating the ``wrong'' graphical model: Benefits in the computation-limited setting. Journal of Machine Learning Research, 7:1829--1859. September 2006. Full Text (343K  pdf) .
    Preliminary versions:
  • M. J. Wainwright. Estimating the ``wrong'' Markov random field: Benefits in the computation-limited setting. NIPS Conference, December 2005, Vancouver, Canada.
  • M. J. Wainwright and M. I. Jordan, Log-determinant relaxation for approximate inference in discrete Markov random fields. IEEE Transactions on Signal Processing, Vol. 54(6), pages 2099--2109. June 2006. Full Text (869K  ps) / Full Text (301K  pdf)
    Preliminary versions:
  • Appeared previously as UC Berkeley, Department of EECS, Technical Report UCB/CSD-3-1226, January 2003 (outdated).
  • M. J. Wainwright and M. I. Jordan Semidefinite relaxations for approximate inference on graphs with cycles. NIPS Conference, December 2003, Vancouver, Canada.

  • E. Maneva, E. Mossel and M. J. Wainwright. A New Look at Survey Propagation and its Generalizations. Journal of the ACM, Volume 54(4), July 2007. pp. 2--41. Full Text  (PDF)
    Preliminary version: A New Look at Survey Propagation and its Generalizations. Extended abstract: Symposium on Discrete Algorithms (SODA), January 2005, Vancouver, Canada.

  • V. N. Kolmogorov and M. J. Wainwright. On optimality of tree-reweighted max-product message-passing. Appeared in Uncertainty in Artificial Intelligence, July 2005, Edinburgh, Scotland.
    Full Text (293K  ps) / Full Text (293K  pdf) .

  • M. J. Wainwright, T. S. Jaakkola and A. S. Willsky, MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Transactions on Information Theory, Vol. 51(11), pages 3697--3717. November 2005. Full Text (719K  pdf)
    Preliminary versions:
  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. Exact MAP estimates by (hyper)tree agreement. NIPS conference; December, 2002; Vancouver, BC, Canada.
  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. MAP estimation via agreement on (hyper)trees: Message-passing and linear programming approaches. Allerton Conference on Communication, Control, and Computing; October 2--4, 2002; Urbana-Champaign, IL
  • Technical report (outdated):UC Berkeley CS Division technical report UCB/CSD-03-1269. August, 2003.

  • M. J. Wainwright and M. I. Jordan. Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations. UC Berkeley, Dept. of Statistics, Technical Report 671. September, 2004.
    Full Text (449K  pdf).

  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. A new class of upper bounds on the log partition function. IEEE Trans. on Information Theory, vol. 51, page 2313--2335, July 2005.
    Full Text (378K  pdf)
    Preliminary versions:
  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. A new class of upper bounds on the log partition function. Uncertainty in Artificial Intelligence; August 1--4, 2002; Edmonton, CA. Best Paper Award Abstract / Full Text (352K  ps) / Full Text (296K  pdf)

  • M. J. Wainwright, and M. I. Jordan. Variational inference in graphical models: The view from the marginal polytope. Invited paper; Allerton Conference on Communication, Control, and Computing; October 1--3, 2003; Urbana-Champaign, IL
    Full Text (290K  ps)

  • M. J. Wainwright, and M. I. Jordan. Graphical models, exponential families, and variational inference. UC Berkeley, Dept. of Statistics, Technical Report 649. September, 2003.
    Full Text (1.8M  PS) / Full Text (1.7M  PDF)

  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree-reweighted belief propagation and approximate ML estimation by pseudo-moment matching. Presented at the 9th Workshop on Artificial Intelligence and Statistics, Key West, Florida; January, 2003
    Abstract / Full Text (352K  ps) / Full Text (352K  pdf)

  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Statistics and Computing, April 2004, Vol. 14, 143--166.
    Journal version: Full Text (446K  pdf)

  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. IEEE Transactions on Information Theory, 45(9): pages 1120--1146. Originally appeared as LIDS Technical Report P-2510; Laboratory for Information and Decision Systems, MIT, May 2001.
    Local PDF file / Link to paper on IEEE Xplore
    Preliminary version:
  • M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree-based reparameterization for approximate estimation on graphs with cycles. Presented at the Conference on Neural Information Processing Systems (NIPS). Vancouver, Canada. Dec 3--8, 2001. Published in Advances in Neural Information Processing Systems 14; MIT Press, Cambridge MA, May 2002. Runner-up Best Student Paper Award

  • E. Sudderth, M. J. Wainwright and A. S. Willsky. Embedded trees: Estimation of Gaussian processes on graphs with cycles. IEEE Transactions on Signal Processing, November 2004, Vol. 52, pp. 3136 --3150.
    Journal version: Full Text (770K  pdf)
    Preliminary version:
  • M. J. Wainwright, E. Sudderth and A. S. Willsky. Tree-based modeling and estimation of Gaussian processes on graphs with cycles. Presented at the Conference on Neural Information Processing Systems (NIPS). Denver, CO. Nov. 28--30, 2000.

    • Back to top

    High-dimensional statistical inference

  • D. Omidiran and M. J. Wainwright. High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency. UC Berkeley Technical Report 753, May 2008. Full Text (181K  pdf). Short version to appear in International Symposium on Information Theory (ISIT), Toronto, Canada. July, 2008

  • W. Wang, M. J. Wainwright and K. Ramchandran. Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices. UC Berkeley Technical Report 754, May 2008. Full Text (181K  pdf). Short version to appear in International Symposium on Information Theory (ISIT), Toronto, Canada. July, 2008

  • N. Santhanam and M. J. Wainwright. Information-theoretic limits of graphical model selection in high dimensions. Short version to appear in International Symposium on Information Theory (ISIT), Toronto, Canada. July, 2008

  • Arash A. Amini and M. J. Wainwright, High-dimensional analysis of semidefinite programming relaxations for sparse principal component analysis. Technical report 747, Department of Statistics, UC Berkeley. March 2008. Full Text (181K  pdf). Short version tño appear in International Symposium on Information Theory (ISIT), Toronto, Canada. July, 2008

  • M. J. Wainwright, Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting. Technical report 725, Department of Statistics, UC Berkeley. January 2007. Full Text (181K  pdf) Presented in part at International Symposium on Information Theory (ISIT), Nice, France, July 2007.

  • P. Ravikumar, M. J. Wainwright and J. Lafferty. High-dimensional graphical model selection using $\ell_1$-regularized logistic regression. Department of Statistics, Technical Report 750, April 2008. Full Text (260K  pdf)
    Preliminary version:
  • M. J. Wainwright, P. Ravikumar and J. Lafferty. High-dimensional graphical model selection using $\ell_1$-regularized logistic regression. Advances in Neural Information Processing Systems, December 2006. Vancouver. Canada. Full Text (138K  pdf)

  • M. J. Wainwright, Sharp thresholds for noisy and high-dimensional recovery of sparsity using $\ell_1$-constrained quadratic programming. Technical report 709, Department of Statistics, UC Berkeley. May 2006. Full Text (660K  pdf). Short version presented at Allerton Conference on Communication, Control and Computing, September 2006.

    Distributed statistical inference and signal processing

  • R. Rajagopal and M. J. Wainwright. Network-based consensus averaging with general noisy channels. Department of Statistics, Technical Report 751, May 2008. Presented in part at Allerton Conference on Control, Communication, and Computing (Sep. 2007). Full Text  (1.6M  pdf)

  • A. G. Dimakis, A. Sarwate and M. J. Wainwright. Geographic Gossip: Efficient Averaging for Sensor Networks. IEEE Transactions on Signal Processing, 53: 1205--1216. March 2008. Full Text (1.2M  pdf)
    Conference version:
  • Geographic Gossip: Efficient Averaging for Sensor Networks. Fifth International Conference on Information Processing in Sensor Networks (IPSN), Nashville, TN. April 2006.

  • M. Cetin, L. Chen, J. Fisher, A. Ihler, R. Moses, M. J. Wainwright and A. S. Willsky. Distributed fusion in sensor networks. IEEE Signal Processing Magazine, July 2006. Full Text (1M  pdf)

  • X. Nguyen, M. J. Wainwright and M. I. Jordan, On optimal quantization rules for some problems in sequential decentralized detection. IEEE Transactions on Information Theory, Vol. 54(7), pp. 3285--3295. July 2008. Full Text (PDF)
    Preliminary versions:
  • Presented in part at International Symposium on Information Theory, Seattle, WA. July 2006.
  • Longer version appeared originally as Technical Report 708, Department of Statistics, UC Berkeley. August 2006.

  • R. Rajagopal, M. J. Wainwright and P. Varaiya, Universal Quantile Estimation with Feedback in the Communication-Constrained Setting, International Symposium on Information Theory, Seattle, WA. July 2006. Full Text (148K  pdf)

  • X. Nguyen, M. J. Wainwright and M. I. Jordan. On divergences, surrogate loss functions, and decentralized detection. UC Berkeley Department of Statistics, Technical Report 695, October 2005. Full Text (348K  pdf) To appear in the Annals of Statistics (2008).
    Conference version:
  • X. Nguyen, M. J. Wainwright and M. I. Jordan. On information divergence measures, surrogate loss functions and decentralized hypothesis testing. 43rd Annual Allerton Conference on Communication, Control and Computing, IL, September 2005. Full Text (133K  pdf)

  • X. Nguyen, M. J. Wainwright and M. I Jordan. Nonparametric decentralized detection using kernel methods. IEEE Transactions on Signal Processing, Vol. 53(11), pages 4053--4066. November 2005. Full Text (754K  pdf)
    IEEE Signal Processing Outstanding Young Author Award (XuanLong Nguyen)

    Preliminary versions:
  • X. Nguyen, M. J. Wainwright and M. I Jordan. Decentralized detection and classification using kernel methods. Proceedings of the International Conference on Machine Learning, July 2004. Outstanding Student Paper Award (XuanLong Nguyen) Full Text (204K  ps) / Full Text (204K  pdf)

  • Technical report (superseded by journal paper): Decentralized detection and classification using kernel methods. UC Berkeley, Dept. of Statistics, Technical Report 658. April, 2004.

  • L. Chen, M. Wainwright, M. Cetin and A. Willsky, Multitarget-multisensor data association using the tree-reweighted max-product algorithm. Presented at the SPIE Aerosense conference, Orlando, FL, March 2003.
    Full Text (204K  pdf) \ Full Text (204K  pdf)

    Back to top

    Channel coding, data compression, algorithms

  • P. Lee, L. Dolecek, Z. Zhang, V. Anantharam, B. Nikolic and M. J . Wainwright, Error Floors in LDPC Codes: Fast Simulation, Bounds and Hardware Emulation . IEEE International Symposium on Information Theory (ISIT 2008), Toronto, Canada, July 2008. Full Text  (PDF)

  • A. D. G. Dimakis, M. J. Wainwright, M.J., and K. Ramchandran, Lower bounds on the rate-distortion function of LDGM codes. Information Theory Workshop (ITW), September 2007, pp. 650 - 655. Full Text  (PDF)

  • M. J. Wainwright, Sparse graph codes for side information and binning, IEEE Signal Processing Magazine: 24(5): 47--57, September 2007. Full Text  (PDF)

  • L. Dolecek, Z. Zhang, M. J. Wainwright, V. Anantharam, and B. Nikolic, Evaluation of the low frame error rate performance of LDPC codes using importance sampling, IEEE Information Theory Workshop, Lake Tahoe CA, September 2007, pp. 202 - 207. Full Text  (PDF)

  • L. Dolecek, Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolic, Analysis of Absorbing Sets for Array-Based LDPC Codes, IEEE International Conference on Communications (ICC), Glasgow, United Kingdom, June 2007, pp. 6261-6268.

  • Z. Zhang, L. Dolecek, V. Anantharam, M. J. Wainwright, and B. Nikolic, Quantization Effects in Low-Density Parity-Check Decoders, IEEE International Conference on Communications (ICC), Glasgow, United Kingdom, June 2007, pp. 6231-6237. Full Text  (PDF)

  • A. Dimakis, B. Godfrey, M. J. Wainwright and K. Ramchandran, Network Coding for Distributed Storage Systems INFOCOM 2007, Anchorage, Alaska. May 2007. Full Text  (PDF)

  • E. Martinian and M. J. Wainwright, Low-density graph codes that are optimal for source/channel coding and binning. Department of Statistics, Technical Report 730, April 2007. Available at arxiv:cs.it: arxiv paper

  • C. Daskalakis, A. G. Dimakis, R. Karp and M. J. Wainwright, M. J. Wainwright, Probabilistic analysis of linear programming decoding. SIAM Symposium on Discrete Algorithms, New Orleans, LA. January 2007. To appear in IEEE Trans. Info. Theory.
    Technical report version: Full Text  (1.2M  pdf)

  • Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam, and M. J. Wainwright, Investigation of error floors of structured low-density parity-check codes by hardware emulation. Proceedings of IEEE Globecom, San Francisco, CA, November 2006. Full Text  (1.2M  pdf)

  • E. Martinian and M. J. Wainwright, Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds. International Symposium on Information Theory, Seattle, WA. July 2006. Full Text  (151K  pdf)

  • A. D. G. Dimakis and M. J. Wainwright, Guessing Facets: Polytope Structure and Improved LP Decoding. International Symposium on Information Theory, Seattle, WA. July 2006. Full Text (191K  pdf)

  • E. Martinian and M. J. Wainwright, Low-density codes achieve the rate-distortion bound. Data Compression Conference, Snowbird, UT. March 2006. Full Text (191K  pdf)

  • E. Martinian and M. J. Wainwright, Analysis of LDGM and compound codes for lossy compression and binning. Workshop on Information Theory and its Applications, San Diego, CA. February 2006. Full Text (185K  pdf)

  • M. J. Wainwright and E. Maneva, Lossy source coding via message-passing and decimation over generalized codewords of LDGM codes. Presented at the International Symposium on Information Theory, Adelaide, Australia. September, 2005.
    Full Text (1.7M  ps) / Full Text (304K  pdf)

  • J. Feldman, T. Malkin, R. Servedio, C. Stein and M. J. Wainwright, LP Decoding Corrects a Constant Fraction of Errors. IEEE Trans. Information Theory, (53):82--89. January, 2007. Full Text (280K  pdf)

    Preliminary versions:
  • LP Decoding Corrects a Constant Fraction of Errors. CORC Technical Report TR-2003-08, Industrial Engineering and Operations Research, Columbia University. December 2003.
  • Presented at International Symposium on Information Theory, Chicago, IL. July, 2004.

  • J. Feldman, M. J. Wainwright and D. R. Karger. (2005) Using linear programming to decode binary linear codes. IEEE Transactions on Information Theory, (51):954-972. Full Text (531K  pdf) / Link to paper on IEEExplore

    Preliminary versions:
  • J. Feldman, D. Karger and M. J. Wainwright, LP Decoding Invited Paper; Allerton Conference on Communication, Control, and Computing; October 1--3, 2003; Urbana-Champaign, IL.
    Full Text (424K  ps) / Full Text (173K  pdf)

  • J. Feldman, D. Karger and M. Wainwright, Using linear programming to decode LDPC codes. Conference on Information Sciences and Systems, Baltimore, March 2003.
    Full Text (424K  ps) / Full Text (173K  pdf)

  • J. Feldman, D. Karger and M. Wainwright, Linear programming-based decoding of turbo-like codes and its relation to iterative approaches. Presented at the Allerton Conference on Communication, Control, and Computing; October 2--4, 2002; Urbana-Champaign, IL
    . Full Text (352K  ps) / Full Text (352K  pdf)

    Back to list

    Natural image models and statistical image processing

  • J. Portilla, V. Strela, M. J. Wainwright and E.P. Simoncelli. Image denoising using Gaussian scale mixtures in the wavelet domain. IEEE Transactions on Image Processing, November 2003. Vol. 12, pp. 1338-1351. Abstract / Local PDF file / Link to IEEExplore

    Preliminary version:

  • J. Portilla, V. Strela, M. J. Wainwright and E.P. Simoncelli. Adaptive Wiener denoising using a Gaussian scale mixture model in the wavelet domain. Proceedings of the 8th International Conference on Image Processing. October, 2001; Greece.

  • M. J. Wainwright, E. P. Simoncelli and A. S. Willsky. Random cascades on wavelet trees and their use in analyzing and modeling natural images. Applied Computational and Harmonic Analysis (2001), vol. 11, pages 89--123. / Full Text (1M  ps) / Full Text (822K  pdf)

    Preliminary versions:

  • M. J. Wainwright, E. P. Simoncelli and A. S. Willsky. Random cascades on wavelet trees and their use in analyzing and modeling natural images. Invited Paper; Published in Proceedings of the 45th Annual Meeting of the SPIE. San Diego, CA; July 30 -- August 4, 2000.

  • M. J. Wainwright, E. P. Simoncelli and A. S. Willsky. Random cascades of Gaussian scale mixtures and their use in modeling natural images with application to denoising. Proceedings of the 7th International Conference on Image Processing. Vancouver, BC, Canada. 10-13 September 2000.

  • M. J. Wainwright and E. P. Simoncelli. Scale Mixtures of Gaussians and the Statistics of Natural Images. Conference on Neural Information Processing Systems (NIPS). Denver, CO. Nov 29-Dec 2, 1999; pages 855--861. Full Text (1.8M, pdf)

    Back to top

    Statistical theories of biological vision

  • M. J. Wainwright, O. Schwartz, and E. P. Simoncelli, "Natural image statistics and divisive normalization: Modeling nonlinearities and adaptation in cortical neurons", Chapter 10, pages 203--222; Statistical Theories of the Brain, Eds. P. Rao, B. Olshausen and M. Lewicki, MIT Press 2002. Full Text (137K, pdf)

  • M. J. Wainwright, "Visual adaptation as optimal information transmission", Vision Research , 39:3960--3974, 1999. Full Text (245K, pdf)

    Back to top

    Ph.D. thesis

  • M. J. Wainwright, "Stochastic Processes on Graphs: Geometric and Variational Approaches", Ph.D. Thesis, Department of EECS, Massachusetts Institute of Technology, 2002. Full Text (3.9M, pdf)