The Enigma cipher machine was a series of encryption devices used before and during WWII. The Enigma had an enormous key space, one that the Nazis were sure the Allies would never be able to exhaust over, and because of this the Nazis were totally confident of the device’s security …
A common prior in modern statistical signal processing is that an observed signal is the noisy measurement of a few weighted sources. For example, the image of a collection of point sources of light can be parameterized by their locations and intensities. The goal of superresolution is to remove the …
I will first define positive semidefinite rank and mention some of its applications. We study the set of matrices of given psd rank. This set is semialgebraic. As a first step to giving a semialgebraic description, we describe its boundary. This is ongoing work with Kaie Kubjas and Richard Robinson.
The recent explosion of web analytics tools has enabled us to collect an immense amount of partial preferences for large sets of items such as products from Amazon, movies from Netflix, or restaurants from Yelp, from a large and diverse population of users through transactions, clicks, etc. Modeling, learning, and …
High-dimensional low-rank structure arises in many applications including genomics, signal processing, and social science. In this talk, we discuss some recent results on high-dimensional low-rank matrix recovery, including low-rank matrix recovery via rank-one projections and structured matrix completion. We provide theoretical justifications for the proposed methods and derive lower bounds …
In harmonic analysis we work to understand signals and operators by breaking them up into simpler pieces. We will discuss several problems for which these pieces live on lower dimensional sets whose curvature makes them seem bigger than they are. Surprising connections to some geometric and physical problems will also …
We propose an algorithm for minimizing expected risk F that shares some properties with randomized incremental aggregated gradient methods as well as dynamic sampling methods. Unlike aggregated gradient methods, which are designed to revisit the training set many times, the algorithm proposed here is well suited for problems involving a …
Bacteria and other organisms do not follow the paradigm of vertical inheritance of genetic material. Human beings, for example, inherit their DNA from their parents only (vertical transfer), but bacteria can share DNA between different species (horizontal transfer). Therefore, their evolution cannot be modeled by a tree. To incorporate these …
We develop a new active learning algorithm for the streaming setting satisfying three important properties: 1) It provably works for any classifier representation and classification problem including those with severe noise. 2) It is efficiently implementable with an ERM oracle. 3) It is more aggressive than all previous approaches satisfying …
Network models provide a unifying framework for understanding dependencies among variables in medical, biological, and other sciences. Networks can be used to reveal underlying data structures, infer functional modules, and facilitate experiment design. In practice, however, size, uncertainty and complexity of the underlying associations render these applications challenging. In this …