IDeAS

Spring 2017

IDeAS Seminar: Nonconvex Recovery of Low-Complexity Models

Speaker: 
John Wright, Columbia University
Date: 
Feb 8 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Nonconvex optimization plays important role in wide range of areas of science and engineering — from learning feature representations for visual classification, to reconstructing images in biology, medicine and astronomy, to disentangling spikes from multiple neurons. The worst case theory for nonconvex optimization is dismal: in general, even guaranteeing a local minimum is NP hard. However, in these and other applications, very simple iterative methods such as gradient descent often perform surprisingly well. 

In this talk, I will discuss examples of nonconvex optimization problems that can be solved to global optimality using simple iterative methods, which succeed independent of initialization. These include variants of the sparse dictionary learning problem, image recovery from certain types of phaseless measurements, and variants of the sparse blind deconvolution problem. These problems possess a characteristic structure, in which (i) all local minima are global, and (ii) the energy landscape does not have any “flat” saddle points. For each of the aforementioned problems, this geometric structure allows us to obtain new types of performance guarantees. I will motivate these problems from applications in imaging and computer vision, and describe how this viewpoint leads to new approaches to analyzing electron microscopy data.

Joint work with Ju Sun (Stanford), Qing Qu (Columbia), Yuqian Zhang (Columbia), Yenson Lau (Columbia) Sky Cheung, (Columbia), Abhay Pasupathy (Columbia)

John Wright is an Associate Professor in the Electrical Engineering Department at Columbia University. He received his PhD in Electrical Engineering from the University of Illinois at Urbana-Champaign in 2009, and was with Microsoft Research from 2009-2011. His research is in the area of high-dimensional data analysis. In particular, his recent research has focused on developing algorithms for robustly recovering structured signal representations from incomplete and corrupted observations, and applying them to practical problems in imaging and vision. His work has received a number of awards and honors, including the 2009 Lemelson-Illinois Prize for Innovation for his work on face recognition, the 2009 UIUC Martin Award for Excellence in Graduate Research, and a 2008-2010 Microsoft Research Fellowship, and the Best Paper Award from the Conference on Learning Theory (COLT) in 2012, the 2015 PAMI TC Young Researcher Award.

IDeAS Seminar: Synchronization over Cartan motion groups via contraction

Speaker: 
Nir Sharon, Princeton University
Date: 
Feb 15 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

The mathematical problem of group synchronization deals with the question of how to estimate unknown set of group elements from a set of their mutual relations. This problem appears as an important step in solving many real world problem such as Structure from Motion (SfM) in vision or pose graph optimization (estimating positions and orientations of mobile robots) in robotics. In this talk, we present a novel solution for synchronization over the class of the non-compact Cartan motion groups, which includes the special important case of rigid motions. Our method is based upon the idea of group contraction, which is a compactification process origin in relativistic mechanics. We show the construction of such a solution for synchronization, analyze some of its theoretical aspects, and illustrate numerically its advantages compared to some of the current state-of-the-art synchronization methods on both synthetic and real data.

IDeAS Seminar: Rapid solution of the cryo-EM reconstruction problem by frequency marching

Speaker: 
Marina Spivak, Simons Center for Data Analysis
Date: 
Feb 22 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Determining the three-dimensional structure of proteins and protein complexes at atomic resolution is a fundamental task in structural biology. Over the last decade, remarkable progress has been made using ``single particle" cryo-electron microscopy (cryo-EM) for this purpose. The reconstruction of a high-resolution image from cryo-EM data is typically formulated as a nonlinear, non-convex optimization problem for hundreds of thousands of unknown parameters. 

This leads to a very CPU-intensive task---limiting both the number of particle images which can be processed and the number of independent reconstructions which can be carried out for the purpose of statistical validation. Here, we propose a deterministic method for high-resolution reconstruction given a very low resolution initial guess, that requires a predictable and relatively modest amount of computational effort.

Marina Spivak received her B.A. from UC Berkeley and her Ph.D. in Computer Science from NYU. Her research interests include machine learning and questions in bioinformatics. Her postdoctoral research at the University of Washington focused on application of machine learning techniques to shotgun mass spectrometry protein sequencing. She joined the Simons Foundation Center for Computational Biology in 2013, where her current topic of research is development of algorithms for cryo electron microscopy data analysis.

IDeAS Seminar: A Taste of Julia for Scientific Computing

Speaker: 
Stefan Karpinski, Julia Computing
Date: 
Mar 1 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Bridging cultures that have often been distant, Julia combines expertise from the diverse fields of computer science and computational science to create a new approach to numerical computing. Julia is designed to be easy and fast and questions notions generally held to be “laws of nature” by practitioners of numerical computing:

1. High-level dynamic programs have to be slow.

2. One must prototype in one language and then rewrite in another language for speed or deployment.

3. There are parts of a system appropriate for the programmer, and other parts that are best left untouched as they have been built by the experts.

This talk will be an introduction to the Julia programming language and its design—a dance between specialization and abstraction. Specialization allows for custom treatment. Multiple dispatch, a technique from computer science, picks the right algorithm for the right circumstance. Abstraction, which is what good computation is really about, recognizes what remains the same after differences are stripped away. Abstractions in mathematics are captured as code through another technique from computer science, generic programming. Julia shows that one can achieve machine performance without sacrificing human convenience.

Stefan Karpinski is one of the co-creators of the Julia programming language and a co-founder of Julia Computing, Inc. He holds a part-time position as a Research Engineer at NYU as part of the Moore-Sloan Data Science Initiative and has previously worked as a software engineer and data scientist at AkamaiCitrix, and Etsy.

IDeAS Seminar: Structure-Aware Dictionary Learning for Graph Signals

Speaker: 
Yael Yankelevsky, Technion
Date: 
Mar 3 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Dictionary Learning techniques aim to find sparse signal representations that capture prominent characteristics in the given data. For signals residing on non-Euclidean topologies, represented by weighted graphs, an additional challenge is incorporating the underlying geometric structure of the data domain into the learning process. We introduce an approach that aims to infer and preserve the local intrinsic geometry in both dimensions of the data. Combining ideas from spectral graph theory, manifold learning and sparse representations, our proposed algorithm simultaneously takes into account the underlying graph topology as well as the data manifold structure. The efficiency of this approach is demonstrated on a variety of applications, including sensor network data completion and enhancement, image structure inference, and challenging multi-label classification problems.

Yael is a PhD student in the Computer Science Department at the Technion, working under the supervision of prof. Michael Elad. Her research interests include signal and image processing, machine learning, sparse representations, inverse problems and graphical models.

IDeAS Seminar: The effectiveness of nonconvex optimization in two problems

Speaker: 
Yuxin Chen, Princeton University
Date: 
Mar 8 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Many information and data science applications involve computation of the maximum likelihood estimates (MLE) over a high-dimensional space. Unfortunately, most MLEs are solutions to non-convex problems, which are in general intractable. 

Fortunately, some of the problems are not as hard as they may seem, and can be solved by optimizing the nonconvex objectives directly.  This talk illustrates this observation through two problems: (1) solving a random quadratic system of equations, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning;  (2) recovering a collection of discrete variables from noisy pairwise differences, which arises when one wishes to jointly align multiple images or to retrieve the genome phases from paired sequencing reads. In both cases, the proposed solutions can be accomplished within linear time, while achieving a statistical accuracy that is nearly un-improvable.

This is based on joint work with Emmanuel Candes.

Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional structured estimation, convex and nonconvex optimization, statistical learning, and information theory.

IDeAS Seminar: Applications of Noncommutative Harmonic Analysis in Engineering and the Applied Sciences

Speaker: 
Gregory Chirikjian, Johns Hopkins University
Date: 
Mar 29 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

This talk will focus more on both the mathematics and the structural biology.

Gregory S. Chirikjian received undergraduate degrees from Johns Hopkins University in 1988, and the Ph.D. degree from the California Institute of Technology, Pasadena, in 1992. Since 1992, he has been on the faculty of the Department of Mechanical Engineering, Johns Hopkins University, where he has been a full professor since 2001. From 2004-2007 he served as department chair. His research interests include robotics, applications of group theory in a variety of engineering  disciplines, and the mechanics of biological macromolecules. He is a 1993 National Science Foundation Young Investigator, a 1994 Presidential Faculty Fellow, and a 1996 recipient of the ASME Pi Tau Sigma Gold Medal. In 2008 he became a Fellow of the ASME, and in 2010 he became a Fellow of the IEEE. He is the author of more than 200 journal and conference papers and primary author on three books: Engineering Applications of Noncommutative Harmonic Analysis (2001) and Stochastic Models, Information Theory, and Lie Groups, Vols. 1+2. (2009,2011). In 2016 and expanded edition of his 2001 book came out as a Dover book under the new

title: Harmonic Analysis for Engineers and Applied Scientists.

IDeAS Seminar

Speaker: 
Yongxin Chen, Research Fellow in the Department of Medical Physics in Memorial Sloan Kettering Cancer Center.
Date: 
Mar 30 2017 - 2:30pm
Event type: 
IDeAS
Room: 
McDonnell Hall, Room 102A
Abstract: 

TBA

IDeAS Seminar: Demixing Sines and Spikes: Spectral Super-resolution in the Presence of Outliers

Speaker: 
Carlos Fernandez-Granda, NYU
Date: 
Apr 5 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

In this talk we consider the problem of super-resolving the line spectrum of a multisinusoidal signal from a finite number of samples, some of which may be completely corrupted. Measurements of this form can be modeled as an additive mixture of a sinusoidal and a sparse component. We propose to demix the two components and super-resolve the spectrum of the multisinusoidal signal by solving a convex program. Our main theoretical result is that-- up to logarithmic factors-- this approach is guaranteed to be successful with high probability for a number of spectral lines that is linear in the number of measurements, even if a constant fraction of the data are outliers. We show that the method can be implemented via semidefinite programming and explain how to adapt it in the presence of dense perturbations, as well as exploring its connection to atomic-norm denoising. In addition, we propose a fast greedy demixing method which provides good empirical results when coupled with a local nonconvex-optimization step.

Carlos Fernandez-Granda is an Assistant Professor of Mathematics and Data Science at the Center for Data Science and the Courant Institute of Mathematical Sciences at NYU. His research focuses on developing and analyzing optimization-based methods to tackle inverse problems that arise in applications such as neuroscience, computer vision and medical imaging. Before joining NYU, he completed his PhD under the supervision of Emmanuel Candes at Stanford University and then spent a year at Google, where he worked on techniques to process neural data. 

IDeAS Seminar: A random walk on the upper triangular matrices

Speaker: 
Evita Nestoridi, Princeton University
Date: 
Apr 12 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

We study the following random walk on the group of n n upper triangular matrices with coecients in Z=pZ and ones along the diagonal. Starting at the identity, at each step we choose a row at random and either add it to or subtract it from the row immediately above. The mixing time of this walk is conjectured to be asymptotically n2p2. While much has been proven in this direction by a number of authors, the full conjecture remains open. We sharpen the techniques introduced by Arias-Castro, Diaconis, and Stanley to show that the dependence on p of the mixing time is p2. To prove this result, we use super-character theory and comparison theory to bound the eigenvalues of this random walk.

IDeAS Seminar

Speaker: 
Weihao Kong, Stanford University
Date: 
Apr 18 2017 - 2:30pm
Event type: 
IDeAS
Room: 
Location TBD
Abstract: 

TBA

IDeAS Seminar

Speaker: 
Manas Rachh, Yale University
Date: 
Apr 19 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA

IDeAS Seminar

Speaker: 
Amit Moscovich, Weizman Institute of Science
Date: 
Apr 25 2017 - 2:30pm
Event type: 
IDeAS
Room: 
McDonnell Hall, Room 102A
Abstract: 

TBA

IDeAS Seminar

Speaker: 
Joel Tropp, Caltech
Date: 
Apr 26 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA

IDeAS Seminar: Algorithms for Reducing the Computational Burden of cryo-EM

Speaker: 
Marcus Brubaker, University of Toronto
Date: 
Apr 27 2017 - 2:30pm
Event type: 
IDeAS
Room: 
McDonnell Hall, Room 102A
Abstract: 

Computational expense has long been a challenge for 3D structure determination in electron cryomicroscopy (cryo-EM).  This problem has become more pressing as resolutions have increased and the desire to separate conformational computational variations has required ever-larger datasets.  This talk presents two new algorithmic developments which, when coupled with modern GPU hardware, dramatically reduces the computational requirements for cryo-EM.  Given low-resolution starting structures, high resolution structures can now be obtained in as little as 10s of minutes on modest desktop workstations.  Further, despite the severe non-convexity of the objective function, these new refinement algorithms have shown themselves to be robust to local minima, enabling ab initio structure determination and 3D classification.  Together, these algorithms can produce ab initio high resolution structures in an hour or two.  This talk will describe the underlying algorithmic advances (stochastic optimization and branch-and-bound search) along with results from their implementation in the recently released cryoSPARC software package.

Dr. Marcus Brubaker is an Assistant Professor of Computer Science at York University in Toronto, Canada.  He received his Ph.D. in Computer Science from the University of Toronto in 2011 and, before joining York University, worked as a postdoctoral fellow at the Toyota Technological Institute at Chicago.  His research interests span computer vision, machine learning and statistics and he has worked on a range of problems including video-based human motion estimation, physical models of human motion, Bayesian inference, ballistic forensics, electron cryomicroscopy and autonomous driving.  He also consults with industry on machine learning and computer vision related projects and has been involved in a number of startups, including as the co-founder of Structura Biotechnology Inc.

IDeAS Seminar

Speaker: 
Afonso Bandeira, NYU
Date: 
May 1 2017 - 2:30pm
Event type: 
IDeAS
Room: 
110 Fine Hall
Abstract: 

TBA

IDeAS Seminar

Speaker: 
Joe Zhong, Princeton University
Date: 
May 10 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA