EE Seminar: On the injectivity and (in)stability of invariant encoding
https://us02web.zoom.us/j/86785731080?pwd=dk10aVJNM3NXeHE3WFJvZmlUQndadz09
Meeting ID: 867 8573 1080
Passcode: TAUEESYS
Speaker: Dr. Nadav Dym
Department of Mathematics of Duke University
Monday, November 9th, 2020, at 15:00
On the injectivity and (in)stability of invariant encoding
Abstract
Quotient spaces are a natural mathematical tool to describe a variety of algorithmic problems in computer vision and related fields, where different objects are to be compared while their natural symmetries are to be ignored.
One popular approach for working in quotient spaces is cancelling out symmetries by finding a canonical alignment of the objects at hand. This approach typically involves solving a challenging optimization problem over the symmetry group. We will review the tractability of these problems for sets, their intractability for graphs, and recent advances in the complexity of computing these problems for the intermediate case of rigid point clouds.
An alternative approach for working in quotient spaces avoids the computational challenges of alignment by directly mapping objects to features invariant to the object’s symmetries. The challenge with this approach is devising a sufficiently expressive family of invariant features. We will describe constructive methods for mapping quotient spaces injectively to a finite set of invariants, which lead to proofs of universality of networks for sets and rigid point clouds, and to injectivity of linear phaseless measurements in the context of phase retrieval problems. We will then discuss results in the phase retrieval literature that suggest that though injective, mappings to invariant features can be unstable and suffer from the curse of dimensionality. These results indicate that every system of invariants has `blind spots’, which corresponds to `disconnected signals’ in the measurement domain. We will describe work to quantify the stability via measures of connectivity used in spectral graph theory, and in particular show that real phase retrieval is related to the Cheeger constant, while complex phase retrieval relates to the second eigenvalue of the Laplacian.
Short Bio
I am an applied mathematician and computer scientist, interested in the development and analysis of algorithms, typically targeting 3D problems in computer vision and related fields. I am currently working on problems related to global optimization, phase retrieval, and theoretical and geometric deep learning. I am an Assistant Research Professor at the Department of Mathematics of Duke University, hosted by Prof. Ingrid Daubechies at the Information Initiative at Duke (iiD). In 2018 I completed my PhD in the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman. I have received a BSc and MSc in mathematics from the Hebrew University.
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בצ'אט
