Approximation by sums of ridge functions with fixed directions

V. E. Ismailov

Algebra i analiz, Tome 28 (2016) no. 6, pp. 20-69.

Résumé

The paper contains a survey of some results about approximation of functions of several variables by sums of ridge functions with fixed directions. Also, some new theorems are proved, both for uniform approximation and for approximation in $L_2$ . These theorems generalize some results by the author known previously. The paper is finished by the study of the role of ridge functions in a problem of approximation by neural networks.

Détail

Keywords: Ridge function, best approximation, superposition, cycle, path, neural network.

Bibliographie

[1] Arnold V. I., “O predstavlenii nepreryvnykh funktsii trekh peremennykh superpozitsiyami nepreryvnykh funktsii dvukh peremennykh”, Mat. sb., 48(90):1 (1959), 3–74 | MR | Zbl

[2] Babaev M.-B. A., “O priblizhenii mnogochlenov dvukh peremennykh summami funktsii odnoi peremennoi”, Dokl. AN SSSR, 193:5 (1970), 967–969 | Zbl

[3] Babaev M.-B. A., “O tochnykh otsenkakh priblizheniya funktsii mnogikh peremennykh summami funktsii menshego chisla peremennykh”, Mat. zametki, 12:1 (1972), 105–114 | MR | Zbl

[4] Braess D., Pinkus A., “Interpolation by ridge functions”, J. Approx. Theory, 73:2 (1993), 218–236 | DOI | MR | Zbl

[5] Buck R. C., “On approximation theory and functional equations”, J. Approx. Theory, 5 (1972), 228–237 | DOI | MR | Zbl

[6] Buhmann M. D., Pinkus A., “Identifying linear combinations of ridge functions”, Adv. in App. Math., 22:1 (1999), 103–118 | DOI | MR | Zbl

[7] Candes E. J., “Ridgelets: estimating with ridge functions”, Ann. Statist., 31:5 (2003), 1561–1599 | DOI | MR | Zbl

[8] Candes E. J., Ridgelets: theory and applications, Ph. D. Thesis, Depart. Statist., Stanford Univ., Stanford, 1998 | MR

[9] Chen T., Chen H., “Approximation of continuous functionals by neural networks with application to dynamic systems”, IEEE Trans. Neural Networks, 4 (1993), 910–918 | DOI

[10] Cheney E. W., Light W. A., Approximation theory in tensor product spaces, Lecture Notes in Math., 1169, Springer-Verlag, Berlin, 1985 | MR | Zbl

[11] Chui C. K., Li X., “Approximation by ridge functions and neural networks with one hidden layer”, J. Approx. Theory, 70:2 (1992), 131–141 | DOI | MR | Zbl

[12] Cowsik R. C., Klopotowski A., Nadkarni M. G., “When is $f(x,y)=u(x)+v(y)$?”, Proc. Indian Acad. Sci. Math. Sci., 109:1 (1999), 57–64 | DOI | MR | Zbl

[13] Cybenko G., “Approximation by superpositions of a sigmoidal function”, Math. Control Signals, Systems, 2:4 (1989), 303–314 | DOI | MR | Zbl

[14] Demko S., “A superposition theorem for bounded continuous functions”, Proc. Amer. Math. Soc., 66:1 (1977), 75–78 | DOI | MR | Zbl

[15] DeVore R. A., Oskolkov K. I., Petrushev P. P., “Approximation by feedforward neural networks”, Ann. Numer. Math., 4:1 (1997), 261–287 | MR | Zbl

[16] Diaconis P., Shahshahani M., “On nonlinear functions of linear combinations”, SIAM J. Sci. Statist. Comput., 5:1 (1984), 175–191 | DOI | MR | Zbl

[17] Diliberto S. P., Straus E. G., “On the approximation of a function of several variables by the sum of functions of fewer variables”, Pacific J. Math., 1 (1951), 195–210 | DOI | MR | Zbl

[18] Donoho D. L., Johnstone I. M., “Projection-based approximation and a duality method with kernel methods”, Ann. Statist., 17:1 (1989), 58–106 | DOI | MR | Zbl

[19] Dyn N., Light W. A., Cheney E. W., “Interpolation by piecewise-linear radial basis functions”, J. Approx. Theory, 59:2 (1989), 202–223 | DOI | MR | Zbl

[20] Fridman B. L., “Uluchshenie gladkosti funktsii v teoreme A. N. Kolmogorova o superpozitsiyakh”, Dokl. AN SSSR, 177:5 (1967), 1019–1022 | Zbl

[21] Friedman J. H., Tukey J. W., “A projection pursuit algorithm for exploratory data analysis”, IEEE Trans. Comput., 23 (1974), 881–890 | DOI | Zbl

[22] Friedman J. H., Stuetzle W., “Projection pursuit regression”, J. Amer. Statist. Assoc., 76:376 (1981), 817–823 | DOI | MR

[23] Garkavi A. L., Medvedev V. A., Khavinson S. Ya., “O suschestvovanii nailuchshego ravnomernogo priblizheniya funktsii dvukh peremennykh summami $\varphi(x)+\psi(y)$”, Sib. mat. zh., 36:4 (1995), 819–827 | MR | Zbl

[24] von Golitschek M., Light W. A., “Approximation by solutions of the planar wave equation”, SIAM J. Numer. Anal., 29:3 (1992), 816–830 | DOI | MR

[25] Golomb M., “Approximation by functions of fewer variables. On numerical approximation”, Proc. Symp. (Madison, 1958), Univ. Wisconsin Press, Madison, 1959, 275–327 | MR

[26] Gripenberg G., “Approximation by neural networks with a bounded number of nodes at each level”, J. Approx. Theory, 122:2 (2003), 260–266 | DOI | MR | Zbl

[27] Hornik K., “Approximation capabilities of multilayer feedforward networks”, Neural Networks, 4 (1991), 251–257 | DOI

[28] Huber P. J., “Projection pursuit”, Ann. Statist., 13:2 (1985), 435–475 | DOI | MR

[29] Ismailov V. E., “Approximation by neural networks with weights varying on a finite set of directions”, J. Anal. Appl., 389:1 (2012), 72–83 | DOI | MR | Zbl

[30] Ismailov V. E., “A note on the representation of continuous functions by linear superpositions”, Expo. Math., 30:1 (2012), 96–101 | DOI | MR | Zbl

[31] Ismailov V. E., “On the theorem of M. Golomb”, Proc. Indian Acad. Sci. Math. Sci., 119:1 (2009), 45–52 | DOI | MR | Zbl

[32] Ismailov V. E., “On the representation by linear superpositions”, J. Approx. Theory, 151:2 (2008), 113–125 | DOI | MR | Zbl

[33] Ismailov V. E., “A note on the best $L_2$ approximation by ridge functions”, Appl. Math. E-Notes, 7 (2007), 71–76, (electronic) | MR | Zbl

[34] Ismailov V. E., “Characterization of an extremal sum of ridge functions”, J. Comput. Appl. Math., 205:1 (2007), 105–115 | DOI | MR | Zbl

[35] Ismailov V. E., “On error formulas for approximation by sums of univariate functions”, Int. J. Math. Math. Sci., 2006 (2006), Article ID 65620 | DOI | MR | Zbl

[36] Ismailov V. E., “O metodakh vychisleniya tochnogo znacheniya nailuchshego priblizheniya summami funktsii odnoi peremennoi”, Sib. mat. zh., 47:5 (2006), 1076–1082 | MR | Zbl

[37] Ito Y., “Nonlinearity creates linear independence”, Adv. Comput. Math., 5:2–3 (1996), 189–203 | DOI | MR | Zbl

[38] Ito Y., “Approximation of functions on a compact set by finite sums of a sigmoid function without scaling”, Neural Networks, 4:6 (1991), 817–826 | DOI

[39] Ito Y., “Approximation of continuous functions on $\mathbb R^d$ by linear combinations of shifted rotations of a sigmoid function with and without scaling”, Neural Networks, 5 (1992), 105–115 | DOI

[40] John F., Plane waves and spherical means applied to partial differential equations, Intersci. Publ., New York, 1955 | MR | Zbl

[41] Kazantsev I., “Tomographic reconstruction from arbitrary directions using ridge functions”, Inverse Problems, 14:3 (1998), 635–645 | DOI | MR | Zbl

[42] Kazantsev I., Lemahieu I., “Reconstruction of elongated structures using ridge functions and natural pixels”, Inverse Problems, 16:6 (2000), 505–517 | DOI | MR | Zbl

[43] Khavinson S. Ya., Best approximation by linear superpositions (approximate nomography), Transl. Math. Monogr., 159, Amer. Math. Soc., Providence, RI, 1997 | MR | Zbl

[44] Khavinson S. Ya., “Chebyshevskaya teorema dlya priblizheniya funktsii dvukh peremennykh summami $\varphi(x)+\psi(y)$”, Izv. AN SSSR. Ser. mat., 33:3 (1969), 650–666 | MR | Zbl

[45] Klopotowski A., Nadkarni M. G., Bhaskara Rao K. P. S., “When is $f(x_1,x_2,\dots,x_n)=u_1(x_1)+u_2(x_2)+\dots+u_n(x_n)$?”, Proc. Indian Acad. Sci. Math. Sci., 113:1 (2003), 77–86 | DOI | MR | Zbl

[46] Kolmogorov A. N., “O predstavlenii nepreryvnykh funktsii neskolkikh peremennykh v vide superpozitsii nepreryvnykh funktsii odnoi peremennoi i slozheniya”, Dokl. AN SSSR, 114:5 (1957), 953–956 | MR | Zbl

[47] Leshno M., Lin V. Ya., Pinkus A., Schocken S., “Multilayer feedforward networks with a non-polynomial activation function can approximate any function”, Neural Networks, 6 (1993), 861–867 | DOI

[48] Li X., “Interpolation by ridge polynomials and its application in neural networks”, J. Comput. Appl. Math., 144:1–2 (2002), 197–209 | MR | Zbl

[49] Light W. A., Cheney E. W., “On the approximation of a bivariate function by the sum of univariate functions”, J. Approx. Theory, 29:4 (1980), 305–323 | DOI | MR

[50] Light W. A., “Ridge functions, sigmoidal functions and neural networks”, Approximation Theory VII (Austin, TX, 1992), Acad. Press, Boston, MA, 1993, 163–206 | MR

[51] Lin V. Ya., Pinkus A., “Fundamentality of ridge functions”, J. Approx. Theory, 75:3 (1993), 295–311 | DOI | MR | Zbl

[52] Logan B. F., Shepp L. A., “Optimal reconstruction of a function from its projections”, Duke Math. J., 42:4 (1975), 645–659 | DOI | MR | Zbl

[53] Lorentz G. G., “Metric entropy, widths, and superpositions of functions”, Amer. Math. Monthly, 69 (1962), 469–485 | DOI | MR | Zbl

[54] Maiorov V., Pinkus A., “Lower bounds for approximation by MLP neural networks”, Neurocomputing, 25 (1999), 81–91 | DOI | Zbl

[55] Maiorov V., “Approximation by neural networks and learning theory”, J. Complexity, 22:1 (2006), 102–117 | DOI | MR | Zbl

[56] Maiorov V. E., “On best approximation by ridge functions”, J. Approx. Theory, 99:1 (1999), 68–94 | DOI | MR | Zbl

[57] Marr R. B., “On the reconstruction of a function on a circular domain from a sampling of its line integrals”, J. Math. Anal. Appl., 45 (1974), 357–374 | DOI | MR | Zbl

[58] Marshall D. E., O'Farrell A. G., “Approximation by a sum of two algebras. The lightning bolt principle”, J. Funct. Anal., 52:3 (1983), 353–368 | DOI | MR | Zbl

[59] Marshall D. E., O'Farrell A. G., “Uniform approximation by real functions”, Fund. Math., 104:3 (1979), 203–211 | MR | Zbl

[60] Natterer F., The mathematics of computerized tomography, J. Wiley, Lfd., Chichester, 1986 | MR | Zbl

[61] Oskolkov K. I., “Relefnaya approksimatsiya, analiz Fure–Chebysheva i optimalnye kvadraturnye formuly”, Tr. MIAN, 219, 1997, 269–285 | MR | Zbl

[62] Ostrand P. A., “Dimension of metric spaces and Hilbert's problem 13”, Bull. Amer. Math. Soc., 71 (1965), 619–622 | DOI | MR | Zbl

[63] Petrushev P. P., “Approximation by ridge functions and neural networks”, SIAM J. Math. Anal., 30:1 (1998), 155–189 | DOI | MR

[64] Pinkus A., “Approximating by ridge functions”, Surface Fitting and Multiresolution Methods, Vanderbilt Univ. Press, Nashville, 1997, 279–292 | MR | Zbl

[65] Pinkus A., “Approximation theory of the MLP model in neural networks”, Acta Numer., 8 (1999), 143–195 | DOI | MR | Zbl

[66] Rudin W., Functional analysis, McGraw-Hill Ser. Higher Math., McGraw-Hill Book Co., New York, 1973 | MR | Zbl

[67] Sanguineti M., “Universal approximation by ridge computational models and neural networks: a survey”, Open Appl. Math. J., 2:1 (2008), 31–58 | DOI | MR | Zbl

[68] Schwartz L., “Theorie generale des fonctions moyenne-periodiques”, Ann. of Math. (2), 48 (1947), 857–928 | DOI | MR

[69] Shin Y., Ghosh J., “Ridge polynomial networks”, IEEE Trans. Neural Networks, 6 (1995), 610–622 | DOI

[70] Sprecher D. A., “An improvement in the superposition theorem of Kolmogorov”, J. Math. Anal. Appl., 38 (1972), 208–213 | DOI | MR | Zbl

[71] Sproston J. P., Strauss D., “Sums of subalgebras of $\mathrm{C(X)}$”, J. London Math. Soc. (2), 45:2 (1992), 265–278 | DOI | MR | Zbl

[72] Sternfeld Y., “Dimension, superposition of functions and separation of points, in compact metric spaces”, Israel J. Math., 50:1–2 (1985), 13–53 | DOI | MR | Zbl

[73] Sternfeld Y., “Uniform separation of points and measures and representation by sums of algebras”, Israel J. Math., 55:3 (1986), 350–362 | DOI | MR | Zbl

[74] Sternfeld Y., “Uniformly separating families of functions”, Israel J. Math., 29:1 (1978), 61–91 | DOI | MR | Zbl

[75] Stinchcombe M., White H., “Approximating and learning unknown mappings using multilayer feedforward networks with bounded weights”, Proc. Internat. Joint Conf. Neural Networks, v. 3, IEEE, New York, 1990, 7–16 | MR

[76] Temlyakov V. N., On approximation by ridge functions, Preprint, Depart. Math., Univ. South Carolina, 1996

[77] Vitushkin A. G., Khenkin G. M., “Lineinye superpozitsii funktsii”, Uspekhi mat. nauk, 22:1 (1967), 77–124 | MR | Zbl

[78] Vostretsov B. A., Kreines M. A, “O priblizhenii nepreryvnykh funktsii superpozitsiyami ploskikh voln”, Dokl. AN SSSR, 140:6 (1961), 1237–1240 | Zbl

[79] Wu W., Feng G., Li X., “Training multilayer perceptrons via minimization of sum of ridge functions”, Adv. Comput. Math., 17:4 (2002), 331–347 | DOI | MR | Zbl

[80] Xie T. F., Cao F. L., “The ridge function representation of polynomials and an application to neural networks”, Acta Math. Sin. (Engl. Ser.), 27:11 (2011), 2169–2176 | DOI | MR | Zbl