Figure 1.
Domain $ \Omega = [0, 1]^2 $ ; the local cube $ \omega_i^{H} $ and the subsampled cube $ \omega_i^{h, H} $
-
Previous Article
Stuart-type polar vortices on a rotating sphere
- DCDS Home
- This Issue
-
Next Article
Mathematical analysis of a cloud resolving model including the ice microphysics
January
2021, 41(1): 169-199.
doi: 10.3934/dcds.2020296
Function approximation via the subsampled Poincaré inequality
Applied and Computational Mathematics, Caltech, 91106 |
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 and Continuous Dynamical Systems,
2021, 41
(1)
: 169-199.
doi: 10.3934/dcds.2020296
![]()
References:
| [1] |
R. A. Adams, Sobolev Spaces, Academic Press, New York-London, 1975. |
| [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. |
| [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. |
| [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. |
| [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. |
| [6] |
Y. Chen and T. Y. Hou, Multiscale elliptic PDEs upscaling and function approximation via subsampled data, preprint, 2020. |
| [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. |
| [8] |
J. Duchon,
Splines minimizing rotation-invariant semi-norms in sobolev spaces, Constructive theory of functions of several variables, 571 (1977), 85-100.
|
| [9] |
L. C. Evans, Partial Differential Equations, Graduate studies in mathematics, American Mathematical Society, 2010.
doi: 10.1090/gsm/019. |
| [10] |
D. Gilbarg and N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, 2015. |
| [11] |
R. L. Harder and R. N. Desmarais,
Interpolation using surface splines, Journal of aircraft, 9 (1972), 189-191.
doi: 10.2514/3.44330. |
| [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. |
| [13] |
R. Kyng, A. Rao, S. Sachdeva and D. A. Spielman, Algorithms for Lipschitz learning on graphs, Conference on Learning Theory, (2015), 1190–1223. |
| [14] |
M. Ledoux, Poincaré inequalities in probability and geometric analysis, Available from: https://perso.math.univ-toulouse.fr/ledoux/files/2016/05/Poincare100wpause.pdf |
| [15] |
G. Leoni, A First Course in Sobolev Spaces, Graduate Studies in Mathematics, American Mathematical Society, 2009.
doi: 10.1090/gsm/105. |
| [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. |
| [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. |
| [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. |
| [19] |
C. A. Micchelli and T. J. Rivlin, A survey of optimal recovery, Optimal estimation in approximation theory, (1977), 1–54. |
| [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. |
| [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. |
| [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.
|
| [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. |
| [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. |
| [25] |
D. Ruiz, A note on the uniformity of the constant in the poincaré inequality, preprint, arXiv: 1208.6045. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
show all references
References:
| [1] |
R. A. Adams, Sobolev Spaces, Academic Press, New York-London, 1975. |
| [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. |
| [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. |
| [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. |
| [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. |
| [6] |
Y. Chen and T. Y. Hou, Multiscale elliptic PDEs upscaling and function approximation via subsampled data, preprint, 2020. |
| [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. |
| [8] |
J. Duchon,
Splines minimizing rotation-invariant semi-norms in sobolev spaces, Constructive theory of functions of several variables, 571 (1977), 85-100.
|
| [9] |
L. C. Evans, Partial Differential Equations, Graduate studies in mathematics, American Mathematical Society, 2010.
doi: 10.1090/gsm/019. |
| [10] |
D. Gilbarg and N. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, 2015. |
| [11] |
R. L. Harder and R. N. Desmarais,
Interpolation using surface splines, Journal of aircraft, 9 (1972), 189-191.
doi: 10.2514/3.44330. |
| [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. |
| [13] |
R. Kyng, A. Rao, S. Sachdeva and D. A. Spielman, Algorithms for Lipschitz learning on graphs, Conference on Learning Theory, (2015), 1190–1223. |
| [14] |
M. Ledoux, Poincaré inequalities in probability and geometric analysis, Available from: https://perso.math.univ-toulouse.fr/ledoux/files/2016/05/Poincare100wpause.pdf |
| [15] |
G. Leoni, A First Course in Sobolev Spaces, Graduate Studies in Mathematics, American Mathematical Society, 2009.
doi: 10.1090/gsm/105. |
| [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. |
| [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. |
| [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. |
| [19] |
C. A. Micchelli and T. J. Rivlin, A survey of optimal recovery, Optimal estimation in approximation theory, (1977), 1–54. |
| [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. |
| [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. |
| [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.
|
| [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. |
| [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. |
| [25] |
D. Ruiz, A note on the uniformity of the constant in the poincaré inequality, preprint, arXiv: 1208.6045. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [1] |
Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977 |
| [2] |
Yongliang Zhou, Yangkendi Deng, Di Wu, Dunyan Yan. Necessary and sufficient conditions on weighted multilinear fractional integral inequality. Communications on Pure and Applied Analysis, 2022, 21 (2) : 727-747. doi: 10.3934/cpaa.2021196 |
| [3] |
Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895 |
| [4] |
Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645 |
| [5] |
Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022017 |
| [6] |
Giovanni Covi, Keijo Mönkkönen, Jesse Railo. Unique continuation property and Poincaré inequality for higher order fractional Laplacians with applications in inverse problems. Inverse Problems and Imaging, 2021, 15 (4) : 641-681. doi: 10.3934/ipi.2021009 |
| [7] |
Yutian Lei, Zhongxue Lü. Axisymmetry of locally bounded solutions to an Euler-Lagrange system of the weighted Hardy-Littlewood-Sobolev inequality. Discrete and Continuous Dynamical Systems, 2013, 33 (5) : 1987-2005. doi: 10.3934/dcds.2013.33.1987 |
| [8] |
Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485 |
| [9] |
Guozhen Lu, Yunyan Yang. Sharp constant and extremal function for the improved Moser-Trudinger inequality involving $L^p$ norm in two dimension. Discrete and Continuous Dynamical Systems, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963 |
| [10] |
Jorge A. Becerril, Javier F. Rosenblueth. Necessity for isoperimetric inequality constraints. Discrete and Continuous Dynamical Systems, 2017, 37 (3) : 1129-1158. doi: 10.3934/dcds.2017047 |
| [11] |
Gisella Croce, Bernard Dacorogna. On a generalized Wirtinger inequality. Discrete and Continuous Dynamical Systems, 2003, 9 (5) : 1329-1341. doi: 10.3934/dcds.2003.9.1329 |
| [12] |
Canghua Jiang, Zhiqiang Guo, Xin Li, Hai Wang, Ming Yu. An efficient adjoint computational method based on lifted IRK integrator and exact penalty function for optimal control problems involving continuous inequality constraints. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1845-1865. doi: 10.3934/dcdss.2020109 |
| [13] |
Felipe Riquelme. Ruelle's inequality in negative curvature. Discrete and Continuous Dynamical Systems, 2018, 38 (6) : 2809-2825. doi: 10.3934/dcds.2018119 |
| [14] |
YanYan Li, Tonia Ricciardi. A sharp Sobolev inequality on Riemannian manifolds. Communications on Pure and Applied Analysis, 2003, 2 (1) : 1-31. doi: 10.3934/cpaa.2003.2.1 |
| [15] |
Hubert L. Bray, Marcus A. Khuri. A Jang equation approach to the Penrose inequality. Discrete and Continuous Dynamical Systems, 2010, 27 (2) : 741-766. doi: 10.3934/dcds.2010.27.741 |
| [16] |
S. S. Dragomir, C. E. M. Pearce. Jensen's inequality for quasiconvex functions. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 279-291. doi: 10.3934/naco.2012.2.279 |
| [17] |
Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437 |
| [18] |
Alexei Shadrin. The Landau--Kolmogorov inequality revisited. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1183-1210. doi: 10.3934/dcds.2014.34.1183 |
| [19] |
Alain Haraux. Some applications of the Łojasiewicz gradient inequality. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2417-2427. doi: 10.3934/cpaa.2012.11.2417 |
| [20] |
Igor E. Verbitsky. The Hessian Sobolev inequality and its extensions. Discrete and Continuous Dynamical Systems, 2015, 35 (12) : 6165-6179. doi: 10.3934/dcds.2015.35.6165 |
2020 Impact Factor: 1.392
Tools
Metrics
Other articles
by authors
[Back to Top]