Complexity of approximation of functions of few variables in high dimensions
From MaRDI portal
Publication:2431335
DOI10.1016/j.jco.2011.01.004zbMath1343.65015OpenAlexW1996674925MaRDI QIDQ2431335
Publication date: 13 April 2011
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2011.01.004
Algorithms for approximation of functions (65D15) Complexity and performance of numerical algorithms (65Y20)
Related Items (7)
A Survey of Compressed Sensing ⋮ Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points ⋮ \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations ⋮ On \(n\)-widths of a Sobolev function class in Orlicz spaces ⋮ Information based complexity for high dimensional sparse functions ⋮ Sampling schemes and recovery algorithms for functions of few coordinate variables ⋮ On some aspects of approximation of ridge functions
Cites Work
- Learning functions of few arbitrary linear parameters in high dimensions
- Approximation of functions of few variables in high dimensions
- Best subset selection, persistence in high-dimensional statistical learning and optimization under \(l_1\) constraint
- Tractability of multivariate problems. Volume I: Linear information
- On sets of Boolean \(n\)-vectors with all \(k\)-projections surjective
- New bounds for perfect hashing via information theory
- Finite-order weights imply tractability of linear multivariate problems
- Sperner capacities
- Capturing ridge functions in high dimensions from point queries
- Diffusion wavelets
- Families of \(k\)-independent sets
- On the power of adaption
- On the Size of Separating Systems and Families of Perfect Hash Functions
- Compressed sensing and best 𝑘-term approximation
- Convergence rates for sparse chaos approximations of elliptic problems with stochastic coefficients
- Learning juntas
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Stable signal recovery from incomplete and inaccurate measurements
- Compressed sensing
This page was built for publication: Complexity of approximation of functions of few variables in high dimensions
