Sampling discretization and related problems
From MaRDI portal
Publication:2136857
DOI10.1016/j.jco.2022.101653zbMath1503.41001arXiv2109.07567OpenAlexW4214612440MaRDI QIDQ2136857
I. Limonova, Boris S. Kashin, Vladimir N. Temlyakov, Egor D. Kosov
Publication date: 16 May 2022
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.07567
learning theoryrandom matricessampling discretizationoperator norms of submatricesoptimal embedding of finite-dimensional subspaces
Interpolation in approximation theory (41A05) Rate of convergence, degree of approximation (41A25) Trigonometric polynomials, inequalities, extremal problems (42A05) Research exposition (monographs, survey articles) pertaining to approximations and expansions (41-02) Best constants in approximation theory (41A44)
Related Items
On sampling discretization in \(L_2\), Some improved bounds in sampling discretization of integral norms, A sharp upper bound for sampling numbers in \(L_2\), Random points are good for universal discretization, On the reconstruction of functions from values at subsampled quadrature points, Sampling discretization of integral norms and its application, Remarks on sampling discretization of integral norms of functions, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), On universal sampling recovery in the uniform norm, Sampling discretization error of integral norms for function classes with small smoothness, On the cardinality of lower sets and universal discretization, Sampling discretization of the uniform norm, Marcinkiewicz-Zygmund inequalities for polynomials in Fock space, Discretizing \(L_p\) norms and frame theory, Randomized weakly admissible meshes
Cites Work
- A mathematical introduction to compressive sensing
- Optimal asymptotic bounds for spherical designs
- Covariance estimation for distributions with \({2+\varepsilon}\) moments
- On generic chaining and the smallest singular value of random matrices with heavy tails
- Random reordering in SOR-type methods
- On Nikol'skii inequalities for domains in \({\mathbb {R}}^d\)
- Sums of random Hermitian matrices and an inequality by Rudelson
- Marcinkiewicz-Zygmund measures on manifolds
- User-friendly tail bounds for sums of random matrices
- Tractability of multivariate problems. Volume III: Standard information for operators
- How close is the sample covariance matrix to the actual covariance matrix?
- Approximating the moments of marginals of high-dimensional distributions
- Homogeneous polynomials on the ball and polynomial bases
- Sampling, Marcinkiewicz-Zygmund inequalities, approximation, and quadrature rules
- Sampling discretization of integral norms of the hyperbolic cross polynomials
- The entropy in learning theory. Error estimates
- \(L_{p}\)-moments of random vectors via majorizing measures
- Concentration of mass on convex bodies
- Marcinkiewicz-Zygmund inequalities
- On singular values of matrices with independent rows
- Tractability of multivariate problems. Volume I: Linear information
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- Embedding \(l_ p^ m\) into \(l_ 1^ n\)
- A survey of information-based complexity
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- Bounded orthogonal systems and the \(\Lambda\) (p)-set problem
- Deterministic and stochastic error bounds in numerical analysis
- Norms of random matrices
- On uncomplemented subspaces of \(L_p\), \(1<p<2\)
- The dimension of almost spherical sections of convex bodies
- Operator norms of submatrices
- Asymptotics and weighted estimates of Meixner polynomials orthogonal on the grid \(\{ 0,\delta,2\delta,\dots\}\)
- On a certain norm and related applications
- Random vectors in the isotropic position
- On the norms of polynomials in systems of periodic wavelets in the spaces \(L_p\)
- Contact points of convex bodies
- The Marcinkiewicz-type discretization theorems
- Universal discretization
- Chaining, interpolation and convexity II: the contraction principle
- On the existence of optimal meshes in every convex domain on the plane
- An elementary proof of the restricted invertibility theorem
- Approximation of smooth functions on compact two-point homogeneous spaces
- On the complexity of computing the \(L_q\) norm
- Almost orthogonal submatrices of an orthogonal matrix
- Approximation of zonoids by zonotopes
- A distribution-free theory of nonparametric regression
- Random linear combinations of functions from \(L_1\).
- On best \(m\)-term approximations and the entropy of sets in the space \(L^ 1\)
- Weighted polynomial inequalities with doubling and \(A_\infty\) weights
- Interpolation and integral norms of hyperbolic polynomials
- Function values are enough for \(L_2\)-approximation. II
- Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
- Geometric computation of Christoffel functions on planar convex domains
- Approximating \(L_p\) unit balls via random sampling
- On optimal recovery in \(L_2\)
- Marcinkiewicz-type discretization of \(L^p\)-norms under the Nikolskii-type inequality assumption
- Optimal pointwise sampling for \(L^2\) approximation
- \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace
- Decomposing a matrix into two submatrices with extremely small operator norm
- Worst-case recovery guarantees for least squares approximation using random samples
- Well-separated spherical designs
- Some nonlinear problems are as easy as the approximation problem
- Positive cubature formulas and Marcinkiewicz-Zygmund inequalities on spherical caps
- Multipliers, bases, and unconditional bases in the weighted spaces B and SB
- Decomposing a matrix into two submatrices with extremally small \((2,1)\)-norm
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- On approximate recovery of functions with bounded mixed derivative
- Efficient reconstruction of functions on the sphere from scattered data
- Feature selection for linear SVM with provable guarantees
- Greedy approximation with regard to non-greedy bases
- Approximation methods for supervised learning
- On the singular values of random matrices
- Multivariate polynomial inequalities with respect to doubling weights and \(A_{\infty}\) weights
- Sampling, splines and frames on compact manifolds
- Topics in multiplicative number theory
- On the interval of fluctuation of the singular values of random matrices
- Remarks on sampling discretization of integral norms of functions
- Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature
- On the mathematical foundations of learning
- A User's Guide to Measure Theoretic Probability
- On uniformly bounded bases in spaces of holomorphic functions
- Decomposing a matrix into two submatrices with smaller $ (2,1)$-norms
- Tight embedding of subspaces of ๐ฟ_{๐} in โ_{๐}โฟ for even ๐
- Polynomial interpolation and approximation in Cd
- Functions with Disconnected Spectrum
- Graphs, Vectors, and Matrices
- Embedding Subspaces of L 1 into l N 1
- Extensions of Pure States
- The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials
- Exponential frames on unbounded sets
- Lunin's method for selecting large submatrices with small norm
- Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
- Fine Embeddings of Finite Dimensional Subspaces of L p , 1 ๎บp < 2 into l m 1
- On values of homogeneous polynomials in discrete sets of points
- EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES
- Estimating the $ L_p$-norm of an algebraic polynomial in terms of its values at the nodes of a uniform grid
- The Growth of Polynomials Bounded at Equally Spaced Points
- DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
- Finite dimensional subspaces of $L_{p}$
- Extensions, Restrictions, and Representations of States on C โ - Algebras
- Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type
- The Behaviour of Legendre And Ultraspherical Polynomials in Lp-Spaces
- Random walks and anO*(n5) volume algorithm for convex bodies
- Multivariate Approximation
- Decomposing an orthogonal matrix into two submatrices with extremally small (2,1)-norm
- Restricted Invertibility Revisited
- Sample Covariance Matrices of Heavy-Tailed Distributions
- Random Sampling of Multivariate Trigonometric Polynomials
- Shannon sampling and function reconstruction from point values
- On Contact Points of Convex Bodies
- Continuous Frames and the Kadison-Singer Problem
- Optimal weighted least-squares methods
- ๐ฟ^{๐}-Bernstein inequalities on ๐ถยฒ-domains and applications to discretization
- A remark on entropy numbers
- Twice-Ramanujan Sparsifiers
- Integral norm discretization and related problems
- Tchakaloff polynomial meshes
- Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square
- Asymptotic Geometric Analysis, Part I
- Observations on discretization of trigonometric polynomials with given spectrum
- Pipage Rounding, Pessimistic Estimators and Matrix Concentration
- Upper and Lower Bounds for Stochastic Processes
- Sur l'interpolation (I)
- On Information and Sufficiency
- Concentration property on probability spaces.
- John's decompositions: Selecting a large part
- On the power of standard information for weighted approximation
- Estimates for norms of random polynomials and their application
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
