检索结果-内蒙古大学图书馆

Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning functions of Many Variables

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2021年第2期21卷 275-329页

作者： Choi, Bosu Iwen, Mark A. Krahmer, Felix UT Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI 48824 USA Tech Univ Munich Dept Math Munich Germany

In this paper we develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms of general bounded orthonormal tensor product bases. Such functions appear in many applications including, e.g., various Uncertainty Quantification (UQ) problems involving the solution of parametric PDE that are approximately sparse in Chebyshev or Legendre product bases (Chkifa et al. in Polynomial approximation via compressed sensing of high-dimensional functions on lower sets., 2016;Rauhut and Schwab in Math Comput 86(304):661-700, 2017). We expect that our results provide a starting point for a new line of research on sublinear-time solution techniques for UQ applications of the type above which will eventually be able to scale to significantly higher-dimensional problems than what are currently computationally feasible. More concretely, let B be a finite Bounded Orthonormal Product Basis (BOPB) of cardinality vertical bar B vertical bar = N. Herein we will develop methods that rapidly approximate any functionfthat is sparse in the BOPB, that is,f: D subset of R-D -> C of the form f(x)= Sigma(b is an element of S) c(b)center dot b(x) with S subset of B of cardinality vertical bar S vertical bar = s << N. Our method adapts the CoSaMP algorithm (Needell and Tropp in Appl Comput Harmon Anal 26(3):301-321, 2009) to use additional function samples fromfalong a randomly constructed grid G subset of R-D with universal approximation properties in order to rapidly identify the multi-indices of the most dominant basis functions in S component by component during each CoSaMP iteration. It has a runtime of just(slogN)O(1), uses only(slogN)O(1) function evaluations on the fixed and nonadaptive grid G, and requires not more than(slogN)O(1) bits of memory. We emphasize that nothing about S or any of the coefficientscb is an element of Cis assumed in advance other than that S subset of B has |S| <= s. Both S and its related coe

关键词： high-dimensional function approximation Sublinear-time algorithms function learning Sparse approximation Compressive sensing

来源：评论

学校读者我要写书评

暂无评论

GRADIENT-BASED DIMENSION REDUCTION OF MULTIVARIATE VECTOR-VALUED functionS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2020年第1期42卷 A534-A558页

作者： Zahm, Olivier Constantine, Paul G. Prieur, Clementine Marzouk, Youssef M. Univ Grenoble Alpes Inria CNRS Grenoble INPInst EngnLJK F-38000 Grenoble France Univ Colorado Boulder CO 80309 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

Multivariate functions encountered in high-dimensional uncertainty quantification problems often vary most strongly along a few dominant directions in the input parameter space. We propose a gradient-based method for detecting these directions and using them to construct ridge approximations of such functions, in the case where the functions are vector-valued (e.g., taking values in R-n). The methodology consists of minimizing an upper bound on the approximation error, obtained by subspace Poincar'e inequalities. We provide a thorough mathematical analysis in the case where the parameter space is equipped with a Gaussian probability measure. The resulting method generalizes the notion of active subspaces associated with scalar-valued functions. A numerical illustration shows that using gradients of the function yields effective dimension reduction. We also show how the choice of norm on the codomain of the function has an impact on the function's low-dimensional approximation.

关键词： high-dimensional function approximation dimension reduction ridge approximation active subspace Sobol' indices Poincare inequality

来源：评论

学校读者我要写书评

暂无评论

Sparse Spectral Methods for Solving high-dimensional and Multiscale Elliptic PDEs

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2024年第3期25卷 765-811页

作者： Gross, Craig Iwen, Mark Michigan State Univ Dept Math 619 Red Cedar Rd East E Lansing MI 48824 USA Michigan State Univ Dept Computat Math Sci & Engn 428 S Shaw Lane E Lansing MI 48824 USA

In his monograph Chebyshev and Fourier Spectral Methods, John Boyd claimed that, regarding Fourier spectral methods for solving differential equations, "[t]he virtues of the Fast Fourier Transform will continue to improve as the relentless march to larger and larger [bandwidths] continues" [Boyd in Chebyshev and Fourier spectral methods, second rev ed. Dover Publications, Mineola, NY, 2001, pg. 194]. This paper attempts to further the virtue of the Fast Fourier Transform (FFT) as not only bandwidth is pushed to its limits, but also the dimension of the problem. Instead of using the traditional FFT however, we make a key substitution: a high-dimensional, sparse Fourier transform paired with randomized rank-1 lattice methods. The resulting sparse spectral method rapidly and automatically determines a set of Fourier basis functions whose span is guaranteed to contain an accurate approximation of the solution of a given elliptic PDE. This much smaller, near-optimal Fourier basis is then used to efficiently solve the given PDE in a runtime which only depends on the PDE's data compressibility and ellipticity properties, while breaking the curse of dimensionality and relieving linear dependence on any multiscale structure in the original problem. Theoretical performance of the method is established herein with convergence analysis in the Sobolev norm for a general class of non-constant diffusion equations, as well as pointers to technical extensions of the convergence analysis to more general advection-diffusion-reaction equations. Numerical experiments demonstrate good empirical performance on several multiscale and high-dimensional example problems, further showcasing the promise of the proposed methods in practice.

关键词： Spectral methods Sparse Fourier transforms high-dimensional function approximation Elliptic partial differential equations Compressive sensing Rank-1 lattices

来源：评论

学校读者我要写书评

暂无评论

A machine learning approach to optimal Tikhonov regularization I: Affine manifolds

引用

ANALYSIS AND APPLICATIONS 2022年第2期20卷 353-400页

作者： De Vito, Ernesto Fornasier, Massimo Naumova, Valeriya Univ Genoa DIMA Via Dodecaneso 35 I-16146 Genoa Italy Univ Genoa MaLGa Via Dodecaneso 35 I-16146 Genoa Italy Tech Univ Munich Fak Math Boltzmannstr 3 D-85748 Garching Germany Simula Res Lab Martin Linges Vei 25 N-1364 Fornebu Norway

Despite a variety of available techniques, such as discrepancy principle, generalized cross validation, and balancing principle, the issue of the proper regularization parameter choice for inverse problems still remains one of the relevant challenges in the field. The main difficulty lies in constructing an efficient rule, allowing to compute the parameter from given noisy data without relying either on any a priori knowledge of the solution, noise level or on the manual input. In this paper, we propose a novel method based on a statistical learning theory framework to approximate the high-dimensional function, which maps noisy data to the optimal Tikhonov regularization parameter. After an offline phase where we observe samples of the noisy data-to-optimal parameter mapping, an estimate of the optimal regularization parameter is computed directly from noisy data. Our assumptions are that ground truth solutions of the inverse problem are statistically distributed in a concentrated manner on (lower-dimensional) linear subspaces and the noise is sub-gaussian. We show that for our method to be efficient, the number of previously observed samples of the noisy data-to-optimal parameter mapping needs to scale at most linearly with the dimension of the solution subspace. We provide explicit error bounds on the approximation accuracy from noisy data of unobserved optimal regularization parameters and ground truth solutions. Even though the results are more of theoretical nature, we present a recipe for the practical implementation of the approach. We conclude with presenting numerical experiments verifying our theoretical results and illustrating the superiority of our method with respect to several state-of-the-art approaches in terms of accuracy or computational time for solving inverse problems of various types.

关键词： Tikhonov regularization parameter choice rule sub-gaussian vectors high-dimensional function approximation concentration inequalities

来源：评论

学校读者我要写书评

暂无评论

Learning functions of Few Arbitrary Linear Parameters in high Dimensions

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2012年第2期12卷 229-262页

作者： Fornasier, Massimo Schnass, Karin Vybiral, Jan Tech Univ Munich Fac Math D-85748 Garching Germany Austrian Acad Sci Johann Radon Inst Computat & Appl Math A-4040 Linz Austria

Let us assume that f is a continuous function defined on the unit ball of R-d, of the form f(x) = g(Ax), where A is a k x d matrix and g is a function of k variables for k << d. We are given a budget m is an element of N of possible point evaluations f(x(i)), i = 1, ... , m, of f, which we are allowed to query in order to construct a uniform approximating function. Under certain smoothness and variation assumptions on the function g, and an arbitrary choice of the matrix A, we present in this paper 1. a sampling choice of the points {x(i)} drawn at random for each function approximation;2. algorithms (Algorithm 1 and Algorithm 2) for computing the approximating function, whose complexity is at most polynomial in the dimension d and in the number m of points. Due to the arbitrariness of A, the sampling points will be chosen according to suitable random distributions, and our results hold with overwhelming probability. Our approach uses tools taken from the compressed sensing framework, recent Chernoff bounds for sums of positive semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.

关键词： high-dimensional function approximation Compressed sensing Chernoff bounds for sums of positive semidefinite matrices Stability bounds for invariant subspaces of singular value decompositions

来源：评论

学校读者我要写书评

暂无评论

Sparse harmonic transforms II: bests-term approximation guarantees for bounded orthonormal product bases in sublinear-time

引用

NUMERISCHE MATHEMATIK 2021年第2期148卷 293-362页

作者： Choi, Bosu Iwen, Mark Volkmer, Toni Univ Texas Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI 48824 USA Tech Univ Chemnitz Fac Math Chemnitz Germany

In this paper we develop a sublinear-time compressive sensing algorithm for approximating functions of many variables which are compressible in a given Bounded Orthonormal Product Basis (BOPB). The resulting algorithm is shown to both have an associated best s-term recovery guarantee in the given BOPB, and also to work well numerically for solving sparse approximation problems involving functions contained in the span of fairly general sets of as many as similar to 10(230) orthonormal basis functions. All code is made publicly available. As part of the proof of the main recovery guarantee new variants of the well known CoSaMP algorithm are proposed which can utilize any sufficiently accurate support identification procedure satisfying a Support Identification Property (SIP) in order to obtain strong sparse approximation guarantees. These new CoSaMP variants are then proven to have both runtime and recovery error behavior which are largely determined by the associated runtime and error behavior of the chosen support identification method. The main theoretical results of the paper are then shown by developing a sublinear-time support identification algorithm for general BOPB sets which is robust to arbitrary additive errors. Using this new support identification method to create a new CoSaMP variant then results in a new robust sublinear-time compressive sensing algorithm for BOPB-compressible functions of many variables.

关键词： high-dimensional function approximation Sublinear-time algorithms function learning Sparse approximation Compressive Sensing Sparse Fourier transforms (SFT)

来源：评论

学校读者我要写书评

暂无评论

On some aspects of approximation of ridge functions

引用

JOURNAL OF approximation THEORY 2015年 194卷 35-61页

作者： Kolleck, Anton Vybiral, Jan Tech Univ Berlin Math Inst D-10623 Berlin Germany Charles Univ Prague Dept Math Anal Prague 18600 8 Czech Republic

We present effective algorithms for uniform approximation of multivariate functions satisfying some prescribed inner structure. We extend, in several directions, the analysis of recovery of ridge functions f (x) = g (< a, x >) as performed earlier by one of the authors and his coauthors. We consider ridge functions defined on the unit cube [-1, 1](d) as well as recovery of ridge functions defined on the unit ball from noisy measurements. We conclude with the study of functions of the type f (x) = g (parallel to a - x parallel to(2)(l2d)). (C) 2015 Elsevier Inc. All rights reserved.

关键词： Ridge functions high-dimensional function approximation Noisy measurements Compressed sensing Dantzig selector

来源：评论

学校读者我要写书评

暂无评论

The recovery of ridge functions on the hypercube suffers from the curse of dimensionality

引用

JOURNAL OF COMPLEXITY 2021年 63卷 101521-101521页

作者： Doerr, Benjamin Mayer, Sebastian Inst Polytech Paris Lab Informat LIX Ecole Polytech CNRS Palaiseau France Fraunhofer Ctr Machine Learning D-53754 St Augustin Germany Fraunhofer Inst Algorithms & Sci Comp SCAI D-53754 St Augustin Germany

A multivariate ridge function is a function of the form f (x) = g(a(T) x), where g is univariate and a is an element of R-d. We show that the recovery of an unknown ridge function defined on the hypercube [-1, 1](d) with Lipschitz-regular profile g suffers from the curse of dimensionality when the recovery error is measured in the L-infinity-norm, even if we allow randomized algorithms. If a limited number of components of a is substantially larger than the others, then the curse of dimensionality is not present and the problem is weakly tractable, provided the profile g is sufficiently regular. (C) 2020 Elsevier Inc. All rights reserved.

关键词： high-dimensional function approximation Ridge functions Randomized algorithms Lower bounds Information-based complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：