Abstract – Graphical models and their associated greedy/message-passing algorithms make excellent error correcting codes as well as efficient compressive sensing systems and they are the natural setting for general random constraint satisfaction problems. Empirically, such systems, if properly chosen, work very well. Analytically, they are not always easy to handle.
When we are interested in the behaviour of a function of a real variable it is sometimes useful to think of this function as defined on the whole complex plane. Even though the setting is now more general and seemingly more difficult, the analysis can simplify. E.g., think of a polynomial and its roots.
For graphical models we can do something similar. Instead of thinking of one graphical model, we can imagine many of them coupled together spatially along a line. It turns out that for some problems not only is it easier to analyse a coupled system but understanding this coupled system also allows us to draw conclusion about the underlying uncoupled one.
I will discuss this phenomenon in the framework of random constraint satisfaction problems.
No prior familiarity with graphical models, spatial coupling or constraint satisfaction will be assumed.
This talk is based on joint work with Dimitris Achlioptas, Hamed Hassani, and Nicolas Macris.
Abstract– A discussion of science and engineering practices in the field of signal and image processing as it relates to algorithm development and evaluation.
Abstract – We consider the problem of recovering an image from “corrupted” outputs of a linear measurement operator, where corruption may occur through additive noise or some component-wise non-linear operation like quantization or phase removal. We describe recent results on “approximate message passing” (AMP) solutions to this problem, which are motivated by the case that the measurement operator is a large random matrix. In particular, we discuss connections between AMP and contemporary convex optimization algorithms, convergence properties of AMP and methods to robustify AMP to non-random matrices, and recent methods to automatically tune the parameters underlying the assumed statistical model. Numerical results for cosparse-analysis compressive imaging and compressive phase retrieval are provided to illustrate the advantages of the AMP methods.
Biography – Philip Schniter received the B.S. and M.S. degrees in Electrical Engineering from the University of Illinois at Urbana-Champaign in 1992 and 1993, respectively, and the Ph.D. degree in Electrical Engineering from Cornell University in Ithaca, NY, in 2000. From 1993 to 1996 he was employed by Tektronix Inc. in Beaverton, OR as a systems engineer. After receiving the Ph.D. degree, he joined the Department of Electrical and Computer Engineering at The Ohio State University, Columbus, where he is currently a Professor. In 2008-2009 he was a visiting professor at Eurecom, Sophia Antipolis, France, and Supelec, Gif-sur-Yvette, France. In 2003, Dr. Schniter received the National Science Foundation CAREER Award, and in 2014 he was elevated to Fellow of the IEEE.
Abstract – In a wide spectrum of problems in science and engineering that includes hyperspectral imaging, gene expression analysis, and metabolic networks, the observed data is high-dimensional and can be modeled as arising from an unknown mixture of a small set of unknown shared latent factors. Our approach is based on a natural separability property of the shared latent factors. Our separability property posits that every latent factor contains at least one component that is dominant in that factor. We first establish that this property is not only natural but an inevitable consequence of high-dimensionality, and satisfied by the estimates produced by popular nonparametric Bayes approaches. We show that geometrically these dominant latent factors can be associated with extreme points in a suitable space. We leverage this geometric insight to develop a suite of efficient algorithms for a diverse set of latent variable problems. The proposed random-projections-based algorithm is naturally amenable to a low communication-cost distributed implementation that is attractive for modern web-scale distributed data mining applications. We then establish statistical and computational efficiency guarantees for learning in high-dimensional latent variable models.
This is joint work with Weicong Ding & Prakash Ishwar.
Biography – Venkatesh Saligrama is a faculty member in the Electrical and Computer Engineering Department at Boston University. He holds a PhD from MIT. His research interests are in Statistical Signal Processing, Statistical Learning, Video Analysis, Information and Decision theory. He has edited a book on Networked Sensing, Information and Control. He has served as an Associate Editor for IEEE Transactions on Information Theory, IEEE Transactions on Signal Processing and Technical Program Committees of several IEEE conferences. He is the recipient of numerous awards including the Presidential Early Career Award (PECASE),
Abstract – The invention of turbo codes and the rediscovery of low-density parity-check (LDPC) codes, allowed to approach capacity with practical codes. Nowadays, both turbo and LDPC codes are ubiquitous in communication standards. In the academic arena, however, the interest on turbo-like codes has been declining in the last years in favor of the more mathematically-appealing LDPC codes. This trend has been exacerbated with the recent introduction of spatial coupling of LDPC codes, which has revealed as a powerful technique to construct codes that universally achieve capacity for the class of binary input memoryless channels under belief propagation (BP) decoding. The main principle behind this outstanding behavior is the convergence of the BP threshold to the maximum a posteriori threshold of the underlying block code ensemble.
The concept of spatial coupling, however, is not exclusive of LDPC codes. In this talk, we discuss spatially coupled turbo codes (SC-TCs), the spatial coupling of classical turbo codes, i.e., Berrou et al. and Benedetto et al. parallel and serially concatenated codes. We consider the construction of a family of rate-compatible SC-TCs with simple 4-state component encoders that perform very close to the Shannon limit for a wide range of code rates.