FoCM 2014 conference
Session B1 - Approximation Theory
Organizers: Nira Dyn (Tel-Aviv University, Israel) - Tom Lyche (University of Oslo, Norway) - Holger Wendland (University of Oxford, USA)
Talks
December 16, 15:30 ~ 15:55 - Room B21
Tree Algorithms for Classification
Peter Binev
University of South Carolina , USA - binev@math.sc.edu
The solution of the problem of binary classification is often presented as a set of points at which one predicts a positive outcome assuming that a negative outcome is expected at the points of the complement set. Given a family of sets the goal is to find an element for which the risk of misclassification is as small as possible. We want to find an effective algorithm that based on a collection of query points identifies with high probability a good approximation in terms of minimizing the risk. As usual, no prior knowledge is assumed about the underlying probability measure related to the classification. We consider families of sets defined via tree structures and propose a convergence analysis based on nonlinear approximation theory, which allows us to significantly weaken the usual assumptions that are made to establish a given convergence rate. Algorithms using occupancy trees and decorated trees are presented to show one possible efficient realization of the general theory.
December 16, 18:00 ~ 18:25 - Room B21
Estimating the $n$-width of solution manifolds of parametric PDE's
Albert Cohen
Université Paris VI, France - cohen@ann.jussieu.fr
Numerous computational model reduction methods, such as reduced basis and its generalization, proper orthogonal decomposition, generalized empirical interpolation, rely on the implicit assumption that the solution manifold, that gathers the solution to a PDE as parameters vary, can be well approximated by low dimensional spaces. This is made more precise by assuming that the Kolmogorov $n$-width of the manifold has certain decay. In this talk, I shall discuss strategies that allow to rigorously establish rates of decay for the Kolmogorov $n$-width of solution manifolds associated with relevant parametric PDE’s, where the parameters are infinite dimensional. One key result is that the rate of decay of $n$-width of sets in Banach space is almost preserved under the action of holomorphic maps.
Joint work with Ronald DeVore (Texas A&M University).
December 15, 14:35 ~ 15:25 - Room A12
Greedy approximation of a solution manifold
Wolfgang Dahmen
RWTH Aachen, Germany - dahmen@igpm.rwth-aachen.de
Many design or optimization tasks in scientific computation require a frequent(even online) evaluation of solutions to parameter dependent families of partial differential equations describing the underlying model. This is often only feasible when the model is suitably reduced. The so called Reduced Basis Method is a model reduction paradigm that has recently been attracting considerable attention since it aims at certifying the quality of the reduced model through a-posteriori error bounds. The central idea is to approximate the solution manifold, comprised of all solutions obtained when the parameters range over the given parameter domain by the linear hull of possibly few snapshots from that manifold so as to still guarantee that the maximal error stays below a given target tolerance. Each parameter query, e.g. in an optimization process, requires then only solving a relatively small problem in the reduced space. This can be viewed as finding a problem dependent dictionary with respect to which all solutions are nearly sparse. This talk highlights the basic ideas behind this method. In particular, it is indicated under which circumstances certain greedy strategies for finding the generating snapshots are optimal in the sense that the corresponding subspaces realize the rate of the Kolmogorov n-widths even for problem classes not covered by conventional strategies.
December 16, 14:35 ~ 15:25 - Room B21
Wavelet decompositions of Random Forests
Shai Dekel
GE Global Research & Tel-Aviv University, Israel - Shai.Dekel@GE.com
In the talk we will review how Approximation Theory can be applied to solve some of the challenges of Machine Learning. Tools such as the tree-based Random Forest and the Gradient Boosting Machine are popular and powerful machine learning algorithms that are also employed as part of 'Deep Learning' systems. Constructing the right form of wavelet decomposition of these tools allows establishing ordering of their decision nodes: from `significant' features to `less significant' to `insignificant' noise. Consequently, simple wavelet techniques can be used to overcome the presence of noise and misclassifications in the training sets and compress large scale neural networks.
December 16, 16:00 ~ 16:25 - Room B21
Using Semidefinite Programming in Approximation Theory
Simon Foucart
University of Georgia, USA - foucart@math.uga.edu
This talk reports on some ongoing work that uncovers many semidefinite relaxations to classic Approximation Theory problems. These include best approximations in the max-norm by trigonometric polynomials, algebraic polynomials, rational functions, and splines. One may deal with unconstrained, one-sided, monotone, or simultaneous approximations alike. Solving the associated semidefinite programs numerically gives new insight on various results and conjectures.
December 15, 16:00 ~ 16:25 - Room A12
Convolution operations in curve and surface modeling
Thomas Grandine
Boeing Computer Services, USA - thomas.a.grandine@boeing.com
Motivated by the need to develop empirical models of cured composite laminated parts, convolution-based techniques of smoothing curve and surface models have recently been investigated. These convolution operations for tensor product splines have been found to be very effective, not only for building the intended models, but also for modeling tooling and machining. The technique so far appears to be very promising, and it appears to offer the potential to solve some of the data complexity issues that arise in the practical modeling of real world manufactured parts. This talk will describe the investigations that have so far been performed and offer ideas for further development
December 17, 17:05 ~ 17:55 - Room A12
Recent progress on boundary effects in kernel approximation
Thomas Hangelbroek
University of Hawai, USA - hangelbr@math.hawaii.edu
The existence of a boundary in kernel approximation is known to drive down rates of convergence { in many cases, using kernels with centers restricted to a bounded domain causes approximation orders to be saturated at a low rate (roughly half the rate of the corresponding boundary-free rates). Another unpleasant e ect is that although alternative bases like Lagrange and local Lagrange functions are known to be stable and well-localized in boundary-free kernel approximation, the proof of this fact does not generalize to re- gions with boundary. Indeed, there is strong evidence that in the presence of a boundary, Lagrange functions decay at a rate that is too slow to be useful. In this talk we present recent advances in kernel approximation that treat both of the aforementioned boundary e ects. We begin by discussing approximation results that over- come the low saturation order imposed by the boundary. This is an expansion from the previously understood case of surface splines on Euclidean regions to more general kernels acting on Riemannian manifolds. We follow this by presenting local basis constructions for bounded regions which yield Lp-stability results and Bernstein inequalities.
December 17, 15:35 ~ 16:25 - Room A12
$\alpha$-Molecules: Wavelets, Shearlets, and beyond
Gitta Kutyniok
Technische Universität Berlin), Germany - kutyniok@math.tu-berlin.de
The area of applied harmonic analysis provides a variety of multiscale systems such as wavelets, curvelets, shearlets, or ridgelets. A distinct property of each of those systems is the fact that it sparsely approximates a particular class of functions. Some of these systems even share similar approximation properties such as curvelets and shearlets which both optimally sparsely approximate functions governed by curvilinear features, a fact that is usually proven on a case-by-case basis for each different construction. The recently developed framework of parabolic molecules, which includes all known anisotropic frame constructions based on parabolic scaling, provides a unified concept for a sparse approximation results of such systems.
In this talk we will introduce the novel concept of $\alpha$-molecules which allows for a unified framework encompassing most multiscale systems from the area of applied harmonic analysis with the parameter $\alpha$ serving as a measure for the degree of anisotropy. The main result essentially states that the cross-Gramian of two systems with the same degree of anisotropy exhibits a strong off-diagonal decay. One main consequence we will discuss is that all such systems then share similar approximation properties, and desirable approximation properties of one can be deduced for virtually any other system with the same degree of anisotropy.
Joint work with P. Grohs (ETH Zurich), S. Keiper (TU Berlin) and M. Schäfer (TU Berlin).
December 16, 17:05 ~ 17:55 - Room B21
Weighted D-T moduli revisited and applied
Dany Leviatan
Tel Aviv University, Israel - leviatan@math.tau.ac.il
We introduce weighted moduli of smoothness for functions $f\in L_p[-1,1]\cap C^{r-1}(-1,1)$ $r\ge 1$, that have an $(r-1)$st absolutely continuous derivative in $(-1,1)$ and such that $\varphi^rf^r\in L_p[-1,1]$, where $\varphi(x)=(1-x^2)^{1/2}$. These moduli are equivalent to certain weighted D-T moduli, but our definition is more transparent and simpler. In addition, instead of applying these weighted moduli to weighted approximation, which was the purpose of the original D-T moduli, we apply these moduli to obtain Jackson-type estimates on the approximation of functions in $L_p[-1,1]$ (no weight), by means of algebraic polynomials. We also have inverse theorems that yield characterization of the behavior of the derivatives of the function by means of its degree of approximation.
Joint work with K. Kopotun (University of Manitoba, Canada) and I. A. Shevchuk (Ukrainian National Academy of Sciences, Kiev).
December 15, 15:30 ~ 15:55 - Room A12
Approximation of freeform surfaces with polyhedral patterns
Helmut Pottmann
KAUST, Saudi Arabia, and TU Wien, Austria - pottmann@geometrie.tuwien.ac.at
Polyhedral meshes, i.e. meshes with planar faces, recently received a lot of interest because of their potential applications in architecture and industrial design. Avoiding triangle meshes because of their high node complexity, research concentrated mainly on polyhedral quad meshes. They possess an elegant treatment within discrete diff erential geometry and are capable of approximating arbitrary shapes. However, they are strongly linked to the curvature behavior of the surfaces to be approximated and may not possess sufficient flexibility to satisfy the design intent. As an alternative, various types of patterns diff erent from the quad grid have been investigated, both in real projects and in geometric computing. We report on our recent progress on polyhedral meshes which are combinatorially equivalent to well-known 2D patterns, analyze their flexibility in approximating freeform shapes, discuss ways to handle the arising new forms of smoothness and suggest a computational framework suitable for interactive design and approximation.
Joint work with Caigui Jiang, Jun Wang, Chengcheng Tang, Peter Wonka and Johannes Wallner.
December 17, 18:00 ~ 18:25 - Room A12
Series kernels for high dimensional reconstruction problems
Christian Rieger
University of Bonn, Germany - rieger@ins.uni-bonn.de
In this talk, we will discuss series kernels and their applications in high dimensional problems. In many problems we are able to determine an application-adapted reproducing kernel which is however typically not available in closed form. This makes it necessary to approximate the kernel itself. In most cases, one can derive an infinite series expansion of the kernel. For numerical purposes, however, this infinite series has to be truncated. We will present some approximation properties of kernel methods based on such truncated kernels. Further, we present how such series expansion can be obtained from the application. As a model problem, we will focus on parametric partial differential equations as they appear in the field of uncertainty quantification. As the resulting kernels are in many cases smooth, we are able to show exponential convergence rates in the parameter discretization. Furthermore we use sampling inequalities to analyze non-intrusive methods. In particular, we derive error estimates which contain the error of solving the partial differential equation for a fixed parameter. This allows us to couple these two errors and to derive a final convergence rate.
December 17, 14:35 ~ 15:25 - Room A12
Stable reconstruction from Fourier samples
Alexei Shadrin
University of Cambridge, UK - A.Shadrin@dampt.cam.ac.uk
For an analytic and periodic function $f$, the $m$-th partial sums of its Fourier series converge exponentially fast in $m$, but such rapid convergence is destroyed once periodicity is no longer present (because of the Gibbs phenomenon at the end-points).
We can restore higher-order convergence, e.g., by reprojecting the slowly convergent Fourier series onto a suitable basis of orthogonal algebraic polynomials, however, all exponentially convergent methods appear to suffer from some sort of ill-conditioning, whereas methods that recover $f$ in a stable manner have a much slower approximation rate.
We give to these observations a definite explanation in terms of the following fundamental stability barrier: the best possible convergence rate for a stable reconstruction from the first $m$ Fourier coefficients is root-exponential in $m$.
December 15, 17:05 ~ 17:55 - Room A12
Linear Differential Operators on Spline Spaces and Spline Vector Fields
Tatyana Sorokina
Towson University, USA - tsorokina@towson.edu
We consider the application of standard differentiation operators to polynomial spline spaces and spline vector fields defined on triangulations. In particular, we explore the use of Bernstein Bézier techniques for answering questions such as: what are the images or the kernels, and their dimensions, of partial derivative, gradient, divergence, curl, or Laplace, operators. We also describe applications of our results to finite element methods.
Joint work with Peter Alfeld (University of Utah).
December 15, 18:00 ~ 18:25 - Room A12
Algebraic tools for the study of spline spaces
Nelly Villamizar
RICAM, Austria - nvillami@gmail.com
A spline space attached to a partitioned domain is the vector space of functions which are polynomials (up to certain degree) on each piece of the partition and have a fixed order of global smoothness. In this talk, we will address the problem of finding the dimension of the spline space associated to a triangulation or a tetrahedral partition of a region in the plane or in the three dimensional space, respectively. Applying homological techniques and exploring connections of splines with ideals generated by powers of linear forms, we establish formulas for lower and upper bounds on the dimension of the spline space for any given degree and order of smoothness. The homological construction gives an insight into ways of computing the exact dimension for a given partition, and brings to light connections between the theory of splines and classical problems in algebraic geometry.