Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems

DOI10.1007/978-3-319-21362-0_11zbMATH Open1439.05172arXiv1503.01837OpenAlexW1543767267MaRDI QIDQ3452284FDOQ3452284

Menghan Wang, Meera Sitharam

Publication date: 11 November 2015

Published in: Automated Deduction in Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1503.01837

zbMATH Keywords

non-uniform hypergraphdictionary learning problems

Mathematics Subject Classification ID

Hypergraphs (05C65) Finite affine and projective planes (geometric aspects) (51E15)

Cites Work

• An algorithm for two-dimensional rigidity percolation: The pebble game
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• The Rigidity of Graphs
• The Algebraic Geometry of Motions of Bar-and-Body Frameworks
• Pin-collinear body-and-pin frameworks and the molecular conjecture
• Sparse hypergraphs and pebble game algorithms
• Body-and-cad geometric constraint systems
• ON AFFINE RIGIDITY
• Slider-pinning rigidity: a Maxwell-Laman-type theorem
• The Algebraic Geometry of Stresses in Frameworks
• Symbolic constraints in constructive geometric constraint solving
• On the number of fundamental fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• The combinatorial geometry of stresses in frameworks

This page was built for publication: Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452284)