^February March – 2013 ^April

We offer a new perspective on the nearest neighbor classifier, which yields tighter risk asymptotics than the classic Cover-Hart analysis. As a by-product, our analysis suggests a natural solution to the problem of noisy labels/outliers. Our result holds in doubling metric spaces, of which Euclidean spaces are a special case. The classifier may be learned in linear time and evaluated on new points in logarithmic time via approximate nearest neighbors. Time permitting, we'll discuss recent results on metric dimensionality reduction as well. Joint work with Lee-Ad Gottlieb and Robert Krauthgamer

The bulk of previous research on global image statistics has focused either on first order statistics such as luminance and contrast distributions, or on second order statistics such as the autocorrelation, or equivalently the power spectrum. While numerous links between global statistics of natural images and the functional architecture of biological visual systems have been established, it is widely agreed that perceptually important details such as edges and object boundaries are not captured by such low order statistics but rather by higher order ones. In this talk, I'll address the global first and second order statistics, but unlike previous studies, we consider them jointly. For this purpose we have developed an algorithm that produces random images with prescribed first and second order statistics. That is, given a natural image, the algorithm generates a new image with a similar distribution and spatial correlations of color as those of the original one, but otherwise being random. Our surprising observation is that the original images might be reconstructed only from their low order statistics. We conclude that the perceptual information content of first and second order statistics of natural images, when considered jointly, is greater than has been previously appreciated, and therefore might be utilized for efficient representations and processing of visual information.A joint work with prof. Ohad Ben-Shahar.

In many fields of application we encounter very large graphs. Because of their size and for many other practical reasons, it is completely infeasible to calculate complicated graph parameters of such graphs. Yet, and since we still want to extract some useful information from the data, what should we do? Current practices in this area are very unsatisfactory and often concentrate on easy-to-compute but fairly uninformative parameters such as the degree distribution of the vertices. Another approach which is also practiced in certain circles is take a ``local" view of the graph. Namely, fix some small integer k; sample at random k-tuples of veritces and look at the distribution of the induced k-vertex subgraphs. This leads to many interesting questions, on some of which we now have fairly satisfactory answers, while others are still very hard and challenging: 1. To what extent do local profiles characterize the big graph? 2. What local profiles are possible? 3. What global conclusions can be drawn from local information?