April 29, 2014, 4:00pm
Rina Foygel, Department of Statistics, University of Chicago.
Demixing signals: the geometry of corrupted sensing
Abstract: In the compressed sensing problem, a high-dimensional signal with underlying structure can often be recovered with a small number of linear measurements. When multiple structured signals are superimposed, similar techniques can be used to try to separate the signals at a low sample size. We extend theoretical work on compressed sensing to the corrupted sensing problem, where our measurements of a structured signal are corrupted in a structured way (such as a sparse set of outliers in the measurements). Convex penalties placed on the signal and the corruption reflect their respective latent structure (e.g. sparsity, block-wise sparsity, low rank, etc). The resulting penalized optimization problem involves a tuning parameter controlling the tradeoff between the two penalties. We find that this tuning parameter can be chosen by comparing geometric properties of the two types of structure, which requires no cross-validation and yields nearly optimal results in theory and in simulations.
Joint work with Lester Mackey.