Abstract
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 hyperspherical coordinate representation of the discontinuity surface of a function. Then sparse approximations of the transformed function are built in the hyperspherical coordinate system, 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.
Original language | English |
---|---|
Pages (from-to) | 517-551 |
Number of pages | 35 |
Journal | SIAM Review |
Volume | 58 |
Issue number | 3 |
DOIs | |
State | Published - 2016 |
Funding
This material is based upon work supported in part by the U.S. Air Force of Scientific Research under grants 1854-V521-12 and FA9550-15-1-0001; the U.S. Defense Advanced Research Projects Agency, Defense Sciences Office under contract and award HR0011619523 and 1868-A017-15; the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contracts and awards ERKJ259, ERKJE45, and DE-SC0010678; and by the Laboratory Directed Research and Development program at the Oak Ridge National Laboratory, which is operated by UT-Battelle, LLC., for the U.S. Department of Energy under contract DE-AC05-00OR22725.
Keywords
- Adaptive approximations
- Compressed sensing
- Discontinuity detection
- Discrete projection
- Hierarchical methods
- Hyperspherical coordinates
- Least squares
- Sparse grid interpolation