The Taub Faculty of Computer Science Events and Talks

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