Session: Manifolds, samples, and learning
Chair: Ralf Zimmermann
Cluster: Optimization on Manifolds
Talk 1: Dynamic Subspace Estimation using Grassmannian Geodesics
Speaker: Laura Balzano
Abstract: In this work, we consider recovering a sequence of low-rank matrices from noisy and possibly undersampled measurements, where an underlying subspace varies across samples over time. We propose a Riemannian block majorize-minimization algorithm that constrains the time-varying subspaces as a geodesic along the Grassmann manifold. Our proposed method can faithfully estimate the subspaces at each time point, even when the number of samples at each time point is less than the rank of the subspace. We demonstrate the effectiveness of our algorithm on synthetic data, dynamic fMRI data, video data, and graph data with evolving communities.
Talk 2: Shape-Graph Matching Network (SGM-Net): Registration for Statistical Shape Analysis
Speaker: Shenuan Liang
Abstract: This talk explores the statistical analysis of shapes of data objects called shape graphs, a set of nodes connected by articulated curves with arbitrary shapes. A critical need here is a constrained registration of points (nodes to nodes, edges to edges) across objects. This requires optimization over the permutations, made challenging by differences in nodes (in terms of numbers, locations) and edges (in terms of shapes, placements, and sizes) across objects. We tackle this registration problem using a novel neural-network architecture and formulate it using an unsupervised loss function derived from the elastic shape metric. This architecture results in (1) state-of-the-art performance and (2) an order of magnitude reduction in the computational cost relative to baseline approaches. We demonstrate the effectiveness of the proposed approach using both simulated data and real-world, publicly available 2D and 3D shape graphs.
Talk 3: NP-hardness of Grassmannian optimization
Speaker: Zehua Lai
Abstract: We show that unconstrained quadratic optimization over a Grassmannian is NP-hard. Our results cover all scenarios: (i) when k and n are both allowed to grow; (ii) when k is arbitrary but fixed; (iii) when k is fixed at its lowest possible value 1. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold and the orthogonal group. As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of FPTAS in all cases.
