Combinatorial rigidity and independence of generalized pinned subspace-incidence constraint systems

Abstract

Given a hypergraph $H$ with $m$ hyperedges and a set $X$ of $m$ \emph{pins}, i.e.\ globally fixed subspaces in Euclidean space ${\mathbb{R}}^d$, a \emph{pinned subspace-incidence system} is the pair $(H,X)$, with the constraint that each pin in $X$ lies on the subspace spanned by the point realizations in ${\mathbb{R}}^d$ of vertices of the corresponding hyperedge of $H$. We are interested in combinatorial characterization of pinned subspace-incidence systems that are \emph{minimally rigid}, i.e.\ those systems that are guaranteed to generically yield a locally unique realization. As is customary, this is accompanied by a characterization of generic independence as well as rigidity. In a previous paper \cite{sitharam2014incidence}, we used pinned subspace-incidence systems towards solving the \emph{fitted dictionary learning} problem, i.e.\ dictionary learning with specified underlying hypergraph, and gave a combinatorial characterization of minimal rigidity for a more restricted version of pinned subspace-incidence system, with $H$ being a uniform hypergraph and pins in $X$ being 1-dimension subspaces. Moreover in a recent paper \cite{Baker2015}, the special case of pinned line incidence systems was used to model biomaterials such as cellulose and collagen fibrils in cell walls. In this paper, we extend the combinatorial characterization to general pinned subspace-incidence systems, with $H$ being a non-uniform hypergraph and pins in $X$ being subspaces with arbitrary dimension. As there are generally many data points per subspace in a dictionary learning problem, which can only be modeled with pins of dimension larger than $1$, such an extension enables application to a much larger class of fitted dictionary learning problems.