Research Highlight


Hyperspherical sparse approximation for high-dimensional discontinuity detection

Achievement

This work proposes a hyperspherical sparse approximation framework for detecting jump discontinuities in functions in high-dimensional spaces. The need for a novel approach results from the theoretical and computational inefficiencies of well-known approaches, such as adaptive sparse grids, for discontinuity detection. Our approach constructs the hyper- spherical coordinate representation of the discontinuity surface of a function. Then sparse approximations of the transformed function are built in the hyperspherical coordinate sys- tem, with values at each point estimated by solving a one-dimensional discontinuity detection problem. Due to the smoothness of the hypersurface, the new technique can identify jump discontinuities with significantly reduced computational cost, compared to existing methods. Several approaches are used to approximate the transformed discontinuity surface in the hyperspherical system, including adaptive sparse grid and radial basis function interpolation, discrete least squares projection, and compressed sensing approximation. Moreover, hierarchical acceleration techniques are also incorporated to further reduce the overall complexity. Rigorous complexity analyses of the new methods are provided, as are several numerical examples that illustrate the effectiveness of our approach.

Figure: Comparison between the standard sparse grid method and our hyperspherical sparse grid method in capturing the discontinuity surface (i.e., the 3D unit sphere). To achieve the same accuracy, the standard sparse grid requires about 100K points while our method only needs about 150 points. 

Publications: