Seminars & Events for PACM IDeAS

March 9, 2016
2:30pm - 3:30pm
Convex optimization approaches to protein structural calculation from NMR

Nuclear magnetic resonance (NMR) spectroscopy is the most-used technique for protein structure determination besides X-ray crystallography. Typically the 3D structure of a protein is obtained through finding the coordinates of atoms subject to pairwise distance constraints. However, for large proteins there are usually insufficient distance measurements and the structure determination problem becomes ill-posed. Residual dipolar coupling (RDC) measurements provide additional geometric information on the angles between bond directions and the principal-axis-frame. The optimization problem involving RDC is non-convex and we present a novel convex programming relaxation to it by incorporating quaternion algebra. In simulations we attain the Cramer-Rao lower bound with relatively efficient running time.

Speaker: Yuehaw Khoo, Physics, Princeton University
Location:
Fine Hall 224
March 16, 2016
2:30pm - 3:30pm
Multi-taper spectral estimation and accumulation phenomena

multi-taper methods aim to recover the spectral density of a point process by weighting the data with different masks and then performing an average that reduces variance. I'll present performance bounds for one central example of those methods: Thomson's spectral estimator. The estimates allow us to quantify the trade-off between bias and variance reduction. The key element of the analysis is thedescription of the aggregated profile of the data tapers. I'll discuss other applications of these methods in time-frequency analysis and determinantal point processes.  This is joint work with Luis Daniel Abreu - Acoustics Research Institute, Austrian Academy of Sciences.

Speaker: Jose-Luis Romero, University of Vienna
Location:
Fine Hall 224
March 23, 2016
2:30pm - 3:30pm
Exploring non stationary and multivariable time series by Concept and alternating diffusion

Explosive technological advances lead to current and future exponential growth of massive data-sets in medicine and health-related fields. Of particular importance is an adaptive acquisition of suitable intrinsic features and an innovative approach to combine information extracted from multi-modal datasets. For example, the hidden low dimensional physiological dynamics often expresses itself as the time-varying periodicity and trend in the observed dataset. In this talk, I will focus on the non stationary and multivariable time series analysis by combining two adaptive signal processing techniques, alternating diffusion (AD) and concentration of frequency and time (Concept). In addition to the theoretical justification, a direct application to the sleep-cycle and anesthesia depth problem will be demonstrated.

Speaker: Hau-Tieng Wu, University of Toronto
Location:
Fine Hall 224
March 30, 2016
2:30pm - 3:30pm
The expected norm of a sum of independent random matrices: An elementary approach

In contemporary applied and computational mathematics, a frequent challenge is to bound the expectation of the spectral norm of a sum of independent random matrices. This quantity is controlled by the norm of the expected square of the random matrix and the expectation of the maximum squared norm achieved by one of the summands; there is also a weak dependence on the dimension of the random matrix. The purpose of this talk is to give a complete, elementary proof of this important, but underappreciated, inequality.

Speaker: Joel Tropp, Caltech
Location:
Fine Hall 224
April 6, 2016
2:30pm - 3:30pm
Phase retrieval from a single diffraction pattern of separated objects

Recent advances in X-ray free-electron lasers allow capturing of the diffraction pattern from a single nanoparticle before it disintegrates, in so-called ‘diffraction before destruction’ experiments. However, in order to reconstruct the nanoparticle structure from the diffraction pattern, the diffraction phase must be retrieved. Presently, the phase is reconstructed by iterative algorithms, imposing a non-convex computational challenge. Here we present a scheme for convex single-shot phase retrieval for two (or more) sufficiently separated objects, demonstrated in two dimensions (2D). 

Speaker: Oren Raz, Maryland University
Location:
Fine Hall 224
April 13, 2016
2:30pm - 3:30pm
Reconstruction of Molecules in Heterogeneous Samples in Cryo-electron Microscopy using SDP

The Cryo-electron microscopy (Cryo-EM) reconstruction problem is to recover a 3D structure of a molecule from 2D images, in the presence of high noise levels and in the absence of information about the relative orientations of the images. In many cases, the problem is further complicated by heterogeneous samples, containing a variety of molecules. I will talk about approaches to classification and discuss a simultaneous classification and determination of relative orientations using semidefinite programming (SDP).

Speaker: Roy Lederman, Princeton University
Location:
Fine Hall 224
May 2, 2016
11:00am - 12:00pm
A message passing algorithm for cryo-EM and synchronization problems

In synchronization tasks, a collection of entities have latent 'alignments' drawn from some symmetry group, and the task is to recover the relative alignments based on very noisy pairwise observations. A central example is the recovery of molecule rotations in cryo-electron microscopy. We present a new algorithm following the framework of approximate message passing, which statistical physics suggests may yield the optimal reconstruction. Our approach leverages the representation theory of compact groups to give a unified approach for all such problems.

Speaker: William Perry, Massachusetts Institute of Technology
Location:
Fine Hall 214
May 2, 2016
4:00pm - 5:00pm
How Robust are Reconstruction Thresholds for Community Detection?

The stochastic block model is a model for community detection in graphs: n nodes are partitioned into two hidden communities and we observe a random graph where within-community edges occur with probability a/n and between-community edges occur with probability b/n (for some constants a > b). The goal is to observe this graph and (approximately) recover the hidden community structure. This problem is known to exhibit sharp threshold behavior: it is information-theoretically possible to recover the communities (better than random guessing, in the limit of large n) precisely when (a-b)^2 > 2(a+b).

Speaker: Alex Wein, Massachusetts Institute of Technology
Location:
Fine Hall 214
May 4, 2016
2:30pm - 3:30pm
ShapeFit: Exact location recovery from corrupted pairwise directions

We consider the problem of recovering a set of locations given observations of the direction between pairs of these locations.   This recovery task arises from the Structure from Motion problem, in which a three-dimensional structure is sought from a collection of two-dimensional images.  In this context, the locations of cameras and structure points are to be found from epipolar geometry and point correspondences among images.  These correspondences are often incorrect because of lighting, shadows, and the effects of perspective.  Hence, the resulting observations of relative directions contain significant corruptions.  Over the past few years, researchers have introduced several algorithms for outlier-tolerant location recovery.  For example, Wilson and Snavely introduced the 1dSfM method, and Ozyesil and Singer introduced an second-

Speaker: Paul Hand, Rice University
Location:
Fine Hall 224
May 9, 2016
2:30pm - 3:30pm
Optimal detection of weak principal components in high-dimensional data

Please note special day (Monday).   Principal component analysis is a widely used method for dimension reduction. In high dimensional data, the ``signal'' eigenvalues corresponding to weak principal components (PCs) do not necessarily separate from the bulk of the ``noise'' eigenvalues. In this setting, it is not possible to decide based on the largest eigenvalue alone whether or not there are "signal" PCs in the data. In this talk we explore this phenomenon in a general model that captures the shape of eigenvalue distributions often seen in applications. We show how to construct statistical tests to detect principal components, based on all eigenvalues. We also explain how recent computational advances in random matrix theory enable the efficient implementation of our methods.

Speaker: Edgar Dobriban, Stanford University
Location:
TBD
May 11, 2016
2:30pm - 3:30pm
On the Solution of Elliptic Partial Differential Equations on Regions with Corners

The solution of elliptic partial differential equations on regions with non-smooth boundaries (edges, corners, etc.) is a notoriously refractory problem. In this talk, I observe that when the problems are formulated as boundary integral equations of classical potential theory, the solutions (of the integral equations) in the vicinity of corners are representable by series of elementary functions. In addition to being analytically perspicuous, the resulting expressions lend themselves to the construction of accurate and efficient numerical algorithms. The results are illustrated by a number of numerical examples.

Speaker: Kirill Serkh, Yale University
Location:
Fine Hall 224
May 18, 2016
2:30pm - 3:30pm
Randomized Algorithms for Matrix Decomposition

Matrix decompositions, and especially SVD, are very important tools in data analysis. When big data is processed, the computation of matrix decompositions becomes expensive and impractical. In recent years, several algorithms, which approximate matrix decomposition, have been developed. These algorithms are based on metric conservation features for linear spaces of random projections. We present a randomized method based on sparse matrix distribution that achieves a fast approximation with bounded error for low rank matrix decomposition.

Speaker: Yariv Aizenbud, Tel Aviv University
Location:
Fine Hall 224