Abstract
Fix $m, n\geq 1$. Given an $N$-point set $E \subset {\mathbb R}^n$, we exhibit a list of $O(N)$ subsets $S_1,S_2,\ldots,S_L\subset E$, each containing $O(1)$ points, such that the following holds: Let $f: E\to {\mathbb R}^n$. Suppose that, for each $\ell=1,\ldots,L$, there exists $F_\ell \in C^m(\mathbb R^n)$ with norm $\le 1$, agreeing with $f$ on $S_\ell$. Then there exists $F\in C^m(\mathbb R^n)$, with norm $O(1)$, agreeing with $f$ on $E$.
We give an application to the problem of discarding outliers from the set $E$.
-
[Bierstone]
E. Bierstone and P. D. Milman, "$\cal C^m$-norms on finite sets and $\cal C^m$ extension criteria," Duke Math. J., vol. 137, iss. 1, pp. 1-18, 2007.
@article {Bierstone, MRKEY = {2309142},
AUTHOR = {Bierstone, Edward and Milman, Pierre D.},
TITLE = {{$\cal C\sp m$}-norms on finite sets and {$\cal C\sp m$} extension criteria},
JOURNAL = {Duke Math. J.},
FJOURNAL = {Duke Mathematical Journal},
VOLUME = {137},
YEAR = {2007},
NUMBER = {1},
PAGES = {1--18},
ISSN = {0012-7094},
CODEN = {DUMJAO},
MRCLASS = {58C25 (26B05 26B35 58A20)},
MRNUMBER = {2008f:58009},
DOI = {10.1215/S0012-7094-07-13711-6},
MRREVIEWER = {Nahum Zobin},
} -
[Brudnyi]
Y. Brudnyi and P. Shvartsman, "Generalizations of Whitney’s extension theorem," Internat. Math. Res. Notices, vol. 1994 no. 3, iss. 3, pp. 129-139, 1994.
@article {Brudnyi, MRKEY = {1266108},
AUTHOR = {Brudnyi, Yuri and Shvartsman, Pavel},
TITLE = {Generalizations of {W}hitney's extension theorem},
JOURNAL = {Internat. Math. Res. Notices},
FJOURNAL = {International Mathematics Research Notices},
YEAR = {1994},
VOLUME = {1994 no.~3},
NUMBER = {3},
PAGES = {129--139},
ISSN = {1073-7928},
MRCLASS = {58C25 (41A10 46E35)},
MRNUMBER = {95c:58018},
DOI = {10.1155/S1073792894000140},
ZBLNUMBER = {0845.57022},
MRREVIEWER = {H. Wallin},
} -
[Callahan]
P. B. Callahan and R. S. Kosaraju, "A decomposition of multidimensional point sets with applications to $k$-nearest-neighbors and $n$-body potential fields," J. Assoc. Comput. Mach., vol. 42, iss. 1, pp. 67-90, 1995.
@article {Callahan, MRKEY = {1370371},
AUTHOR = {Callahan, Paul B. and Kosaraju, S. Rao},
TITLE = {A decomposition of multidimensional point sets with applications to {$k$}-nearest-neighbors and {$n$}-body potential fields},
JOURNAL = {J. Assoc. Comput. Mach.},
FJOURNAL = {Journal of the Association for Computing Machinery},
VOLUME = {42},
YEAR = {1995},
NUMBER = {1},
PAGES = {67--90},
ISSN = {0004-5411},
CODEN = {JACOAH},
MRCLASS = {68Q20 (68U05)},
MRNUMBER = {96i:68033},
DOI = {10.1145/200836.200853},
ZBLNUMBER = {0886.68078},
} -
[Fefferman2005a]
C. Fefferman, "A generalized sharp Whitney theorem for jets," Rev. Mat. Iberoamericana, vol. 21, iss. 2, pp. 577-688, 2005.
@article {Fefferman2005a, MRKEY = {2174917},
AUTHOR = {Fefferman, Charles},
TITLE = {A generalized sharp {W}hitney theorem for jets},
JOURNAL = {Rev. Mat. Iberoamericana},
FJOURNAL = {Revista Matemática Iberoamericana},
VOLUME = {21},
YEAR = {2005},
NUMBER = {2},
PAGES = {577--688},
ISSN = {0213-2230},
MRCLASS = {58C25 (26A51 26B25 49K24 58A20)},
MRNUMBER = {2007a:58009},
URL = {http://projecteuclid.org/getRecord?id=euclid.rmi/1123766807},
ZBLNUMBER = {1102.58004},
MRREVIEWER = {Pavel A. Shvartsman},
} -
[Fefferman2005b]
C. Fefferman, "Interpolation and extrapolation of smooth functions by linear operators," Rev. Mat. Iberoamericana, vol. 21, iss. 1, pp. 313-348, 2005.
@article {Fefferman2005b, MRKEY = {2155023},
AUTHOR = {Fefferman, Charles},
TITLE = {Interpolation and extrapolation of smooth functions by linear operators},
JOURNAL = {Rev. Mat. Iberoamericana},
FJOURNAL = {Revista Matemática Iberoamericana},
VOLUME = {21},
YEAR = {2005},
NUMBER = {1},
PAGES = {313--348},
ISSN = {0213-2230},
MRCLASS = {58C25 (30E05 41A65 52A35)},
MRNUMBER = {2006h:58009},
URL = {http://projecteuclid.org/getRecord?id=euclid.rmi/1114176236},
ZBLNUMBER = {1084.58003},
MRREVIEWER = {Yu. A. Brudny{\u\i}},
} -
[Fefferman2009a]
C. Fefferman and B. Klartag, "Fitting a $C^m$-smooth function to data, I," Ann. of Math., vol. 169, pp. 315-346, 2009.
@article{Fefferman2009a,
author = {C.~Fefferman and B.~Klartag},
title = {Fitting a $C^m$-smooth function to data, {I}},
journal = {Ann. of Math.},
VOLUME = {169},
year = {2009},
pages = {315--346},
url = {http://pjm.math.berkeley.edu/annals/2009/169-1/p08.xhtml},
} -
[Fefferman2009b]
C. Fefferman and B. Klartag, "Fitting a $C^m$-smooth function to data, II," Rev. Mat. Iberoamericana, vol. 25, pp. 49-273, 2009.
@article{Fefferman2009b,
author = {C.~Fefferman and B.~Klartag},
title = {Fitting a $C^m$-smooth function to data, {II}},
journal = {Rev. Mat. Iberoamericana},
YEAR = {2009},
pages = {49--273},
volume = {25},
url = {http://projecteuclid.org/euclid.rmi/1236864106},
} -
[Fefferman2005c]
C. L. Fefferman, "A sharp form of Whitney’s extension theorem," Ann. of Math., vol. 161, iss. 1, pp. 509-577, 2005.
@article {Fefferman2005c, MRKEY = {2150391},
AUTHOR = {Fefferman, Charles L.},
TITLE = {A sharp form of {W}hitney's extension theorem},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {161},
YEAR = {2005},
NUMBER = {1},
PAGES = {509--577},
ISSN = {0003-486X},
CODEN = {ANMAAH},
MRCLASS = {58C25 (26B35)},
MRNUMBER = {2006h:58008},
ZBLNUMBER = {1102.58005},
MRREVIEWER = {M. Laczkovich},
DOI = {10.4007/annals.2005.161.509},
} -
[HarPeled]
S. Har-Peled and M. Mendel, "Fast construction of nets in low-dimensional metrics and their applications," SIAM J. Comput., vol. 35, iss. 5, pp. 1148-1184, 2006.
@article {HarPeled, MRKEY = {2217141},
AUTHOR = {Har-Peled, Sariel and Mendel, Manor},
TITLE = {Fast construction of nets in low-dimensional metrics and their applications},
JOURNAL = {{\rm SIAM} J. Comput.},
FJOURNAL = {SIAM Journal on Computing},
VOLUME = {35},
YEAR = {2006},
NUMBER = {5},
PAGES = {1148--1184},
ISSN = {0097-5397},
MRCLASS = {68W25 (52C17 68P05 68W40)},
MRNUMBER = {2007e:68071},
DOI = {10.1137/S0097539704446281},
ZBLNUMBER = {1100.68014},
MRREVIEWER = {Tamas Lengyel},
} -
[Malgrange] B. Malgrange, Ideals of Differentiable Functions, Bombay: Tata Institute of Fundamental Research, 1967.
@book {Malgrange, MRKEY = {0212575},
AUTHOR = {Malgrange, B.},
TITLE = {Ideals of Differentiable Functions},
SERIES = {Tata Institute of Fundamental Research Studies in Mathematics},
NUMBER = {3},
PUBLISHER = {Tata Institute of Fundamental Research},
ADDRESS = {Bombay},
YEAR = {1967},
PAGES = {vii+106},
MRCLASS = {46.55 (13.93)},
MRNUMBER = {35 \#3446},
MRREVIEWER = {M. F. Atiyah},
} -
[Shvartsman]
P. Shvartsman, "The Whitney extension problem and Lipschitz selections of set-valued mappings in jet-spaces," Trans. Amer. Math. Soc., vol. 360, iss. 10, pp. 5529-5550, 2008.
@article {Shvartsman, MRKEY = {2415084},
AUTHOR = {Shvartsman, Pavel},
TITLE = {The {W}hitney extension problem and {L}ipschitz selections of set-valued mappings in jet-spaces},
JOURNAL = {Trans. Amer. Math. Soc.},
FJOURNAL = {Transactions of the American Mathematical Society},
VOLUME = {360},
YEAR = {2008},
NUMBER = {10},
PAGES = {5529--5550},
ISSN = {0002-9947},
CODEN = {TAMTAM},
MRCLASS = {46Exx (52A35 54C60 54C65)},
MRNUMBER = {2415084},
DOI = {10.1090/S0002-9947-08-04469-3},
} -
[Neumann]
J. von Neumann, "First draft of a report on the EDVAC," IEEE Ann. Hist. Comput., vol. 15, iss. 4, pp. 27-75, 1993.
@article {Neumann, MRKEY = {1241101},
AUTHOR = {von Neumann, John},
TITLE = {First draft of a report on the {EDVAC}},
INVNOTE = {Edited and with an introduction by Michael D. Godfrey},
JOURNAL = {{\rm IEEE} Ann. Hist. Comput.},
FJOURNAL = {IEEE Annals of the History of Computing},
VOLUME = {15},
YEAR = {1993},
NUMBER = {4},
PAGES = {27--75},
ISSN = {1058-6180},
MRCLASS = {01A60 (68-03)},
MRNUMBER = {94j:01007},
DOI = {10.1109/85.238389},
ZBLNUMBER = {0944.01510},
MRREVIEWER = {Albert C. Lewis},
}