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

Steven B. Damelin

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 204

Veröffentlichungsjahr: 2023

Beschreibung

Near Extensions and Alignment of Data in R¯n 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.

Leseprobe

Near Extensions and Alignment of Data in ℝn

Whitney extensions of near isometries, shortest paths, equidistribution, clustering and non-rigid alignment of data in Euclidean space

Steven B. Damelin

Ann Arbor, MI, USA

This edition first published 2024

© 2024 John Wiley & Sons Ltd

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Steven B. Damelin to be identified as the author of this work has been asserted in accordance with law.

Registered Offices

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging-in-Publication Data

Names: Damelin, Steven B., author.

Title: Near extensions and alignment of data in ℝn : Whitney extensions of near isometries, shortest paths, equidistribution, clustering and non-rigid alignment of data in Euclidean space / Steven B. Damelin.

Description: Hoboken, NJ : John Wiley & Johns, 2024. | Includes bibliographical references and index.

Identifiers: LCCN 2023032013 | ISBN 9781394196777 (hardback) | ISBN 9781394196791 (adobe pdf) | ISBN 9781394196807 (epub) | ISBN 9781394196814 (ebook)

Subjects: LCSH: Mathematical analysis | Geometry, Analytic. | Rigidity (Geometry) | Nomography (Mathematics) | Euclidean algorithm. | Isometrics (Mathematics)

Classification: LCC QA300 .D325 2024 | DDC 516.3–dc23/eng/20231002

LC record available at https://lccn.loc.gov/2023032013

Cover Design: Wiley

Cover Image: Courtesy of the Author

Set in 9.5/12.5pt STIXTwoText by Integra Software Services Pvt. Ltd, Pondicherry, India

To my family

Preface

This monograph, for fixed integers and , provides a modern treatment of Whitney extensions of near isometries in , non-rigid alignment of data in , interpolation by near isometries in , continuum limits of shortest paths in with several intersecting topics in pure and applied harmonic analysis and data science for example, approximation of near distortions by elements of the orthogonal group using the space of functions of bounded mean oscillation (BMO), clustering of data in , equidistribution and discrepancy via minimal energy and finite field techniques, tensor methods in Whitney theory, approximation theory in algebraic geometry, quantum lattices and covers of the special unitary group , techniques for counting linear independent vectors over finite fields and the maximum distance separable (MDS) conjecture.

The monograph is structured as follows. Chapter 1 introduces the near Whitney extension problem. For finite sets of distinct data in with varying geometries, the chapter interprets this extension problem as an interpolation, non-rigid alignment problem of distinct data in and discusses rigid and non-rigid data alignment problems. The monograph, then moves to machinery to analyze the near Whitney extension problem in Chapter 1, from various perspectives for finite sets of distinct points with varying geometries. Chapter 2 introduces the idea of near distorted diffeomorphism extensions which agree with Euclidean motions in . Slow Twists and Slides are introduced as examples of near distorted diffeomorphisms.

Chapter 5 deals with clustering methods of data in and studies continuum limits of shortest paths. Chapter 7 deals with tensor methods, Chapter 8 studies the use of approximation theory for varieties in algebraic geometry and Chapter 9 introduces near reflection theory.

Chapter 10 studies approximation of near distortions by elements of the orthogonal group , using the space of functions of bounded mean oscillation (BMO) and the John Nirenberg inequality.

Chapters 3, 6, 11–12 introduce Gluing techniques, partitions of unity, further Whitney machinery and finite principles.

Chapter 4 deals with manifold learning and the Johnson–Lindenstrauss theorem.

Chapters 13–18 deal with the analysis of the near Whitney extension problem for compact sets in open sets in . This chapter introduces Whitney techniques such as Whitney cubes and regularization. It provides near distortions agreeing with Euclidean motions in .

Chapter 19 deals with equidistribution and studies minimal energy on -dimensional compact sets embedded in via extremal Newtonian like configurations. It studies group invariant discrepancy, finite field discrepancy, combinatorial designs, techniques for counting linear independent vectors over finite fields, and discusses the maximum distance separable (MDS) conjecture.

Chapter 20 deals with quantum lattices and covers of the special unitary group .

Finally Chapter 21 deals with the near unlabeled data alignment problem and the related optimal transport problem.

Acknowledgements

The work in this monograph is joint with many collaborators and I thank them for exciting and fruitful collaborations. In particular, I would like to thank my collaborator Charles Fefferman for the collaborative work in our papers [39–42] (Chapters 2–3, 6–7, 9–18, Sections 5.7, 8.1). It is a pleasure to thank many colleagues who have generously supported me with this project. In particular, I would like to mention John Bennedeto, Tony Bloch, Emmanuel Candese, David Ragozin, Kai Diethelm, Nadav Dym, Keaton Hamm, Alfred Hero, Joe Kileel, Victor Lieberman, Roy Liederman, Doron Lubinsky, Daniel McKenzie, Boaz Nadler, Peter Oliver, Peter Sarnak, Michael Sears, Amit Singer, Sung jin Wang and Michael Werman. I thank the referees for the enormous amount of methodical work they undertook checking everything and for their many generous suggestions to improve the monograph. Finally, I wish to thank all the editorial staff at John Wiley & Sons for their support and to acknowledge their expertise in bringing the memoir to its current form.* Given the enormous literature on some of the topics discussed in this monograph, any relevant omissions in our reference listed are unintentional.

This monograph will be of interest to applied and pure mathematicians, computer scientists and engineers working in algebraic geometry, approximation theory, computer vision, data science, differential geometry, harmonic analysis, applied harmonic analysis, manifold and machine learning, networks, optimal transport, partial differential equations, probability, shortest paths, signal processing and neuroscience. I hope that readers will enjoy the book and will think about the many areas open to investigation detailed within. I hope that this monograph will inspire new research and curiosity.

Steven B. Damelin

Ann Arbor, MI

18 August, 2023

Note

*

Research support from the National Science Foundation, Georgia Southern University, American Mathematical Society, South African Center for High Performance Computing, and Princeton University is thankfully acknowledged.

Overview

Notation: Throughout, and will be fixed positive integers. By , we mean the Euclidean norm on .* A function is an improper Euclidean motion (rigid motion) if there exist and a translation so that for every , . If , then is a proper Euclidean motion. Here, and are respectively the orthogonal and special orthogonal groups. A Euclidean motion can either be proper or improper. We will call a function  :   , a -distortion if there exists small enough depending on so that for every . Note that is non-rigid and distorts distances by factors making it a near isometry (almost preserves distances). Rigid motions are isometries, that is, they are distance preserving and satisfy for every . A function  :    is bi-Lipschitz if there exists a constant (not depending on ) so that uniformly for all , .

All constants depend on the dimension unless stated otherwise. are always positive constants which depend on and possibly other quantities. This will be made clear. are compact subsets of unless stated otherwise. The symbols are used for functions. We will sometimes write for a function , . It will be clear from the context what we mean. The notation for constants, sets, and functions may denote the same or different constant, set and function at any given time. The context will be clear. Before a precise definition, we sometimes, as a convention moving forward, use imprecise words or phrases such as “close”, “local”, “global”, “rough”, “smooth”, and others. We do this deliberately for motivation and easier reading before the reader needs to absorb a precise definition.**

We will sometimes write that a particular compact set (class of compact sets ) has a certain geometry (has certain geometries). We ask the reader to accept such phrases until the exact geometry (geometries) on the given set (given class of sets ) is defined precisely. Geometries refer to one of many different geometries to be defined precisely when needed.

When we speak to a constant being small enough, we mean that is less than a small controlled positive constant. The diameter of a compact set is:  :  and if is a finite set, denotes the cardinality of the set .

Throughout, we often work with special sets and constants. These then have their own designated symbols, for example the set , the constants and so forth. It will be clear what these sets/constants are, when used. The special constants and will always be small enough. We do however remind the reader of this often.

Notes

*

Unless indicated otherwise.

**

The letters are unfortunately commonly used in numbering. It will be clear moving forward if are used for a numbering or a constant.

Structure

A large part of this monograph studies three variants of the following problem (preliminary versions).

1.

Variant (1): Whitney extensions of near isometries on finite subsets of

(preliminary version)

. Let be a finite set of distinct labeled points and a near isometry. ( are called the labels of the points ). Firstly, how to decide if there exists a smooth near isometry .which extends (that is agrees with on ) and agrees with Euclidean motions on . Secondly, how to understand when there exists a Euclidean motion such that is close to measured in the Euclidean norm. (bi-Lipschitz functions will typically not extend unless is close to ).

§

 [

39

,

40

]

2.

Variant (2): Near isometric alignment and interpolation of labeled data in

(preliminary version)

. Let    be a finite set of distinct labeled data

¶

‖

and  :    a near isometry.

Interpolation and alignment: how to decide if there exists a smooth near isometry , so that interpolates and agrees with Euclidean motions on ?

How to understand when there exists a Euclidean motion such that is close to measured in the Euclidean metric [

39

,

40

].

3.

Variant (3): Whitney extensions of smooth near isometries on compacts subsets of open subsets of

(preliminary version)

. Let be open and compact. Let be a smooth near isometry. How to decide if there exists a smooth near isometry which extends from a neighborhood of and agrees with Euclidean motions on  [

41

].

In addition to Variants (1–3) above, the monograph studies the following topics:

a. Continuum limits of shortest paths and clustering of data in  [

70

,

95

].

b. Equidistribution and minimal energy on -dimensional compact sets embedded in via extremal Newtonian-like configurations. Group invariant discrepancy, finite field discrepancy, combinatorial designs, techniques for counting linear independent vectors over finite fields and the maximum distance separable (MDS) conjecture [

28

,

29

,

33

,

43

,

46

,

48

–

51

,

54

,

55

,

109

].

c. Approximation of smooth near distortions by elements of the orthogonal group , using the space of functions of bounded mean oscillation (BMO) and the John Nirenberg inequality [

42

].

d. Quantum lattices and covers of the special unitary group  [

74

].

e. Manifold learning and the Johnson–Lindenstrauss theorem.

f. Unlabeled analogues of variants (1–2) [

26

].

g. The optimal transport problem [

6

].

Notes

§

The points and () are matched label-wise, meaning for example to , to … to .

¶

Except for

Chapter 21

, by points/data we will now always mean labeled points/data.

‖

Variants (1–2) are identical problems. Variant (2) is Variant (1) written in the terminology of data scientists.

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