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

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

Authors Menghan Wang, Meera Sitharam 

Publication date 11 November 2015

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

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)

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.

Recommendations

• Combinatorial rigidity of incidence systems and application to dictionary learning
• Sparse hypergraphs with applications in combinatorial rigidity
• Rigidity Matroids
• An improved bound for the rigidity of linearly constrained frameworks
• On affine rigidity

Cites Work

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

Cited In (2)

• The combinatorial geometry of stresses in frameworks
• Combinatorial rigidity of incidence systems and application to dictionary learning

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)