Linear and Nonlinear Methods of Relief Approximation

K. I. Oskolkov

Contemporary Mathematics. Fundamental Directions, Theory of functions, Tome 25 (2007), pp. 126-148.

Résumé

In this article we compare the effectiveness of free (nonlinear) relief approximation, equidistant relief approximation, and polynomial approximation $\mathscr R^{\mathrm{fr}}_N[f]$, $\mathscr R^{\mathrm{eq}}_N[f]$, $\mathscr E_N[f]$ of an individual function $f(\mathbf{x})$ in the metric $\mathscr L^2(\mathbb B^2)$, where $\mathbb B^2$ is the unit ball $|\mathbf{x}|\le1$ in the plane $\mathbb R^2$. The notation we use is the following \begin{gather*} \mathscr R^{\mathrm{fr}}_N[f] :=\inf_{R\in\mathscr W^{\mathrm{fr}}_N}\|f-R\|, \quad \mathscr R^{\mathrm{eq}}_N[f]:=\min_{R\in\mathscr W^{\mathrm{eq}}_N}\|f-R\|, \\ \mathscr E_N[f]:=\min_{P\in\mathscr{P}^2_{N-1}}\|f-P\|. \end{gather*} Here $\mathscr W^{\mathrm{fr}}_N$ is the set of all $N$-term linear combinations of functions of the plane wave type $$ R(\mathbf{x})=\sum_1^N W_j(\mathbf{x}\cdot\boldsymbol\theta_j) $$ with arbitrary profiles $W_j(x)$, $x\in\mathbb R^1$ and transmission directions $\{\boldsymbol\theta_j\}_1^N$; $\mathscr W^{\mathrm{eq}}_N$ is the subset of $\mathscr W^{\mathrm{fr}}_N$ associated with $N$ equidistant directions; $$ \mathscr{P}^2_{N-1}:=\operatorname{Span}\{x_1^kx_2^l\}_{k+l} $$ denotes the subspace of algebraic polynomials of degree less or equal to $N-1$ in two real variables. Obviously, inequalities $\mathscr R^{\mathrm{fr}}_N[f] \le\mathscr R^{\mathrm{eq}}_N[f]\le\mathscr E_N[f]$ hold. We state the following model problem. What are the functions which satisfy the relation $\mathscr R^{\mathrm{fr}}_N[f]=o(\mathscr R^{\mathrm{eq}}_N[f])$, i.e., where nonlinear approximation $\mathscr R^{\mathrm{fr}}$ is more effective than linear one? This effect have been proved for harmonic functions, namely, for any $\varepsilon>0$ there exists $c_\varepsilon>0$ such that if $\Delta f(\mathbf{x})=0$, $|\mathbf{x}|1$, $f\in\mathscr L^2(\mathbb B^2)$, then $$ \mathscr R^{\mathrm{fr}}_N[f] \le c_\varepsilon\big(\mathscr R^{\mathrm{eq}}_N[f]\exp(-N^\varepsilon)+\mathscr R^{\mathrm{eq}}_{N^{2-3\varepsilon}}[f]\big). $$ On the other hand, $\mathscr R^{\mathrm{fr}}_N[f]\ge\frac1c\mathscr R^{\mathrm{eq}}_{N^2}[f]$. Thus $\mathscr R^{\mathrm{fr}}_N[f]$ has an “almost squared effectiveness” of $\mathscr R^{\mathrm{eq}}_N[f]$ for $f=f_{\mathrm{harm}}$. However, this ultra-high order of approximation is obtained via a collaps of wave vectors. On the other hand, the nonlinearity of $\mathscr R^{\mathrm{fr}}$ which corresponds to the freedom of choice of wave vectors, does not much improve the order of approximation, for instance, for all the radial functions. If $f(\mathbf{x})=f(|\mathbf{x}|)$, then $\mathscr E_{2N}[f]\ge\mathscr R^{\mathrm{eq}}_N[f]\ge\sqrt{\dfrac23}\mathscr E_{2N}(f)$ and $\mathscr R^{\mathrm{fr}}_N[f]\ge\sup\limits_{\varepsilon>0}\sqrt{\dfrac\varepsilon{3(1+\varepsilon)}}\mathscr R^{\mathrm{eq}}_{(1+\varepsilon)N}[f]$. The technique we use is the Fourier–Chebyshev analysis (which is related to the inverse Radon transform on $\mathbb B^2$) and a duality between the relief approximation problem and the optimization of quadrature formulas in the sense of Kolmogorov–Nikolskii [1] for trigonometric polynomials classes.

Bibliographie

[1] Zhensykbaev A. A., “Monosplainy minimalnoi normy i optimalnye kvadraturnye formuly”, UMN, 36:4 (1981), 107–159 | MR | Zbl

[2] Kashin B. S., “O nekotorykh svoistvakh trigonometricheskikh polinomov v svyazi s ravnomernoi skhodimostyu”, Soobsch. AN Gruz. SSR, 93 (1979), 281–284 | MR | Zbl

[3] Kashin B. S., “O nekotorykh svoistvakh trigonometricheskikh polinomov s ravnomernoi normoi”, Trudy MIAN, 145, 1980, 111–116 | MR | Zbl

[4] Korneichuk N. P., Splainy v teorii approksimatsii, Nauka, M., 1984 | MR

[5] Motornyi V. P., “O nailuchshei kvadraturnoi formule $\sum\limits_{k=1}^n p_kf(x_k)$ dlya nekotorykh klassov periodicheskikh differentsiruemykh funktsii”, Izv. AN SSSR. Ser. matem., 38:3 (1974), 583–614 | MR | Zbl

[6] Nikolskii S. M., Kvadraturnye formuly, Nauka, M., 1974 | MR

[7] Oskolkov K. I., “Ob optimalnosti kvadraturnoi formuly s ravnootstoyaschimi uzlami na klassakh periodicheskikh funktsii”, Dokl. AN SSSR, 249:1 (1979), 49–51 | MR | Zbl

[8] Oskolkov K. I., “Relefnaya approksimatsiya, analiz Chebyshëva–Fure i optimalnye kvadraturnye formuly”, Trudy MIAN, 219, 1997, 269–285 | MR | Zbl

[9] Sharapudinov I. I., “Ob odnom novom primenenii mnogochlenov Chebyshëva, ortogonalnykh na ravnomernoi setke”, Matem. zametki, 64:6 (1998), 950–953 | MR | Zbl

[10] Davison M. E., Grunbaum F. A., “Tomographic reconstruction with arbitrary directions”, Comm. Pure Appl. Math., 34 (1981), 77–120 | DOI | MR

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

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

[13] Groemer H., Geometric applications of Fourier series and spherical harmonics, Cambridge Univ. Press, Cambridge, 1996 | MR | Zbl

[14] Lachance M., Saff E. B., Varga R. S., “Inequalities for polynomials with a prescribed zero”, Math. Z., 168 (1979), 105–116 | DOI | MR | Zbl

[15] Logan B., Schepp L., “Optimal reconstruction of a function from its projections”, Duke Math. J., 42 (1975), 645–659 | DOI | MR | Zbl

[16] Majorov V. E., On best approximation by ridge functions, Preprint, Department of Mathematics, Technion, Haifa, Israel, 1997

[17] Majorov V. E., On best approximation by ridge functions, Preprint, January 14, Department of Mathematics, Technion, Haifa, Israel, 1998

[18] Montgomery H. L., Ten lectures on the interface between analytic number theory and harmonic analysis, Amer. Math. Soc., Providence, RI, 1994 | MR

[19] Oskolkov K. I., “On optimal quadrature formulae on certain classes of periodic functions”, Appl. Math. Optim., 8 (1982), 245–263 | DOI | MR | Zbl

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

[21] Ramm A. G., Katsevich A. I., The Radon transform and local tomography, CRC Press, Boca Raton, CA, 1996 | MR | Zbl

[22] Temlyakov V. N., Approximation of periodic functions, Nova Sci. Publ., Commack, NY, 1993 | MR | Zbl

[23] Temlyakov V. N., On approximation by ridge functions, Preprint, Department of Mathematics, University of South Carolina, 1996 | MR