Graphical designs and gale duality

• 成果类型: Article
• 署名作者: Babecki, Catherine; Thomas, Rekha R.
• 署名单位: University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01861-0
• 发表日期: 2023
• 页码: 703-737
• 关键词: sampling set selection; signals

摘要

A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs - cocktail party graphs, cycles, and graphs of hypercubes - by computing or bounding the smallest designs that average all but the last eigenspace in frequency order.