Simplicial flat norm with scale
We study the multiscale simplicial flat norm (MSFN) problem, which computes flat norm at various scales of sets defined as oriented subcomplexes of finite simplicial complexes in arbitrary dimensions. We show that MSFN is NP-complete when homology is defined over integers. We cast MSFN as an instanc...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2013-11-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/85 |
| _version_ | 1811274026602987520 |
|---|---|
| author | Sharif Ibrahim Bala Krishnamoorthy Kevin Vixie |
| author_facet | Sharif Ibrahim Bala Krishnamoorthy Kevin Vixie |
| author_sort | Sharif Ibrahim |
| collection | DOAJ |
| description | We study the multiscale simplicial flat norm (MSFN) problem, which computes flat norm at various scales of sets defined as oriented subcomplexes of finite simplicial complexes in arbitrary dimensions. We show that MSFN is NP-complete when homology is defined over integers. We cast MSFN as an instance of integer linear optimization. Following recent results on related problems, the MSFN integer program can be solved in polynomial time by solving its linear programming relaxation, when the simplicial complex satisfies a simple topological condition (absence of relative torsion). Our most significant contribution is the simplicial deformation theorem, which states that one may approximate a general current with a simplicial current while bounding the expansion of its mass. We present explicit bounds on the quality of this approximation, which indicate that the simplicial current gets closer to the original current as we make the simplicial complex finer. MSFN opens up the possibilities of using flat norm to denoise or extract scale information of large data sets in arbitrary dimensions. On the other hand, it allows one to employ the large body of algorithmic results on simplicial complexes to address more general problems related to currents. |
| first_indexed | 2024-04-12T23:11:47Z |
| format | Article |
| id | doaj.art-4eeb22f6e7c1476fa30ac3c53123fe89 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-04-12T23:11:47Z |
| publishDate | 2013-11-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-4eeb22f6e7c1476fa30ac3c53123fe892022-12-22T03:12:48ZengCarleton UniversityJournal of Computational Geometry1920-180X2013-11-014110.20382/jocg.v4i1a639Simplicial flat norm with scaleSharif Ibrahim0Bala Krishnamoorthy1Kevin Vixie2Washington State UniversityWashington State UniversityWashington State University and Center for Geometric Analysis and Data (CGAD)We study the multiscale simplicial flat norm (MSFN) problem, which computes flat norm at various scales of sets defined as oriented subcomplexes of finite simplicial complexes in arbitrary dimensions. We show that MSFN is NP-complete when homology is defined over integers. We cast MSFN as an instance of integer linear optimization. Following recent results on related problems, the MSFN integer program can be solved in polynomial time by solving its linear programming relaxation, when the simplicial complex satisfies a simple topological condition (absence of relative torsion). Our most significant contribution is the simplicial deformation theorem, which states that one may approximate a general current with a simplicial current while bounding the expansion of its mass. We present explicit bounds on the quality of this approximation, which indicate that the simplicial current gets closer to the original current as we make the simplicial complex finer. MSFN opens up the possibilities of using flat norm to denoise or extract scale information of large data sets in arbitrary dimensions. On the other hand, it allows one to employ the large body of algorithmic results on simplicial complexes to address more general problems related to currents.http://jocg.org/index.php/jocg/article/view/85 |
| spellingShingle | Sharif Ibrahim Bala Krishnamoorthy Kevin Vixie Simplicial flat norm with scale Journal of Computational Geometry |
| title | Simplicial flat norm with scale |
| title_full | Simplicial flat norm with scale |
| title_fullStr | Simplicial flat norm with scale |
| title_full_unstemmed | Simplicial flat norm with scale |
| title_short | Simplicial flat norm with scale |
| title_sort | simplicial flat norm with scale |
| url | http://jocg.org/index.php/jocg/article/view/85 |
| work_keys_str_mv | AT sharifibrahim simplicialflatnormwithscale AT balakrishnamoorthy simplicialflatnormwithscale AT kevinvixie simplicialflatnormwithscale |