Recovery and Denoising of Simultaneously Structured Models with Limited Information


Event Speaker: 

Maryam Fazel (U. Washington)

Event Location: 


Event Date/Time: 

Tuesday, May 7, 2013 - 4:00pm

Reception to follow.
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.

This talk covers joint work with Samet Oymak, Amin Jalali, Babak Hassibi, and Yonina Eldar.

Maryam Fazel is an assistant professor of Electrical Engineering at the University of  Washington, Seattle, with adjunct appointments in the departments of Computer Science and Engineering, Mathematics, and Statistics. 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. She 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.