Atomic Norm Denoising with Applications to Line Spectral Estimation | Reliability of Content Identification

Title: Atomic Norm Denoising with Applications to Line Spectral Estimation
by Badri Narayan Bhaskar

The sub-Nyquist estimation of line spectra is a classical problem in signal processing, but currently popular subspace-based techniques have few guarantees in the presence of noise and rely on a priori knowledge about system model order. Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectrum estimation that provides theoretical guarantees for the mean- square-error performance in the presence of noise and without advance knowledge of the model order. We propose an abstract theory of denoising with atomic norms which is specialized to provide a convex optimization problem for estimating the frequencies and phases of a mixture of complex exponentials with guaranteed bounds on the mean-squared-error. In general, our proposed optimization problem has no known polynomial time solution, but we provide an efficient algorithm, called DAST, based on the Fast Fourier Transform that achieves nearly the same error rate. We compare DAST with Cadzow’s canonical alternating projection algorithm, which performs marginally better under high signal-to-noise ratios when the model order is known exactly, and demonstrate experimentally that DAST outperforms other denoising techniques, including Cadzow’s, over a wide range of signal-to-noise ratios.

Title: Reliability of Content Identification
by Gautam Dasarathy

The proliferation of multimedia content in our lives has generated a number of interesting problems viz., detection of copyright violation on video-sharing websites, music identification, multimedia tagging etc. The automation of any of these procedures requires an efficient Content Identification (ID) system i.e., a system that stores information about a set of items (“fingerprints”) in a database from which one can query at a later time.

This talk deals with such Content ID systems. We will see how one can use tools from Information Theory to analyze and understand their performance. In particular, we will propose an algorithm to solve the Content ID problem and show how to use the powerful “method of types” to obtain non-asymptotic bounds on the probability of failure. We will also highlight the insights that this analysis gives us and the extensions that it suggests. This is joint work with Prof. Stark C. Draper.