High Dimensional Approximation via Sparse Occupancy Trees

Duration: 42 mins 27 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/3007769/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Binev, P Monday 17th June 2019 - 14:20 to 15:10


Created:	2019-06-18 09:22
Collection:	Approximation, sampling, and compression in high dimensional problems
Publisher:	Isaac Newton Institute
Copyright:	Binev, P
Language:	eng (English)


Abstract:	Adaptive domain decomposition is often used in finite elements methods for solving partial differential equations in low space dimensions. The adaptive decisions are usually described by a tree. Assuming that can find the (approximate) error for approximating a function on each element of the partition, we have shown that a particular coarse-to-fine method provides a near-best approximation. This result can be extended to approximating point clouds any space dimension provided that we have relevant information about the errors and can organize properly the data. Of course, this is subject to the curse of dimensionality and nothing can be done in the general case. In case the intrinsic dimensionality of the data is much smaller than the space dimension, one can define algorithms that defy the curse. This is usually done by assuming that the data domain is close to a low dimensional manifold and first approximating this manifold and then the function defined by it. A few years ago, together with Philipp Lamby, Wolfgang Dahmen, and Ron DeVore, we proposed a direct method (without specifically identifying any low dimensional set) that we called "sparse occupancy trees". The method defines a piecewise constant or linear approximation on general simplicial partitions. This talk considers an extension of this method to find a similar approximation on conforming simplicial partitions following an idea from a recent result together with Francesca Fierro and Andreas Veeser about near-best approximation on conforming triangulations.

Abstract:

Adaptive domain decomposition is often used in finite elements methods for solving partial differential equations in low space dimensions. The adaptive decisions are usually described by a tree. Assuming that can find the (approximate) error for approximating a function on each element of the partition, we have shown that a particular coarse-to-fine method provides a near-best approximation. This result can be extended to approximating point clouds any space dimension provided that we have relevant information about the errors and can organize properly the data. Of course, this is subject to the curse of dimensionality and nothing can be done in the general case. In case the intrinsic dimensionality of the data is much smaller than the space dimension, one can define algorithms that defy the curse. This is usually done by assuming that the data domain is close to a low dimensional manifold and first approximating this manifold and then the function defined by it. A few years ago, together with Philipp Lamby, Wolfgang Dahmen, and Ron DeVore, we proposed a direct method (without specifically identifying any low dimensional set) that we called "sparse occupancy trees". The method defines a piecewise constant or linear approximation on general simplicial partitions. This talk considers an extension of this method to find a similar approximation on conforming simplicial partitions following an idea from a recent result together with Francesca Fierro and Andreas Veeser about near-best approximation on conforming triangulations.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.94 Mbits/sec	617.91 MB	View	Download
WebM	640x360	599.01 kbits/sec	186.24 MB	View	Download
iPod Video	480x270	522.1 kbits/sec	162.33 MB	View	Download
MP3	44100 Hz	249.77 kbits/sec	77.72 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)