American Institute of Mathematical Sciences

Advanced
January  2021, 41(1): 169-199. doi: 10.3934/dcds.2020296

Function approximation via the subsampled Poincaré inequality

Yifan Chen and  Thomas Y. Hou ,

Applied and Computational Mathematics, Caltech, 91106

* Corresponding author: Thomas Y. Hou

Received  December 2019 Revised  June 2020 Published  August 2020

Fund Project: The research was in part supported by NSF Grants DMS-1912654 and DMS-1907977. Y. Chen is supported by the Kortschak Scholars Program

Function approximation and recovery via some sampled data have long been studied in a wide array of applied mathematics and statistics fields. Analytic tools, such as the Poincaré inequality, have been handy for estimating the approximation errors in different scales. The purpose of this paper is to study a generalized Poincaré inequality, where the measurement function is of subsampled type, with a small but non-zero lengthscale that will be made precise. Our analysis identifies this inequality as a basic tool for function recovery problems. We discuss and demonstrate the optimality of the inequality concerning the subsampled lengthscale, connecting it to existing results in the literature. In application to function approximation problems, the approximation accuracy using different basis functions and under different regularity assumptions is established by using the subsampled Poincaré inequality. We observe that the error bound blows up as the subsampled lengthscale approaches zero, due to the fact that the underlying function is not regular enough to have well-defined pointwise values. A weighted version of the Poincaré inequality is proposed to address this problem; its optimality is also discussed.

Keywords: Poincaré inequality, subsampled data, function approximation and recovery, degeneracy, weighted inequality.
Mathematics Subject Classification: Primary: 35A23, 41A44; Secondary: 65D05, 65D07, 62G05.
Citation: Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
References:
[1]

R. A. Adams, Sobolev Spaces, Academic Press, New York-London, 1975.  Google Scholar

[2]

A. E. Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright and M. I. Jordan, Asymptotic behavior of $l_p$-based laplacian regularization in semi-supervised learning., Conference on Learning Theory, (2016), 879–906. Google Scholar

[3]

G. Alessandrini, A. Morassi and E. Rosset, The linear constraints in poincaré and korn type inequalities, Forum Mathematicum, 20 (2008), 557-569.  doi: 10.1515/FORUM.2008.028.  Google Scholar

[4]

J. Calder, Consistency of lipschitz learning with infinite unlabeled data and finite labeled data, SIAM Journal on Mathematics of Data Science, 1 (2019), 780-812.  doi: 10.1137/18M1199241.  Google Scholar

[5]

J. Calder and D. Slepčev, Properly-weighted graph Laplacian for semi-supervised learning, Applied Mathematics & Optimization, 2019. doi: 10.1007/s00245-019-09637-3.  Google Scholar

[6]

Y. Chen and T. Y. Hou, Multiscale elliptic PDEs upscaling and function approximation via subsampled data, preprint, 2020. Google Scholar

[7]

P. Clément, Approximation by finite element functions using local regularization, Revue Française D'automatique, Informatique, Recherche Opérationnelle. Analyse numérique, 9 (1975), 77–84. Google Scholar

[8]

J. Duchon, Splines minimizing rotation-invariant semi-norms in sobolev spaces, Constructive theory of functions of several variables, 571 (1977), 85-100.   Google Scholar

[9]

L. C. Evans, Partial Differential Equations, Graduate studies in mathematics, American Mathematical Society, 2010. doi: 10.1090/gsm/019.  Google Scholar

[10]

D. Gilbarg and N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, 2015.  Google Scholar

[11]

R. L. Harder and R. N. Desmarais, Interpolation using surface splines, Journal of aircraft, 9 (1972), 189-191.  doi: 10.2514/3.44330.  Google Scholar

[12]

T. Y. Hou and P. Zhang, Sparse operator compression of higher-order elliptic operators with rough coefficients, Research in the Mathematical Sciences, 4 (2017), No. 24, 49 pp. doi: 10.1186/s40687-017-0113-1.  Google Scholar

[13]

R. Kyng, A. Rao, S. Sachdeva and D. A. Spielman, Algorithms for Lipschitz learning on graphs, Conference on Learning Theory, (2015), 1190–1223. Google Scholar

[14]

M. Ledoux, Poincaré inequalities in probability and geometric analysis, Available from: https://perso.math.univ-toulouse.fr/ledoux/files/2016/05/Poincare100wpause.pdf Google Scholar

[15]

G. Leoni, A First Course in Sobolev Spaces, Graduate Studies in Mathematics, American Mathematical Society, 2009. doi: 10.1090/gsm/105.  Google Scholar

[16]

A. Målqvist and D. Peterseim, Localization of elliptic multiscale problems, Mathematics of Computation, 83 (2014), 2583-2603.  doi: 10.1090/S0025-5718-2014-02868-8.  Google Scholar

[17]

N. G. Meyers, Integral inequalities of poincaré and wirtinger type, Archive for Rational Mechanics and Analysis, 68 (1978), 113-120.  doi: 10.1007/BF00281405.  Google Scholar

[18]

N. G. Meyers and W. P. Ziemer, Integral inequalities of poincaré and wirtinger type for bv functions, American Journal of Mathematics, 99 (1977), 1345-1360.  doi: 10.2307/2374028.  Google Scholar

[19]

C. A. Micchelli and T. J. Rivlin, A survey of optimal recovery, Optimal estimation in approximation theory, (1977), 1–54.  Google Scholar

[20]

B. Nadler, N. Srebro and X. Zhou, Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data, Advances in neural information processing systems, (2009), 1330–1338. Google Scholar

[21]

H. Owhadi, Multigrid with Rough Coefficients and Multiresolution, Operator Decomposition from Hierarchical Information Games, SIAM Review, 59 (2017), 99-149.  doi: 10.1137/15M1013894.  Google Scholar

[22] H. Owhadi and C. Scovel, Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization: From a Game Theoretic Approach to Numerical Approximation and Algorithm Design, Cambridge University Press, 2019.   Google Scholar
[23]

H. Owhadi, L. Zhang and L. Berlyand, Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization, ESAIM: Mathematical Modelling and Numerical Analysis, 48 (2014), 517-552.  doi: 10.1051/m2an/2013118.  Google Scholar

[24]

H. Poincaré, Sur les Equations aux Dérivées Partielles de la Physique Mathématique, American Journal of Mathematics, 12 (1890), 211-294.  doi: 10.2307/2369620.  Google Scholar

[25]

D. Ruiz, A note on the uniformity of the constant in the poincaré inequality, preprint, arXiv: 1208.6045. Google Scholar

[26]

Z. Shi, S. Osher and W. Zhu, Weighted nonlocal laplacian on interpolation from sparse data, Journal of Scientific Computing, 73 (2017), 1164-1177.  doi: 10.1007/s10915-017-0421-z.  Google Scholar

[27]

D. Slepčev and M. Thorpe., Analysis of p-laplacian regularization in semisupervised learning, SIAM Journal on Mathematical Analysis, 51 (2019), 2085-2120.  doi: 10.1137/17M115222X.  Google Scholar

[28]

A. Veeser and R. Verfürth, Poincaré constants for finite element stars, IMA Journal of Numerical Analysis, 32 (2012), 30-47.  doi: 10.1093/imanum/drr011.  Google Scholar

[29]

X. Zhou and M. Belkin, Semi-supervised learning by higher order regularization, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, (2011), 892–900. Google Scholar

[30]

W. P. Ziemer, Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation, Graduate Texts in Mathematics, 120. Springer-Verlag, New York, 1989. doi: 10.1007/978-1-4612-1015-3.  Google Scholar

show all references

References:
[1]

R. A. Adams, Sobolev Spaces, Academic Press, New York-London, 1975.  Google Scholar

[2]

A. E. Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright and M. I. Jordan, Asymptotic behavior of $l_p$-based laplacian regularization in semi-supervised learning., Conference on Learning Theory, (2016), 879–906. Google Scholar

[3]

G. Alessandrini, A. Morassi and E. Rosset, The linear constraints in poincaré and korn type inequalities, Forum Mathematicum, 20 (2008), 557-569.  doi: 10.1515/FORUM.2008.028.  Google Scholar

[4]

J. Calder, Consistency of lipschitz learning with infinite unlabeled data and finite labeled data, SIAM Journal on Mathematics of Data Science, 1 (2019), 780-812.  doi: 10.1137/18M1199241.  Google Scholar

[5]

J. Calder and D. Slepčev, Properly-weighted graph Laplacian for semi-supervised learning, Applied Mathematics & Optimization, 2019. doi: 10.1007/s00245-019-09637-3.  Google Scholar

[6]

Y. Chen and T. Y. Hou, Multiscale elliptic PDEs upscaling and function approximation via subsampled data, preprint, 2020. Google Scholar

[7]

P. Clément, Approximation by finite element functions using local regularization, Revue Française D'automatique, Informatique, Recherche Opérationnelle. Analyse numérique, 9 (1975), 77–84. Google Scholar

[8]

J. Duchon, Splines minimizing rotation-invariant semi-norms in sobolev spaces, Constructive theory of functions of several variables, 571 (1977), 85-100.   Google Scholar

[9]

L. C. Evans, Partial Differential Equations, Graduate studies in mathematics, American Mathematical Society, 2010. doi: 10.1090/gsm/019.  Google Scholar

[10]

D. Gilbarg and N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, 2015.  Google Scholar

[11]

R. L. Harder and R. N. Desmarais, Interpolation using surface splines, Journal of aircraft, 9 (1972), 189-191.  doi: 10.2514/3.44330.  Google Scholar

[12]

T. Y. Hou and P. Zhang, Sparse operator compression of higher-order elliptic operators with rough coefficients, Research in the Mathematical Sciences, 4 (2017), No. 24, 49 pp. doi: 10.1186/s40687-017-0113-1.  Google Scholar

[13]

R. Kyng, A. Rao, S. Sachdeva and D. A. Spielman, Algorithms for Lipschitz learning on graphs, Conference on Learning Theory, (2015), 1190–1223. Google Scholar

[14]

M. Ledoux, Poincaré inequalities in probability and geometric analysis, Available from: https://perso.math.univ-toulouse.fr/ledoux/files/2016/05/Poincare100wpause.pdf Google Scholar

[15]

G. Leoni, A First Course in Sobolev Spaces, Graduate Studies in Mathematics, American Mathematical Society, 2009. doi: 10.1090/gsm/105.  Google Scholar

[16]

A. Målqvist and D. Peterseim, Localization of elliptic multiscale problems, Mathematics of Computation, 83 (2014), 2583-2603.  doi: 10.1090/S0025-5718-2014-02868-8.  Google Scholar

[17]

N. G. Meyers, Integral inequalities of poincaré and wirtinger type, Archive for Rational Mechanics and Analysis, 68 (1978), 113-120.  doi: 10.1007/BF00281405.  Google Scholar

[18]

N. G. Meyers and W. P. Ziemer, Integral inequalities of poincaré and wirtinger type for bv functions, American Journal of Mathematics, 99 (1977), 1345-1360.  doi: 10.2307/2374028.  Google Scholar

[19]

C. A. Micchelli and T. J. Rivlin, A survey of optimal recovery, Optimal estimation in approximation theory, (1977), 1–54.  Google Scholar

[20]

B. Nadler, N. Srebro and X. Zhou, Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data, Advances in neural information processing systems, (2009), 1330–1338. Google Scholar

[21]

H. Owhadi, Multigrid with Rough Coefficients and Multiresolution, Operator Decomposition from Hierarchical Information Games, SIAM Review, 59 (2017), 99-149.  doi: 10.1137/15M1013894.  Google Scholar

[22] H. Owhadi and C. Scovel, Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization: From a Game Theoretic Approach to Numerical Approximation and Algorithm Design, Cambridge University Press, 2019.   Google Scholar
[23]

H. Owhadi, L. Zhang and L. Berlyand, Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization, ESAIM: Mathematical Modelling and Numerical Analysis, 48 (2014), 517-552.  doi: 10.1051/m2an/2013118.  Google Scholar

[24]

H. Poincaré, Sur les Equations aux Dérivées Partielles de la Physique Mathématique, American Journal of Mathematics, 12 (1890), 211-294.  doi: 10.2307/2369620.  Google Scholar

[25]

D. Ruiz, A note on the uniformity of the constant in the poincaré inequality, preprint, arXiv: 1208.6045. Google Scholar

[26]

Z. Shi, S. Osher and W. Zhu, Weighted nonlocal laplacian on interpolation from sparse data, Journal of Scientific Computing, 73 (2017), 1164-1177.  doi: 10.1007/s10915-017-0421-z.  Google Scholar

[27]

D. Slepčev and M. Thorpe., Analysis of p-laplacian regularization in semisupervised learning, SIAM Journal on Mathematical Analysis, 51 (2019), 2085-2120.  doi: 10.1137/17M115222X.  Google Scholar

[28]

A. Veeser and R. Verfürth, Poincaré constants for finite element stars, IMA Journal of Numerical Analysis, 32 (2012), 30-47.  doi: 10.1093/imanum/drr011.  Google Scholar

[29]

X. Zhou and M. Belkin, Semi-supervised learning by higher order regularization, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, (2011), 892–900. Google Scholar

[30]

W. P. Ziemer, Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation, Graduate Texts in Mathematics, 120. Springer-Verlag, New York, 1989. doi: 10.1007/978-1-4612-1015-3.  Google Scholar

Figure 1.  Domain $ \Omega = [0, 1]^2 $; the local cube $ \omega_i^{H} $ and the subsampled cube $ \omega_i^{h, H} $
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Yangjian Sun, Changjian Liu. The Poincaré bifurcation of a SD oscillator. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1565-1577. doi: 10.3934/dcdsb.2020173
[2]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[3]

Indranil Chowdhury, Gyula Csató, Prosenjit Roy, Firoj Sk. Study of fractional Poincaré inequalities on unbounded domains. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020394
[4]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[5]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389
[6]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[7]

Dmitry Dolgopyat. The work of Sébastien Gouëzel on limit theorems and on weighted Banach spaces. Journal of Modern Dynamics, 2020, 16: 351-371. doi: 10.3934/jmd.2020014
[8]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[9]

Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146
[10]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[11]

Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048
[12]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[13]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[14]

Anna Canale, Francesco Pappalardo, Ciro Tarantino. Weighted multipolar Hardy inequalities and evolution problems with Kolmogorov operators perturbed by singular potentials. Communications on Pure & Applied Analysis, 2021, 20 (1) : 405-425. doi: 10.3934/cpaa.2020274
[15]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107
[16]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[17]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026
[18]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322
[19]

Anna Anop, Robert Denk, Aleksandr Murach. Elliptic problems with rough boundary data in generalized Sobolev spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020286
[20]

Haruki Umakoshi. A semilinear heat equation with initial data in negative Sobolev spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 745-767. doi: 10.3934/dcdss.2020365

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (100)
  • HTML views (295)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences