Efficient Algorithms for Approximate Smooth Selection
- PDF / 974,429 Bytes
- 71 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 281 Views
Efficient Algorithms for Approximate Smooth Selection Charles Fefferman1 · Bernat Guillén Pegueroles1 Received: 8 May 2019 © Mathematica Josephina, Inc. 2019
Abstract In this paper, we provide efficient algorithms for approximate C m (Rn , R D )−selection. In particular, given a set E, a constant M0 > 0, and convex sets K (x) ⊂ R D for x ∈ E, we show that an algorithm running in C(τ )N log N steps is able to solve the smooth selection problem of selecting a point y ∈ (1 + τ )K (x) for x ∈ E for an appropriate dilation of K (x), (1 + τ )K (x), and guaranteeing that a function interpolating the points (x, y) will be C m (Rn , R D ) with norm bounded by C M. Keywords Smooth selection · Approximate algorithms · Efficient algorithms · Partition of unity Mathematics Subject Classification 46E35
Part I: Introduction and Notation I.1 Introduction This paper continues a study of extension and approximation of functions, going back to Whitney [1–3], with important contributions from E. Bierstone, Y. Brudnyi, C. Fefferman, G. Glaeser, A. Israel, B. Klartag, E. Le Gruyer, G. Luli, P. Milman, W. Pawłucki, P. Shvartsman and N. Zobin. See [4–25]. The motivation of these problems is to reconstruct functions from data. In particular, the work of [13,14] shows how to interpolate a function given precise data points.
In fond memory of Elias Stein. Charles Fefferman: Supported by AFOSR FA9550-18-1-069, NSF DMS-1700180, BSF 2014055. Supported by the US-Israel BSF. Bernat Guillén Pegueroles: Supported by Fulbright-Telefónica, AFOSR FA9550-18-1-069, NSF.
B 1
Bernat Guillén Pegueroles [email protected] Princeton University, Princeton, NJ, USA
123
C. Fefferman, B. Guillén Pegueroles
Fig. 1 A simple C m selection problem. The set E consists of the dots on the x−axis marked by a triangle. Above each x ∈ E is an interval K (x). The function F shown here satisfies F(x) ∈ K (x) for all x ∈ E
However, in real applications the data is measured with error. A “finiteness” theorem underlies the results of [13,14] for interpolation of perfectly specified data. The paper [12] proves a corresponding finiteness theorem for interpolation of data measured with error. However, the proofs of the main results of [12] are nonconstructive. The interpolation of data specified with error remains a challenging problem. Fix positive integers m, n, D. We work in C m (Rn , R D ), the space of all F : Rn → D R with all partial derivatives of order up to m continuous and bounded on Rn . We use the norm (I.1.1) F = supx∈Rn max|α|≤m |∂ α F(x)| (or an equivalent one) which is finite. We write c, C, C , etc. to denote constants depending only on m, n, D. These symbols may denote different constants in different occurrences. Let E ⊂ Rn be a finite set with N elements. For each x ∈ E, suppose we are given a bounded convex set K (x) ⊂ R D . A C m selection of K := (K (x))x∈E is a function F ∈ C m (Rn , R D ) such that F(x) ∈ K (x) for all x ∈ E. We want to compute a C m selection F whose norm F is as small as possible up to a factor of C. Such prob
Data Loading...
