Illinois/Missouri Applied Harmonic Analysis Seminar


March 27, 2009

John J. Benedetto - Director, Norbert Wiener Center, University of Maryland
Frames for Classification, Coding, and Vector-valued Codes (pdf of the presentation)
Frame theoretic modeling has emerged as an effective means of addressing problems where numerical stability and robust signal representation are desired goals. There is also a new level of applicability where frames are intrinsic to realistic modeling of some physical phenomena. We present and develop three examples from current and central research areas. These areas are the following: classification problems for spectral imaging data; coding or quantization in low bit environments; and the formulation of ambiguity functions in the setting of vector-valued codes arising in multi-sensor or MIMO settings.

Emmanuel Candes - Ronald and Maxine Linde Professor, California Institute of Technology
Exact Matrix Completion via Convex Optimization
This talk considers a problem of considerable practical interest: the recovery of a matrix of data from a sampling of its entries. For instance, in partially filled out surveys we would like to infer the many missing entries. In the area of recommender systems, users submit ratings on a subset of entries in a database, and the vendor provides recommendations based on the users' preferences. Users rate only a few items, but the vendor would like to infer their preference for unrated items - the famous "Netflix problem".

Formally, suppose that we observe m entries selected uniformly at random from a matrix. Can we complete the matrix and recover the entries that we have not seen? We show (perhaps surprisingly) that one can recover low-rank matrices exactly from a comparatively small number of entries. Further, perfect recovery is possible by solving a simple convex optimization program, namely, a convenient semidefinite program (SDP). This result hinges on powerful techniques in probability theory.

Yoram Bresler - University of Illinois, Urbana-Champaign
Spectrum-Blind Sampling and Compressive Sensing for Continuous-index Signals (pdf of the presentation)
We revisit spectrum-blind sampling (SBS), a sensing technique we introduced in the mid-90 for signals with unknown but sparse spectrum, and explore its relationship to compressive sensing (CS). SBS is "compressive" in the sense that the required sampling rate is determined by the measure of the spectral support of the spectrum, rather than by the range of frequencies contained in the signal. SBS is applicable to continuous or discrete-index signals, finite or infinite length, in one or more dimensions. Using a periodic non-uniform sampling pattern, SBS reduces the reconstruction problem for such signals to a finite dimensional CS problem for DFT-sparse signals, followed by inexpensive linear shift-invariant filtering.

On the one hand, recent results on efficient reconstruction in CS provide reconstruction techniques for SBS. On the other hand, SBS provides efficient designs for blind, non-adaptive, sensing of spectrum-sparse signals, with minimal sampling requirements, reconstruction cost only linear in the amount of data, and robustness against noise.