Hyperspherical sparse approximation techniques for high-dimensional discontinuity detection

Guannan Zhang, Clayton G. Webster, Max Gunzburger, John Burkardt

Research output: Contribution to journalReview articlepeer-review

17 Scopus citations

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 languageEnglish
Pages (from-to)517-551
Number of pages35
JournalSIAM Review
Volume58
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Hyperspherical sparse approximation techniques for high-dimensional discontinuity detection'. Together they form a unique fingerprint.

Cite this