Skip to main content
SpringerLink
Log in

Optimal Stable Nonlinear Approximation

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

While it is well-known that nonlinear methods of approximation can often perform dramatically better than linear methods, there are still questions on how to measure the optimal performance possible for such methods. This paper studies nonlinear methods of approximation that are compatible with numerical implementation in that they are required to be numerically stable. A measure of optimal performance, called stable manifold widths, for approximating a model class K in a Banach space X by stable manifold methods is introduced. Fundamental inequalities between these stable manifold widths and the entropy of K are established. The effects of requiring stability in the settings of deep learning and compressed sensing are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ya. Alber, A. Notik, On some estimates for projection operator on Banach spaces, Comm. on Applied Nonlinear Analysis, 2(1) (1993), arXiv:funct-an/9311003.

  2. P. Aleksandrov, Combinatorial Topology, Vol. 1, Graylock Press, Rochester, NY, 1956.

    Google Scholar 

  3. Y. Benyamini, J. Lindenstrauss, Geometric Nonlinear Functional Analysis, Vol. 1, American Mathematical Society Colloquium Publications, 48(2000), AMS, Providence, RI.

  4. J. Bourgain, On Lipschitz Embedding of Finite Metric Spaces in Hilbert Space, Israel J. Math., 52 (1985), 46–52.

    Article  MathSciNet  Google Scholar 

  5. B. Carl, Entropy numbers, s-numbers, and eigenvalue problems, J. Funct. Anal., 41 (1981), 290–306.

    Article  MathSciNet  Google Scholar 

  6. P. Ciarlet, C. Wagschal, Multipoint Taylor formulas and applications to the finite element method, Num. Mathematik, 17 (1971), 84–100.

    Article  MathSciNet  Google Scholar 

  7. A. Cohen, W. Dahmen, I. Daubechies, R. DeVore, Tree Approximation and Optimal Encoding, ACHA, 11 (2001) 192–226.

    MathSciNet  MATH  Google Scholar 

  8. A. Cohen, W. Dahmen, R. DeVore, Compressed sensing and best k-term approximation, J. Amer. Math. Soc., 22 (2009), 211–231.

    Article  MathSciNet  Google Scholar 

  9. S. Dasgupta, A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures Algorithms, 22(1) (2003), 60–65.

    Article  MathSciNet  Google Scholar 

  10. I. Daubechies, R. DeVore, S. Foucart, B. Hanin, G. Petrova, Nonlinear approximation and deep (ReLU) networks, arXiv:1905.02199, 2019

  11. R. DeVore, R. Howard, C. Micchelli, Optimal nonlinear approximation, Manuscripta Mathematica 63(4) (1989), 469–478.

    Article  MathSciNet  Google Scholar 

  12. R. DeVore, G. Kyriazis, D. Leviaton, V. Tichomirov, Wavelet compression and nonlinear n-widths, Advances in Computational Mathematics, 1(2) (1993), 197–214.

    Article  MathSciNet  Google Scholar 

  13. G. Godefroy, Lipschitz approximable Banach spaces, Comment. Math. Univ. Carolin. 61(2), 187–193 (2020).

  14. G. Godefroy, A survey on Lipschitz-free Banach spaces, Commentationes Mathematicae, 55(2015), 89–118.

    MathSciNet  MATH  Google Scholar 

  15. G. Godefroy, N. Kalton, Lipschitz-free Banach spaces, Studia Math., 159(1) (2003), 121–141.

    Article  MathSciNet  Google Scholar 

  16. T. Hytonen, J van Neerven, M. Veraar, L. Weis, Analysis in Banach Spaces, Volume I: Martingales and Littlewood-Paley Theory, Springer, 2016.

  17. W. Johnson, J. Lindenstrauss, Extensions of Lipschitz Mappings into a Hilbert Space, Contemporary Mathematics, 26 (1984), 189–206.

    Article  MathSciNet  Google Scholar 

  18. W. Johnson, J. Lindenstrauss, G. Schechtman, Extensions of Lipschitz Mappings into Banach Spaces, Israel J. Math., 54(2) (1986), 129–138.

    Article  MathSciNet  Google Scholar 

  19. E. Michael, A. Pełczyński, Separable Banach spaces which admit \(\ell _n^\infty \) approximations, Israel J. Math., 4 (1966), 189–198.

    Article  MathSciNet  Google Scholar 

  20. S. Kachanovich, Meshing submanifolds using Coxeter triangulations Computational Geometry[cs.CG]. COMUE Universite Cote d’Azur (2015 - 2019), 2019. English. NNT: 2019AZUR4072?tel-02419148v2, thesis, https://hal.inria.fr/tel-02419148v2/document

  21. A. Pinkus, \(n\)-widths in Approximation Theory, Springer, 2012.

  22. G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, Cambridge Univ. Press, Cambridge, 1989.

  23. Jianfeng Lu, Zuowei Shen, Haizhao Yang, Shijun Zhang, Deep Network Approximation for Smooth Functions, preprint 2020.

    Google Scholar 

  24. D. Yarotsky, Error bounds for approximations with deep ReLU networks, Neural Networks, 94 (2017), 103–114.

    Article  Google Scholar 

  25. P. Wojtaszczyk, Banach Spaces for Analysts, Cambridge U. Press, 1991.

Download references

Acknowledgements

The authors thank Professor Giles Godefroy for insightful discussions on the results of this paper.

Author information

Authors and Affiliations

  1. Laboratoire Jacques-Louis Lions, Sorbonne Université, 4, Place Jussieu, 75005, Paris, France

    Albert Cohen

  2. Department of Mathematics, Texas A&M University, College Station, TX, 77843, USA

    Ronald DeVore & Guergana Petrova

  3. Institut of Mathematics Polish Academy of Sciences, ul. Śniadeckich 8, 00-656, Warsaw, Poland

    Przemyslaw Wojtaszczyk

Authors
  1. Albert Cohen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ronald DeVore
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guergana Petrova
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Przemyslaw Wojtaszczyk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Albert Cohen.

Additional information

Communicated by Pencho Petrushev.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was supported by the NSF Grant DMS 1817603 (RD-GP) and the ONR Contract N00014-17-1-2908 (RD). P. W. was supported by National Science Centre, Polish Grant UMO-2016/21/B/ST1/00241. A portion of this research was completed when the first three authors were visiting the Isaac Newton InstituteTripods Grant CCF-1934904 (RD-GP); ONR Contract N00014-20-1-2787 (RD-GP).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cohen, A., DeVore, R., Petrova, G. et al. Optimal Stable Nonlinear Approximation. Found Comput Math 22, 607–648 (2022). https://doi.org/10.1007/s10208-021-09494-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-021-09494-z

Keywords

Mathematics Subject Classification

Search

Navigation