Near Extensions and Alignment of Data in R(superscript)n
Description
Comprehensive resource illustrating the mathematical richness of Whitney Extension Problems, enabling readers to develop new insights, tools, and mathematical techniques
Near Extensions and Alignment of Data in R¯n demonstrates a range of hitherto unknown connections between current research problems in engineering, mathematics, and data science, exploring the mathematical richness of near Whitney Extension Problems, and presenting a new nexus of applied, pure and computational harmonic analysis, approximation theory, data science, and real algebraic geometry. For example, the book uncovers connections between near Whitney Extension Problems and the problem of alignment of data in Euclidean space, an area of considerable interest in computer vision.
Written by a highly qualified author, Near Extensions and Alignment of Data in R¯n includes information on:
* Areas of mathematics and statistics, such as harmonic analysis, functional analysis, and approximation theory, that have driven significant advances in the field
* Development of algorithms to enable the processing and analysis of huge amounts of data and data sets
* Why and how the mathematical underpinning of many current data science tools needs to be better developed to be useful
* New insights, potential tools, and mathematical techniques to solve problems in Whitney extensions, signal processing, shortest paths, clustering, computer vision, optimal transport, manifold learning, minimal energy, and equidistribution
Providing comprehensive coverage of several subjects, Near Extensions and Alignment of Data in R¯n is an essential resource for mathematicians, applied mathematicians, and engineers working on problems related to data science, signal processing, computer vision, manifold learning, and optimal transport.
More details
Other editions
Additional editions
Person
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.
Content
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 e-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
> d 25
> d 25
> 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 (¿, t, K) 51
7.1 Hyperplane; We Meet the Positive Constant ¿ 51
7.2 "Well Separated"; We Meet the Positive Constant t 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: (e, d)-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 e-distortions: Near Reflections 59
9.1 Theorem 9.14 59
9.2 Proof of Theorem 9.14 59
10 e-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
> 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
1
Variants 1-2
In this chapter, we introduce the classical Whitney extension problem. Thereafter, we introduce the near distorted Whitney extension problem and two variants of it. The first, via a purely harmonic analysis problem and the second, translated into a problem related to non-rigid alignment and interpolation of data in . We discuss the Procrustes rigid alignment problem.
1.1 The Whitney Extension Problem
Given a real valued function on an arbitrary compact set in , the classical Whitney extension problem asks how can one decide whether extends to a function in , the space of real valued functions on whose derivatives of order are continuous and bounded? Whitney [114, 115] first studied this problem in 1934. He solved the real line case () and proved the classic Whitney extension theorem. See [64, 63] and the references cited therein for an interesting account of this problem.
1.2 Variants (1-2) [39, 40]
Problems (1-2) are examples of Variants (1-2).
Problem 1. Let us be given a positive constant small enough depending on . Does there exist a positive constant small enough depending on so that the following holds? Given two sets of distinct points in , and . Suppose for every ,
(1.1)- (1) Does there exist a -distortion which obeys ?
- (2) Is it possible that at the same time agrees with Euclidean motions as well?
- (3) Can one say something about how are related?
Problem 2. Let us be given a positive constant small enough depending on . Does there exist a positive constant small enough depending on so that the following holds? Given two sets of distinct labeled points in , and . Suppose for every , (1.1) holds.
- (1) Is it possible to find a Euclidean motion which obeys is close to for every . Here close depends on and the points and is measured in the Euclidean norm.
- (2) Can one say something about how are related?
Remark 1. A central remark, at this juncture, is needed moving forward. Problem 1 and Problem 2 are fundamentally different in the sense that Problem 1 is a problem dealing with the existence of extensions. Problem 2 does not ask for an extension. It asks for a Euclidean motion only. This fact translates itself in many ways, for example in how the constants relate to each other.
In the case of isometry, Remark 1 is far less subtle: indeed, the following result is well-known, see for example [112].
Let and be two collections of distinct points in . Suppose that the pairwise distances between the points are equal, that is, the two sets of points are isometric. That is
Then, there exists a Euclidean motion, with
1.3 Variant 2
In this section, we provide some perspective on Variant 2. We briefly discuss the interpolation problem in the sense of manifold learning in Chapter 4.
1.4 Visual Object Recognition and an Equivalence Problem in
Visual object recognition is the ability to perceive properties (such as shape, color and texture) of a visual object in and to apply semantic attributes to it (such as identifying the visual object). This process includes the understanding of the visual object's use, previous experience with the visual object, and how it relates to the containing space . Regardless of the object's position or illumination, the ability to effectively identify an object, makes the object a "visual" object.
One significant aspect of visual object recognition is the ability to recognize a visual object across varying viewing conditions. These varying conditions include object orientation, lighting, object variability, for example, size, color, and other within-category differences to name just a few. Visual object recognition includes viewpoint-invariant, viewpoint-dependent and multiple view theories to name just a few examples. Visual information gained from an object is often divided into simple geometric components, then matched with the most similar visual object representation that is stored in its memory to provide the object's identification. See the following references and the many cited therein [1, 2, 4-6, 19, 39-42, 59-62, 66, 67, 69, 75, 82, 85-88, 91-93, 100, 101, 107, 111, 118, 120].
With this in mind, we define what we mean by an equivalence problem in . Imagine we are given two visual objects and in . An equivalence and symmetry function : , when well defined, is an element of a group. See [98].
Some examples of vision maps are:
- Affine functions: a function is an affine function if there exists a linear transformation and so that for every , . Affine functions preserve area (volume) ratios. If is invertible (i.e., is then invertible affine), then is either proper or improper. If is not invertible, the function is neither proper nor improper.
- Euclidean motions.
- Reflections: a reflection is an isometry with a hyperplane as a set of fixed points.
- Similarity functions: a Euclidean motion plus a scaling. Similarity functions preserve length ratios.
- Projective motions, with
-
Camera rotations, projective orthogonal transformation:
. - Motion tracking (video group). .
- Here, in (e-g), are certain real constants. See for example [98].
1.5 Procrustes: The Rigid Alignment Problem
The recent advances in = data acquisition and the increasing interest in augmented and virtual reality have led to an explosion of volumetric data, as exemplified by point clouds. Point cloud data is prevalent in numerous applications, including robotics, autonomous driving, medical imaging, neuroscience, social science and computer graphics. In many of these applications, the captured point clouds correspond to noisy observations of an object/scene undergoing different deformations. One of the core challenges in these applications is to perform point cloud registration, which refers to finding a transformation that aligns or partially aligns the source and target point sets. At a high level, any point cloud registration algorithm must solve two problems: 1) finding accurate correspondences between the points in the source and target point clouds (implicitly or explicitly), and 2) modeling the deformation to match corresponding source and target points. The existing methods then propose different correspondence estimation algorithms and/or propose novel deformation modeling approaches.
The registration/deformation map (i.e., the transformation) could be rigid, or non-rigid. Most of the existing works in the literature have focused on rigid registration of point clouds, as it is a more prevalent problem in classic computer vision tasks like simultaneous localization and mapping (SLAM). The core innovations in these approaches are often with regards to finding the right correspondences between the points. For instance, the classic iterative closest point (ICP) algorithm relies on nearest-neighbor correspondences as measured via the Euclidean distance between points. This section deals with rigid matching. See [1]. The best way to understand the rigid alignment problem is via Procrustes alignment. The classical rigid Procrustes problem is to find a rigid motion that best aligns two given point-sets in the least-squares sense. More precisely, given two sets of distinct points in , say and . The rigid Procrustes problem is the optimization problem
where is the norm. Here, we recall that is the orthogonal group of orthogonal matrices. The alignment is label-wise. Unlabeled problems are challenging, given it is often unclear which point to map to which. See for example our work in Chapter 21.
The rigid Procrustes optimization problem (See Figures 1.1-1.2), has a closed form solution obtained by applying a singular value decomposition...
