Near Extensions and Alignment of Data in R(superscript)n

Steven B. Damelin is a mathematical scientist having earned his BSc (Hon), Masters and PhD at the University of the Witwatersrand. His PhD advisor, Doron Lubinsky is Full Professor at Georgia Tech. His research interests include Approximation theory, Manifold Learning, Neural Science, Computer Vision, Data Science and Signal Processing having published over 77 research papers and 2 books. He has held several academic positions including Visiting Scholar at University of Michigan, IMA new Directions Professor, University of Minnesota, Full Professor at Georgia Southern University and Editor, Mathematical Reviews, American Mathematical Society. He resides in Ann Arbor, Michigan, USA.

Preface xiii

Overview xvii

Structure xix

1 Variants 1–2 1

1.1 The Whitney Extension Problem 1

1.2 Variants (1–2) 1

1.3 Variant 2 2

1.4 Visual Object Recognition and an Equivalence Problem in Rd 3

1.5 Procrustes: The Rigid Alignment Problem 4

1.6 Non-rigid Alignment 6

2 Building ε-distortions: Slow Twists, Slides 9

2.1 c-distorted Diffeomorphisms 9

2.2 Slow Twists 10

2.3 Slides 11

2.4 Slow Twists: Action 11

2.5 Fast Twists 13

2.6 Iterated Slow Twists 15

2.7 Slides: Action 15

2.8 Slides at Different Distances 18

2.9 3D Motions 20

2.10 3D Slides 21

2.11 Slow Twists and Slides: Theorem 2.1 23

2.12 Theorem 2.2 23

3 Counterexample to Theorem 2.2 (part (1)) for card (E)> d 25

3.1 Theorem 2.2 (part (1)), Counterexample: k > d 25

3.2 Removing the Barrier k > d in Theorem 2.2 (part (1)) 27

4 Manifold Learning, Near-isometric Embeddings, Compressed Sensing, Johnson–Lindenstrauss and Some Applications Related to the near Whitney extension problem 29

4.1 Manifold and Deep Learning Via c-distorted Diffeomorphisms 29

4.2 Near Isometric Embeddings, Compressive Sensing, Johnson–Lindenstrauss and Applications Related to c-distorted Diffeomorphisms 30

4.3 Restricted Isometry 31

5 Clusters and Partitions 33

5.1 Clusters and Partitions 33

5.2 Similarity Kernels and Group Invariance 34

5.3 Continuum Limits of Shortest Paths Through Random Points and Shortest Path Clustering 35

5.3.1 Continuum Limits of Shortest Paths Through Random Points: The Observation 35

5.3.2 Continuum Limits of Shortest Paths Through Random Points: The Set Up 36

5.4 Theorem 5.6 37

5.5 p-power Weighted Shortest Path Distance and Longest-leg Path Distance 37

5.6 p-wspm, Well Separation Algorithm Fusion 38

5.7 Hierarchical Clustering in Rd 39

6 The Proof of Theorem 2.3 41

6.1 Proof of Theorem 2.3 (part(2)) 41

6.2 A Special Case of the Proof of Theorem 2.3 (part (1)) 42

6.3 The Remaining Proof of Theorem 2.3 (part (1)) 45

7 Tensors, Hyperplanes, Near Reflections, Constants (η, τ, K) 51

7.1 Hyperplane; We Meet the Positive Constant η 51

7.2 “Well Separated”; We Meet the Positive Constant τ 52

7.3 Upper Bound for Card (E); We Meet the Positive Constant K 52

7.4 Theorem 7.11 52

7.5 Near Reflections 52

7.6 Tensors, Wedge Product, and Tensor Product 53

8 Algebraic Geometry: Approximation-varieties, Lojasiewicz, Quantification: (ε, δ)-Theorem 2.2 (part (2)) 55

8.1 Min–max Optimization and Approximation-varieties 56

8.2 Min–max Optimization and Convexity 57

9 Building ε-distortions: Near Reflections 59

9.1 Theorem 9.14 59

9.2 Proof of Theorem 9.14 59

10 ε-distorted diffeomorphisms, O(d) and Functions of Bounded Mean Oscillation (BMO) 61

10.1 Bmo 61

10.2 The John–Nirenberg Inequality 62

10.3 Main Results 62

10.4 Proof of Theorem 10.17 63

10.5 Proof of Theorem 10.18 66

10.6 Proof of Theorem 10.19 66

10.7 An Overdetermined System 67

10.8 Proof of Theorem 10.16 70

11 Results: A Revisit of Theorem 2.2 (part (1)) 71

11.1 Theorem 11.21 71

11.2 η blocks 74

11.3 Finiteness Principle 76

12 Proofs: Gluing and Whitney Machinery 77

12.1 Theorem 11.23 77

12.2 The Gluing Theorem 78

12.3 Hierarchical Clusterings of Finite Subsets of Rd Revisited 81

12.4 Proofs of Theorem 11.27 and Theorem 11.28 82

12.5 Proofs of Theorem 11.31, Theorem 11.30 and Theorem 11.29 86

13 Extensions of Smooth Small Distortions [41]: Introduction 89

13.1 Class of Sets E 89

13.2 Main Result 89

14 Extensions of Smooth Small Distortions: First Results 91

Lemma 14.1 91

Lemma 14.2 92

Lemma 14.3 92

Lemma 14.4 93

Lemma 14.5 93

15 Extensions of Smooth Small Distortions: Cubes, Partitions of Unity, Whitney Machinery 95

15.1 Cubes 95

15.2 Partition of Unity 95

15.3 Regularized Distance 95

16 Extensions of Smooth Small Distortions: Picking Motions 99

Lemma 16.1 99

Lemma 16.2 101

17 Extensions of Smooth Small Distortions: Unity Partitions 103

18 Extensions of Smooth Small Distortions: Function Extension 105

Lemma 18.1 105

Lemma 18.2 106

19 Equidistribution: Extremal Newtonian-like Configurations, Group Invariant Discrepancy, Finite Fields, Combinatorial Designs, Linear Independent Vectors, Matroids and the Maximum Distance Separable Conjecture 109

19.1 s-extremal Configurations and Newtonian s-energy 109

19.2 [−1, 1] 110

19.2.1 Critical Transition 110

19.2.2 Distribution of s-extremal Configurations 111

19.2.3 Equally Spaced Points for Interpolation 112

19.3 The n-dimensional Sphere, Sn Embedded in Rn + 1 112

19.3.1 Critical Transition 112

19.4 Torus 113

19.5 Separation Radius and Mesh Norm for s-extremal Configurations 114

19.5.1 Separation Radius of s > n-extremal Configurations on a Set Yn 116

19.5.2 Separation Radius of s < n − 1-extremal Configurations on Sn 116

19.5.3 Mesh Norm of s-extremal Configurations on a Set Yn 116

19.6 Discrepancy of Measures, Group Invariance 117

19.7 Finite Field Algorithm 119

19.7.1 Examples 120

19.7.2 Spherical ̂t-designs 120

19.7.3 Extension to Finite Fields of Odd Prime Powers 121

19.8 Combinatorial Designs, Linearly Independent Vectors, MDS Conjecture 121

19.8.1 The Case q = 2 122

19.8.2 The General Case 122

19.8.3 The Maximum Distance Separable Conjecture 123

20 Covering of SU(2) and Quantum Lattices 125

20.1 Structure of SU(2) 126

20.2 Universal Sets 127

20.3 Covering Exponent 128

20.4 An Efficient Universal Set in PSU(2) 128

21 The Unlabeled Correspondence Configuration Problem and Optimal Transport 131

21.1 Unlabeled Correspondence Configuration Problem 131

21.1.1 Non-reconstructible Configurations 131

21.1.2 Example 132

21.1.3 Partition Into Polygons 134

21.1.4 Considering Areas of Triangles—10-step Algorithm 134

21.1.5 Graph Point of View 137

21.1.6 Considering Areas of Quadrilaterals 137

21.1.7 Partition Into Polygons for Small Distorted Pairwise Distances 138

21.1.8 Areas of Triangles for Small Distorted Pairwise Distances 138

21.1.9 Considering Areas of Triangles (part 2) 141

21.1.10 Areas of Quadrilaterals for Small Distorted Pairwise Distances 142

21.1.11 Considering Areas of Quadrilaterals (part 2) 145

22 A Short Section on Optimal Transport 147

23 Conclusion 149

References 151

Index 159