Korman Center, Room 245
Colloquium: Simplifications of the Lifting Approach for Quadratic Signal Recovery Problems
Wednesday, October 2, 2013
3:00 PM-4:00 PM
Speaker: Paul Hand, Instructor in Applied Mathematics, Massachusetts Institute of Technology
Abstract: Many signal recovery problems can be quadratic in nature, such as phase retrieval, blind deconvolution, sparse PCA, and the discovery of a sparse nonzero vector belonging to a subspace. Such problems in R^n can be convexified by introducing n^2 variables corresponding to each quadratic combination of unknowns. This approach often gives rise to an n x n matrix recovery problem that is convex and has provable recovery guarantees. Because the dimensionality has been squared, it is an important task to find simplifications that make computation more tractable. We will discuss two examples where the lifting approach can be simplified while retaining recovery guarantees. These examples will be the phase retrieval problem and the task of discovering a sparse nonzero vector belonging to a subspace. In the former case, the matrix recovery problem can be simplified from an optimization problem to a feasibility problem. In the latter case, the matrix recovery problem can be replaced by n linear programs on vectors.