<p>The shadow of an abstract simplicial complex <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {K}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">K</mi> </math></EquationSource> </InlineEquation> with vertices in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathbb {R}^N\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>N</mi> </msup> </math></EquationSource> </InlineEquation> is a subset of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathbb {R}^N\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>N</mi> </msup> </math></EquationSource> </InlineEquation> defined as the union of the convex hulls of simplices of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\mathcal {K}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">K</mi> </math></EquationSource> </InlineEquation>. The Vietoris–Rips complex of a metric space <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((\mathcal {S},d)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">S</mi> <mo>,</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> at scale <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation> is an abstract simplicial complex whose each <i>k</i>-simplex corresponds to <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\((k+1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> points of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mathcal {S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">S</mi> </math></EquationSource> </InlineEquation> within diameter <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation>. In case <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\mathcal {S}\subset \mathbb {R}^2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">S</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>2</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(d(a,b)=\Vert a-b\Vert \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">‖</mo> <mi>a</mi> <mo>-</mo> <mi>b</mi> <mo stretchy="false">‖</mo> </mrow> </math></EquationSource> </InlineEquation> the standard Euclidean metric, the natural shadow projection of the Vietoris–Rips complex is already proved by Chambers et al. to induce isomorphisms on <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\pi _0\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>π</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\pi _1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>π</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>. We extend the result beyond the standard Euclidean distance on <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\mathcal {S}\subset \mathbb {R}^N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">S</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>N</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> to a family of path-based metrics, <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(d^\varepsilon _{\mathcal {S}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>d</mi> <mi mathvariant="script">S</mi> <mi>ε</mi> </msubsup> </math></EquationSource> </InlineEquation>. From the pairwise Euclidean distances of points in <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\mathcal {S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">S</mi> </math></EquationSource> </InlineEquation>, we introduce a family (parametrized by <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>) of path-based Vietoris–Rips complexes <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(\mathcal {R}^\varepsilon _\beta (\mathcal {S})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mrow> <mi mathvariant="script">R</mi> </mrow> <mi>β</mi> <mi>ε</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for a scale <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\beta &gt;0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. If <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(\mathcal {S}\subset \mathbb {R}^2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">S</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>2</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> is Hausdorff-close to a planar Euclidean graph <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(\mathcal {G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>, we provide quantitative bounds on scales <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(\beta ,\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo>,</mo> <mi>ε</mi> </mrow> </math></EquationSource> </InlineEquation> for the shadow projection map of the Vietoris–Rips complex of <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\((\mathcal {S},d^\varepsilon _\mathcal {S})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">S</mi> <mo>,</mo> <msubsup> <mi>d</mi> <mi mathvariant="script">S</mi> <mi>ε</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> at scale <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation> to induce <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(\pi _1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>π</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>-isomorphism. This paper first studies the homotopy-type recovery of <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(\mathcal {G}\subset \mathbb {R}^N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo>⊂</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>N</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> using the abstract Vietoris–Rips complex of a Hausdorff-close sample <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(\mathcal {S}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">S</mi> </math></EquationSource> </InlineEquation> under the <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(d^\varepsilon _\mathcal {S}\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>d</mi> <mi mathvariant="script">S</mi> <mi>ε</mi> </msubsup> </math></EquationSource> </InlineEquation> metric. Then, our result on the <InlineEquation ID="IEq29"> <EquationSource Format="TEX">\(\pi _1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>π</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>-isomorphism induced by the shadow projection lends itself to providing also a geometrically close embedding for the reconstruction. Based on the length of the shortest loop and large-scale distortion of the embedding of <InlineEquation ID="IEq30"> <EquationSource Format="TEX">\(\mathcal {G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>, we quantify the choice of a suitable sample density <InlineEquation ID="IEq31"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> and a scale <InlineEquation ID="IEq32"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation> at which the shadow of <InlineEquation ID="IEq33"> <EquationSource Format="TEX">\(\mathcal {R}^\varepsilon _\beta (\mathcal {S})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mrow> <mi mathvariant="script">R</mi> </mrow> <mi>β</mi> <mi>ε</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is homotopy-equivalent and Hausdorff-close to <InlineEquation ID="IEq34"> <EquationSource Format="TEX">\(\mathcal {G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Vietoris–Rips shadow for Euclidean graph reconstruction

  • Rafal Komendarczyk,
  • Sushovan Majhi,
  • Atish Mitra

摘要

The shadow of an abstract simplicial complex \(\mathcal {K}\) K with vertices in \(\mathbb {R}^N\) R N is a subset of \(\mathbb {R}^N\) R N defined as the union of the convex hulls of simplices of \(\mathcal {K}\) K . The Vietoris–Rips complex of a metric space \((\mathcal {S},d)\) ( S , d ) at scale \(\beta \) β is an abstract simplicial complex whose each k-simplex corresponds to \((k+1)\) ( k + 1 ) points of \(\mathcal {S}\) S within diameter \(\beta \) β . In case \(\mathcal {S}\subset \mathbb {R}^2\) S R 2 and \(d(a,b)=\Vert a-b\Vert \) d ( a , b ) = a - b the standard Euclidean metric, the natural shadow projection of the Vietoris–Rips complex is already proved by Chambers et al. to induce isomorphisms on \(\pi _0\) π 0 and \(\pi _1\) π 1 . We extend the result beyond the standard Euclidean distance on \(\mathcal {S}\subset \mathbb {R}^N\) S R N to a family of path-based metrics, \(d^\varepsilon _{\mathcal {S}}\) d S ε . From the pairwise Euclidean distances of points in \(\mathcal {S}\) S , we introduce a family (parametrized by \(\varepsilon \) ε ) of path-based Vietoris–Rips complexes \(\mathcal {R}^\varepsilon _\beta (\mathcal {S})\) R β ε ( S ) for a scale \(\beta >0\) β > 0 . If \(\mathcal {S}\subset \mathbb {R}^2\) S R 2 is Hausdorff-close to a planar Euclidean graph \(\mathcal {G}\) G , we provide quantitative bounds on scales \(\beta ,\varepsilon \) β , ε for the shadow projection map of the Vietoris–Rips complex of \((\mathcal {S},d^\varepsilon _\mathcal {S})\) ( S , d S ε ) at scale \(\beta \) β to induce \(\pi _1\) π 1 -isomorphism. This paper first studies the homotopy-type recovery of \(\mathcal {G}\subset \mathbb {R}^N\) G R N using the abstract Vietoris–Rips complex of a Hausdorff-close sample \(\mathcal {S}\) S under the \(d^\varepsilon _\mathcal {S}\) d S ε metric. Then, our result on the \(\pi _1\) π 1 -isomorphism induced by the shadow projection lends itself to providing also a geometrically close embedding for the reconstruction. Based on the length of the shortest loop and large-scale distortion of the embedding of \(\mathcal {G}\) G , we quantify the choice of a suitable sample density \(\varepsilon \) ε and a scale \(\beta \) β at which the shadow of \(\mathcal {R}^\varepsilon _\beta (\mathcal {S})\) R β ε ( S ) is homotopy-equivalent and Hausdorff-close to \(\mathcal {G}\) G .