Source author record

Ronald DeVore

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA Numerical Analysis math.AP math.FA math.PR math.ST Statistics Theory

Catalog footprint

Research overview

15works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Neural Network Approximation

Neural Networks (NNs) are the method of choice for building learning algorithms. Their popularity stems from their empirical success on several challenging learning problems. However, most scholars agree that a convincing theoretical explanation for this success is still lacking. This article surveys the known approximation properties of the outputs of NNs with the aim of uncovering the properties that are not present in the more traditional methods of approximation used in numerical analysis. Comparisons are made with traditional approximation methods from the viewpoint of rate distortion. Another major component in the analysis of numerical approximation is the computational time needed to construct the approximation and this in turn is intimately connected with the stability of the approximation algorithm. So the stability of numerical approximation using NNs is a large part of the analysis put forward. The survey, for the most part, is concerned with NNs using the popular ReLU activation function. In this case, the outputs of the NNs are piecewise linear functions on rather complicated partitions of the domain of $f$ into cells that are convex polytopes. When the architecture of the NN is fixed and the parameters are allowed to vary, the set of output functions of the NN is a parameterized nonlinear manifold. It is shown that this manifold has certain space filling properties leading to an increased ability to approximate (better rate distortion) but at the expense of numerical stability. The space filling creates a challenge to the numerical method in finding best or good parameter choices when trying to approximate.

preprint2020arXiv

Nonlinear Methods for Model Reduction

The usual approach to model reduction for parametric partial differential equations (PDEs) is to construct a linear space $V_n$ which approximates well the solution manifold $\mathcal{M}$ consisting of all solutions $u(y)$ with $y$ the vector of parameters. This linear reduced model $V_n$ is then used for various tasks such as building an online forward solver for the PDE or estimating parameters from data observations. It is well understood in other problems of numerical computation that nonlinear methods such as adaptive approximation, $n$ -term approximation, and certain tree-based methods may provide improved numerical efficiency. For model reduction, a nonlinear method would replace the linear space $V_n$ by a nonlinear space $Σ_n$ . This idea has already been suggested in recent papers on model reduction where the parameter domain is decomposed into a finite number of cells and a linear space of low dimension is assigned to each cell. Up to this point, little is known in terms of performance guarantees for such a nonlinear strategy. Moreover, most numerical experiments for nonlinear model reduction use a parameter dimension of only one or two. In this work, a step is made towards a more cohesive theory for nonlinear model reduction. Framing these methods in the general setting of library approximation allows us to give a first comparison of their performance with those of standard linear approximation for any general compact set. We then turn to the study these methods for solution manifolds of parametrized elliptic PDEs. We study a very specific example of library approximation where the parameter domain is split into a finite number $N$ of rectangular cells and where different reduced affine spaces of dimension $m$ are assigned to each cell. The performance of this nonlinear procedure is analyzed from the viewpoint of accuracy of approximation versus $m$ and $N$ .

preprint2020arXiv

Optimal Stable Nonlinear Approximation

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 {\em 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.

preprint2020arXiv

Polynomial Approximation of Anisotropic Analytic Functions of Several Variables

Motivated by numerical methods for solving parametric partial differential equations, this paper studies the approximation of multivariate analytic functions by algebraic polynomials. We introduce various anisotropic model classes based on Taylor expansions, and study their approximation by finite dimensional polynomial spaces $\cal{P}_Λ$ described by lower sets $Λ$ . Given a budget $n$ for the dimension of $\cal{P}_Λ$ , we prove that certain lower sets $Λ_n$ , with cardinality $n$ , provide a certifiable approximation error that is in a certain sense optimal, and that these lower sets have a simple definition in terms of simplices. Our main goal is to obtain approximation results when the number of variables $d$ is large and even infinite, and so we concentrate almost exclusively on the case $d=\infty$ . We also emphasize obtaining results which hold for the full range $n\ge 1$ , rather than asymptotic results that only hold for $n$ sufficiently large. In applications, one typically wants $n$ small to comply with computational budgets.

preprint2020arXiv

Reduced Basis Greedy Selection Using Random Training Sets

Reduced bases have been introduced for the approximation of parametrized PDEs in applications where many online queries are required. Their numerical efficiency for such problems has been theoretically confirmed in \cite{BCDDPW,DPW}, where it is shown that the reduced basis space $V_n$ of dimension $n$ , constructed by a certain greedy strategy, has approximation error similar to that of the optimal space associated to the Kolmogorov $n$ -width of the solution manifold. The greedy construction of the reduced basis space is performed in an offline stage which requires at each step a maximization of the current error over the parameter space. For the purpose of numerical computation, this maximization is performed over a finite {\em training set} obtained through a discretization. of the parameter domain. To guarantee a final approximation error $\varepsilon$ for the space generated by the greedy algorithm requires in principle that the snapshots associated to this training set constitute an approximation net for the solution manifold with accuracy or order $\varepsilon$ . Hence, the size of the training set is the $\varepsilon$ covering number for $\mathcal{M}$ and this covering number typically behaves like $\exp(C\varepsilon^{-1/s})$ for some $C>0$ when the solution manifold has $n$ -width decay $O(n^{-s})$ . Thus, the shear size of the training set prohibits implementation of the algorithm when $\varepsilon$ is small. The main result of this paper shows that, if one is willing to accept results which hold with high probability, rather than with certainty, then for a large class of relevant problems one may replace the fine discretization by a random training set of size polynomial in $\varepsilon^{-1}$ . Our proof of this fact is established by using inverse inequalities for polynomials in high dimensions.

preprint2016arXiv

Data Assimilation and Sampling in Banach spaces

This paper studies the problem of approximating a function $f$ in a Banach space $X$ from measurements $l_j(f)$ , $j=1,\dots,m$ , where the $l_j$ are linear functionals from $X^*$ . Most results study this problem for classical Banach spaces $X$ such as the $L_p$ spaces, $1\le p\le \infty$ , and for $K$ the unit ball of a smoothness space in $X$ . Our interest in this paper is in the model classes $K=K(ε,V)$ , with $ε>0$ and $V$ a finite dimensional subspace of $X$ , which consists of all $f\in X$ such that $dist(f,V)_X\le ε$ . These model classes, called {\it approximation sets}, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance, and algorithms for finding near optimal approximations. We show how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.

preprint2016arXiv

Diffusion Coefficients Estimation for Elliptic Partial Differential Equations

This paper considers the Dirichlet problem $-\mathrm{div}(a\nabla u_a)=f \quad \hbox{on}\,\,\ D, \qquad u_a=0\quad \hbox{on}\,\,\partial D,$ for a Lipschitz domain $D\subset \mathbb R^d$ , where $a$ is a scalar diffusion function. For a fixed $f$ , we discuss under which conditions is $a$ uniquely determined and when can $a$ be stably recovered from the knowledge of $u_a$ . A first result is that whenever $a\in H^1(D)$ , with $0<λ\le a\le Λ$ on $D$ , and $f\in L_\infty(D)$ is strictly positive, then $\|a-b\|_{L_2(D)}\le C\|u_a-u_b\|_{H_0^1(D)}^{1/6}.$ More generally, it is shown that the assumption $a\in H^1(D)$ can be weakened to $a\in H^s(D)$ , for certain $s<1$ , at the expense of lowering the exponent $1/6$ to a value that depends on $s$ .

preprint2015arXiv

Approximation of high-dimensional parametric PDEs

Parametrized families of PDEs arise in various contexts such as inverse problems, control and optimization, risk assessment, and uncertainty quantification. In most of these applications, the number of parameters is large or perhaps even infinite. Thus, the development of numerical methods for these parametric problems is faced with the possible curse of dimensionality. This article is directed at (i) identifying and understanding which properties of parametric equations allow one to avoid this curse and (ii) developing and analyzing effective numerical methodd which fully exploit these properties and, in turn, are immune to the growth in dimensionality. The first part of this article studies the smoothness and approximability of the solution map, that is, the map $a\mapsto u(a)$ where $a$ is the parameter value and $u(a)$ is the corresponding solution to the PDE. It is shown that for many relevant parametric PDEs, the parametric smoothness of this map is typically holomorphic and also highly anisotropic in that the relevant parameters are of widely varying importance in describing the solution. These two properties are then exploited to establish convergence rates of $n$ -term approximations to the solution map for which each term is separable in the parametric and physical variables. These results reveal that, at least on a theoretical level, the solution map can be well approximated by discretizations of moderate complexity, thereby showing how the curse of dimensionality is broken. This theoretical analysis is carried out through concepts of approximation theory such as best $n$ -term approximation, sparsity, and $n$ -widths. These notions determine a priori the best possible performance of numerical methods and thus serve as a benchmark for concrete algorithms. The second part of this article turns to the development of numerical algorithms based on the theoretically established sparse separable approximations. The numerical methods studied fall into two general categories. The first uses polynomial expansions in terms of the parameters to approximate the solution map. The second one searches for suitable low dimensional spaces for simultaneously approximating all members of the parametric family. The numerical implementation of these approaches is carried out through adaptive and greedy algorithms. An a priori analysis of the performance of these algorithms establishes how well they meet the theoretical benchmarks.

preprint2015arXiv

Data Assimilation in Reduced Modeling

We consider the problem of optimal recovery of an element $u$ of a Hilbert space $\mathcal{H}$ from $m$ measurements obtained through known linear functionals on $\mathcal{H}$ . Problems of this type are well studied \cite{MRW} under an assumption that $u$ belongs to a prescribed model class, e.g. a known compact subset of $\mathcal{H}$ . Motivated by reduced modeling for parametric partial differential equations, this paper considers another setting where the additional information about $u$ is in the form of how well $u$ can be approximated by a certain known subspace $V_n$ of $\mathcal{H}$ of dimension $n$ , or more generally, how well $u$ can be approximated by each $k$ -dimensional subspace $V_k$ of a sequence of nested subspaces $V_0\subset V_1\cdots\subset V_n$ . A recovery algorithm for the one-space formulation, proposed in \cite{MPPY}, is proven here to be optimal and to have a simple formulation, if certain favorable bases are chosen to represent $V_n$ and the measurements. The major contribution of the present paper is to analyze the multi-space case for which it is shown that the set of all $u$ satisfying the given information can be described as the intersection of a family of known ellipsoids in $\mathcal{H}$ . It follows that a near optimal recovery algorithm in the multi-space problem is to identify any point in this intersection which can provide a much better accuracy than in the one-space problem. Two iterative algorithms based on alternating projections are proposed for recovery in the multi-space problem. A detailed analysis of one of them provides a posteriori performance estimates for the iterates, stopping criteria, and convergence rates. Since the limit of the algorithm is a point in the intersection of the aforementioned ellipsoids, it provides a near optimal recovery for $u$ .

preprint2015arXiv

Kolmogorov widths under holomorphic mappings

If $L$ is a bounded linear operator mapping the Banach space $X$ into the Banach space $Y$ and $K$ is a compact set in $X$ , then the Kolmogorov widths of the image $L(K)$ do not exceed those of $K$ multiplied by the norm of $L$ . We extend this result from linear maps to holomorphic mappings $u$ from $X$ to $Y$ in the following sense: when the $n$ widths of $K$ are $O(n^{-r})$ for some $r\textgreater{}1$, then those of $u(K)$ are $O(n^{-s})$ for any $s \textless{} r-1$, We then use these results to prove various theorems about Kolmogorov widths of manifolds consisting of solutions to certain parametrized PDEs. Results of this type are important in the numerical analysis of reduced bases and other reduced modeling methods, since the best possible performance of such methods is governed by the rate of decay of the Kolmogorov widths of the solution manifold.

preprint2015arXiv

Orthogonal Matching Pursuit under the Restricted Isometry Property

This paper is concerned with the performance of Orthogonal Matching Pursuit (OMP) algorithms applied to a dictionary $\mathcal{D}$ in a Hilbert space $\mathcal{H}$ . Given an element $f\in \mathcal{H}$ , OMP generates a sequence of approximations $f_n$ , $n=1,2,\dots$ , each of which is a linear combination of $n$ dictionary elements chosen by a greedy criterion. It is studied whether the approximations $f_n$ are in some sense comparable to {\em best $n$ term approximation} from the dictionary. One important result related to this question is a theorem of Zhang \cite{TZ} in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers $n$ -sparse signal, whenever the dictionary $\mathcal{D}$ satisfies a Restricted Isometry Property (RIP) of order $An$ for some constant $A$ , and that the procedure is also stable in $\ell^2$ under measurement noise. The main contribution of the present paper is to give a structurally simpler proof of Zhang's theorem, formulated in the general context of $n$ term approximation from a dictionary in arbitrary Hilbert spaces $\mathcal{H}$ . Namely, it is shown that OMP generates near best $n$ term approximations under a similar RIP condition.

preprint2015arXiv

Sparse polynomial approximation of parametric elliptic PDEs. Part II: lognormal coefficients

Elliptic partial differential equations with diffusion coefficients of lognormal form, that is $a=exp(b)$ , where $b$ is a Gaussian random field, are considered. We study the $\ell^p$ summability properties of the Hermite polynomial expansion of the solution in terms of the countably many scalar parameters appearing in a given representation of $b$ . These summability results have direct consequences on the approximation rates of best $n$ -term truncated Hermite expansions. Our results significantly improve on the state of the art estimates available for this problem. In particular, they take into account the support properties of the basis functions involved in the representation of $b$ , in addition to the size of these functions. One interesting conclusion from our analysis is that in certain relevant cases, the Karhunen-Loève representation of $b$ may not be the best choice concerning the resulting sparsity and approximability of the Hermite expansion.

preprint2014arXiv

Classification algorithms using adaptive partitioning

Algorithms for binary classification based on adaptive tree partitioning are formulated and analyzed for both their risk performance and their friendliness to numerical implementation. The algorithms can be viewed as generating a set approximation to the Bayes set and thus fall into the general category of set estimators. In contrast with the most studied tree-based algorithms, which utilize piecewise constant approximation on the generated partition [IEEE Trans. Inform. Theory 52 (2006) 1335-1353; Mach. Learn. 66 (2007) 209-242], we consider decorated trees, which allow us to derive higher order methods. Convergence rates for these methods are derived in terms the parameter $α$ of margin conditions and a rate $s$ of best approximation of the Bayes set by decorated adaptive partitions. They can also be expressed in terms of the Besov smoothness $β$ of the regression function that governs its approximability by piecewise polynomials on adaptive partition. The execution of the algorithms does not require knowledge of the smoothness or margin conditions. Besov smoothness conditions are weaker than the commonly used Hölder conditions, which govern approximation by nonadaptive partitions, and therefore for a given regression function can result in a higher rate of convergence. This in turn mitigates the compatibility conflict between smoothness and margin parameters.

preprint2014arXiv

Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

A recurring theme in attempts to break the curse of dimensionality in the numerical approximations of solutions to high-dimensional partial differential equations (PDEs) is to employ some form of sparse tensor approximation. Unfortunately, there are only a few results that quantify the possible advantages of such an approach. This paper introduces a class $Σ_n$ of functions, which can be written as a sum of rank-one tensors using a total of at most $n$ parameters and then uses this notion of sparsity to prove a regularity theorem for certain high-dimensional elliptic PDEs. It is shown, among other results, that whenever the right-hand side $f$ of the elliptic PDE can be approximated with a certain rate $\mathcal{O}(n^{-r})$ in the norm of ${\mathrm H}^{-1}$ by elements of $Σ_n$ , then the solution $u$ can be approximated in ${\mathrm H}^1$ from $Σ_n$ to accuracy $\mathcal{O}(n^{-r'})$ for any $r'\in (0,r)$ . Since these results require knowledge of the eigenbasis of the elliptic operator considered, we propose a second "basis-free" model of tensor sparsity and prove a regularity theorem for this second sparsity model as well. We then proceed to address the important question of the extent such regularity theorems translate into results on computational complexity. It is shown how this second model can be used to derive computational algorithms with performance that breaks the curse of dimensionality on certain model high-dimensional elliptic PDEs with tensor-sparse data.

preprint2012arXiv

Greedy Algorithms for Reduced Bases in Banach Spaces

Given a Banach space X and one of its compact sets F, we consider the problem of finding a good n dimensional space X_n \subset X which can be used to approximate the elements of F. The best possible error we can achieve for such an approximation is given by the Kolmogorov width d_n(F)_X. However, finding the space which gives this performance is typically numerically intractable. Recently, a new greedy strategy for obtaining good spaces was given in the context of the reduced basis method for solving a parametric family of PDEs. The performance of this greedy algorithm was initially analyzed in A. Buffa, Y. Maday, A.T. Patera, C. Prud'homme, and G. Turinici, "A Priori convergence of the greedy algorithm for the parameterized reduced basis", M2AN Math. Model. Numer. Anal., 46(2012), 595-603 in the case X = H is a Hilbert space. The results there were significantly improved on in P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk, "Convergence rates for greedy algorithms in reduced bases Methods", SIAM J. Math. Anal., 43 (2011), 1457-1472. The purpose of the present paper is to give a new analysis of the performance of such greedy algorithms. Our analysis not only gives improved results for the Hilbert space case but can also be applied to the same greedy procedure in general Banach spaces.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ronald DeVore

Research overview

Is this your work?

15 publications

Neural Network Approximation

Nonlinear Methods for Model Reduction

Optimal Stable Nonlinear Approximation

Polynomial Approximation of Anisotropic Analytic Functions of Several Variables

Reduced Basis Greedy Selection Using Random Training Sets

Data Assimilation and Sampling in Banach spaces

Diffusion Coefficients Estimation for Elliptic Partial Differential Equations

Approximation of high-dimensional parametric PDEs

Data Assimilation in Reduced Modeling

Kolmogorov widths under holomorphic mappings

Orthogonal Matching Pursuit under the Restricted Isometry Property

Sparse polynomial approximation of parametric elliptic PDEs. Part II: lognormal coefficients

Classification algorithms using adaptive partitioning

Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

Greedy Algorithms for Reduced Bases in Banach Spaces

See the researcher in context

Building this map preview