- 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.