The heavy hitters problem elicits a list of the m largest-magnitude components in a signal of length d. Although this problem is easy when the signal is presented explicitly, it becomes much more challenging in the setting of streaming data, where the signal is presented implicitly as a sequence of additive updates. One approach maintains a small sketch of the data that can be used to approximate the heavy hitters quickly. In previous work, this sketch is essentially a random linear projection of the data that fails with small probability for each signal. It is often desirable that the sketch succeed simultaneously for ALL signals from a given class, a requirement that may be called uniform heavy hitters. It arises, for example, when the signal is queried a large number of times or when the signal updates are stochastically dependent.

This talk describes a random linear sketch for uniform heavy hitters that succeeds with high probability. The recovery algorithm produces a list of heavy hitters that approximates the input signal with an l2 error that is optimal, except for an additive term that depends on the optimal l1 error and a controllable parameter e. The recovery algorithm requires space m*poly(log(d)/e) and time m2*poly(log(d)/e) to produce the list of heavy hitters. Up to logarithmic factors, the performance of this algorithm is the best possible with respect to several resources.

Joint work with Martin Strauss, Joel Tropp, and Roman Vershynin.

Two optimization problems arising from polling and nonhomogeneous poisson processes

Many important optimization problems in science and engineering involve functions that can fairly be described as "nasty", which can mean any or all of wildly nonlinear, nonsmooth, noisy, and defined through complex black-box simulation or error-prone experimental data. Because it is often impossible or impractical to calculate derivatives of these functions, non-derivative methods are the only feasible choice. These methods are in the midst of a renaissance involving research on their theoretical and computational properties, as well as investigation of which methods are best suited for which applications. This talk will include examples of challenging problems along with the speaker's assessment of the state of the art in non-derivative optimization methods.

A fictitious play approach to complex systems optimization

Standard information-theoretic results show that data over small, typically binary, alphabets can be compressed to Shannon's entropy limit. Yet most practical sources, such as text, audio, or video, have essentially infinite support. Compressing such sources requires estimating probabilities of unlikely, even unseen, events, a problem considered by Laplace. Of existing estimators, an ingenious if cryptic one derived by Good and Turing while deciphering the Enigma code works best yet not optimally. Hardy and Ramanujan's celebrated results on the number of integer partitions yield an asymptotically optimal estimator that compresses arbitrary-alphabet data patterns to their entropy. The same approach generalizes Fisher's seminal work estimating the number of butterfly species and its extension authenticating a poem purportedly written by The Bard. The talk covers these topics and is self contained.

Joint work with Prasad Santhanam, Krishna Viswanathan, and Junan Zhang

Natural color images captured by digital cameras often exhibit noticeable noise, particularly when the pictures are taken under low lighting or artificial lighting conditions. Traditional denoising techniques, which are often tested for removing artificial noise in monochromatic images, often do not work well for noisy color images.

In this talk, we present an overview of some of the traditional methods for denoising. We discuss a new strategy, which we call the cross-channel principle, that can be applied for very effective denoising of color images. In particular we show how this principle can be applied to the total variation denoising scheme and an ENO type denoising scheme.