Events Calendar

Extracting Hidden Structure From Data: Provable Phase Retrieval by Non-Convex Optimization

Speaker: Mahdi Soltanolkotabi, Stanford University

Talk Title: Extracting Hidden Structure From Data: Provable Phase Retrieval by Non-Convex Optimization

Abstract: A major challenge in modern data analysis is to reliably and automatically discover hidden structure in data with little or no human intervention. However, many mathematical abstractions of these problems are provably intractable in their most general form. Nevertheless, it may be possible to overcome these hardness barriers by focusing on realistic cases that rule out intractable instances.

In this talk we consider the question of recovering the seemingly hidden phase of an object from intensity-only measurements, a problem which naturally appears in X-ray crystallography, speech analysis and related disciplines. We study a physically realistic setup where one can modulate the signal of interest and then collect the intensity of its diffraction pattern. We show that a non-convex formulation of the problem recovers the phase information exactly from a number of near minimal random modulations. To solve this non-convex problem, we develop an iterative algorithm that combines a careful initialization together with a novel update that escapes all local minima and provably converges to the global optimum with a geometric rate. Our proposed scheme is near optimal in terms of usage of computational and data resources. We illustrate our methods with various real data experiments.

We will also briefly discuss other problems involving hidden structure in data (in particular subspace clustering and sparse recovery with coherent and redundant dictionaries) and conclude with a discussion of directions for future research.


Biography: Mahdi Soltanolkotabi is a Ph.D. candidate in Electrical Engineering at Stanford University, advised by Emmanuel Candes. Previously, he received a Master's degree in Electrical Engineering from Stanford University (2011) and a Bachelor's degree in Electrical Engineering from Sharif University of Technology (2009). His research interests include optimization, machine learning, signal processing, high-dimensional statistics, and geometry with emphasis on applications in the information and physical sciences. He was awarded the Benchmark Stanford Graduate Fellowship (2009-2012) as well as the Stanford teaching fellowship in electrical engineering (2011).

Host: Salman Avestimehr, avestimehr@ee.usc.edu, EEB 526, x07326

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos