Georgia Institute of Technology College of Sciences

This talks introduces a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging and many other applications. Our approach combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that any complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we present some novel theory showing that our entire approach may be provably surprisingly effective.

This talk is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. In the second part of the talk, we present applications in computer vision. In video surveillance, for example, our methodology allows for the detection of objects in a cluttered background. We show how the methodology can be adapted to simultaneously align a batch of images and correct serious defects/corruptions in each image, opening new perspectives.

[This talk is canceled. Sep 9, 2012 ] Centroidal Voronoi Tessellations(CVTs) are special Voronoi Tessellations where the centroidal of each segments coincides with its Voronoi generators. CVT has broad applications in various fields. In this talk, we will present a new development for CVT algorithms, Edge-weighted CVTs, which puts the segment boundary length information to the consideration of CVT algorithms. We will demonstrate how EWCVTs can be applied in image segmentations, superpixels, etc.

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance of $S$ or the sparsity of the cut $(S,\bar{S})$)is bounded as follows: \phi(S) = w(S,S') /w(S) \leq \sqrt{2 \lambda_2},where $w$ is the total edge weight of a subset or a cut and $\lambda_2$ is the second smallest eigenvalue of thenormalized Laplacian of the graph.We study natural generalizations of the sparsest cut in a graph: (i) a partition ofthe vertex set into $k$ parts that minimizes the sparsity of the partition (defined as the ratio of theweight of edges between parts to the total weight of edges incident to the smallest $k-1$ parts); (ii) a collection of $k$ disjoint subsets $S_1, \ldots, S_k$ that minimize $\max_{i \in [k]} \phi(S_i)$; (iii) a subset of size $O(1/k)$ of the graph with minimum expansion. Our main results are extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian.In particular, for the sparsest $k$-partition, we prove that the sparsity is at most $8\sqrt{\lambda_k} \log k$where $\lambda_k$ is the $k^{th}$ smallest eigenvalue of the normalized Laplacian matrix.For the $k$ sparse cuts problem we prove that there exist$ck$ disjoint subsets $S_1, \ldots, S_{(1 - \eps)k}$, such that \max_i \phi(S_i) \leq C \sqrt{\lambda_{k} \log k}where $C>0$ are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for any $k$, there is a subset $S$ whoseweight is at most a $\bigO(1/k)$ fraction of the total weight and $\phi(S) \le C \sqrt{\lambda_k \log k}$. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method.Based on joint work with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.