Seminar Details

Seminar Details


Apr 29

3:30 pm

Recovery of Simultaneously Structured Models with Limited Information

Maryam Fazel


University of Washington - Electrical Engineering

Finding models with a low-dimensional structure, given a number of linear observations much smaller than the ambient dimension, has been well-studied in recent years. Examples of such models are sparse vectors, low-rank matrices, and the sum of sparse and low-rank matrices.
In many signal processing and machine learning applications, the desired model has \emph{multiple} structures simultaneously. Applications include sparse phase retrieval, and learning models with several structural priors in machine learning tasks. Often convex penalties that promote individual structures are known, and require a minimal number of generic measurements (e.g.,$\ell$1 norm for sparsity, nuclear norm for matrix rank), so it is reasonable to minimize a combination of such norms. We show that, surprisingly, if we use multiobjective optimization with the individual norms, we can do no better (order-wise) than an algorithm that exploits only one of the structures. This result holds in a general setting and suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation, not one that is a function of relaxations used for each structure. We also consider `denoising' for simultaneously structured signals, and provide bounds on the minimax denoising risk for Gaussian noise.

Maryam Fazel is an assistant professor of Electrical Engineering at the University of Washington, Seattle, with adjunct appointments in the Computer Science and Engineering, Mathematics, and Statistics departments. Maryam received her MS and PhD in EE from Stanford University, her BS in EE from Sharif University of Technology in Iran, and was a Rsesearch Scientist at Caltech prior to joining UW in 2008. Maryam is a recipient of the NSF Career Award (2009), and the UW EE Outstanding Teaching Award (2009). Her current research interests include convex optimization, and parsimonious models in machine learning and signal processing.