Fitting a $C^m$-smooth function to data, III

Charles Fefferman

doi:10.4007/annals.2009.170.427

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$.

Show/hide bibliography for this article

[Bierstone] $Go to document$ 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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ C. Fefferman, "A generalized sharp Whitney theorem for jets," Rev. Mat. Iberoamericana, vol. 21, iss. 2, pp. 577-688, 2005.

Show bibtex

@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] $Go to document$ C. Fefferman, "Interpolation and extrapolation of smooth functions by linear operators," Rev. Mat. Iberoamericana, vol. 21, iss. 1, pp. 313-348, 2005.

Show bibtex

@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] $Go to document$ C. Fefferman and B. Klartag, "Fitting a $C^m$-smooth function to data, I," Ann. of Math., vol. 169, pp. 315-346, 2009.

Show bibtex

@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] $Go to document$ C. Fefferman and B. Klartag, "Fitting a $C^m$-smooth function to data, II," Rev. Mat. Iberoamericana, vol. 25, pp. 49-273, 2009.

Show bibtex

@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] $Go to document$ C. L. Fefferman, "A sharp form of Whitney’s extension theorem," Ann. of Math., vol. 161, iss. 1, pp. 509-577, 2005.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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.

Show bibtex

@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] $Go to document$ 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.

Show bibtex

@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] $Go to document$ J. von Neumann, "First draft of a report on the EDVAC," IEEE Ann. Hist. Comput., vol. 15, iss. 4, pp. 27-75, 1993.

Show bibtex

@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}, }

Fitting a $C^m$-smooth function to data, III

Abstract

Authors