[Colloquium] REVISION: Talks at TTIC: Qixing Huang, Stanford

[Dawn Ellis]

When:     Thursday, February 20th at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Speaker:  Qixing Huang, Stanford

Title:       Joint Object Matching via Matrix Completion

Joint object / graph matching is a fundamental scientific problem -- given
a collection of (partially) similar objects drawn from the same universe,
we wish to recover globally compatible mapping over them. This is a central
task spanning a wide spectrum of scientific problems, including structure
from motion, re-assembling fragmented objects, solving jigsaw puzzles,
fusing partially overlapped kinect scans, DNA/RNA sequencing, to name just
a few. In fact, the global compatibility constraint can be exploited as a
"network regularization criterion", which promises potential refinement of
naive pair-wise matching results computed in isolation. Unfortunately, this
problem is computationally prohibitive in general.

In this talk, I will deliver some encouraging news by transforming this
NP-hard combinatorial problem into tractable convex programs. The approach
is inspired by the success of matrix completion and robust PCA, and builds
upon a low-rank matrix representation of the global consistency criterion.
 Specifically, we formulate any consistent joint maps into a p.s.d.
low-rank (and sparse) matrix that encodes all pair-wise maps in blocks, and
attempt recovery via a parameter-free semidefinite program that minimizes
the incompatibility between the input and the estimate. Somewhat
surprisingly, this convex relaxation method admits exact recovery even the
majority of the input maps are corrupted. On the numerical side, it can be
efficiently solved by alternating direction methods of multipliers (ADMM),
which makes it practically appealing for large-scale problems. I will
demonstrate the usefulness of this approach on various real problems.

BIO:

Qixing Huang is a Post-doc researcher at the computer science department of
Stanford University.  His main research interests are in organizing large
collections of geometric data and exploring various data-driven
applications in analysis, animation, modeling and visualization. Qixing
Huang received the PHD degree from Stanford University in 2012, working
with Prof. Leonidas Guibas.  He is the recipient of Mr. and Mrs. Chin-Nan
Chen Stanford Graduate Fellowship from 2008-2011, and the recipient of the
Best Paper Award at the conference Symposium on Geometry Processing 2013.

Host: Gregory Shakhnarovich, gregory at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140217/c22cd6c0/attachment-0001.htm