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

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

Authors

Charles Fefferman

Princeton University
Department of Mathematics
Princeton, NJ 08544
United States