Empirical Approximation of L p L_{p} Norms
Feng Dai, Egor Kosov, Noel Murasko · 2026
Read Empirical Approximation of L p L_{p} Norms by Feng Dai, Egor Kosov, Noel Murasko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00347.txt.
Introduction
Dai, Kosov, and Murasko bound how well scant draws can match a norm of a chance vector. The Lp norm weights big parts more as p grows. Draw-based sums stand in for the true norm in many tools. The team gauge the worst gap twixt draw sums and true means.
Their bound rests on a fresh cap for a famed spread gauge. That cap beats the old chain-count bound in sharp terms. Two uses flow from the new cap. For high p, far fewer draws pin the norm on a whole space at once. For low p, draws give a sparse-isometry trait for bounded wave sets. Both marks near the best that chance draws can hope for.
Catalog record
| CREATOR | Feng Dai, Egor Kosov, Noel Murasko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Empirical Approximation of L p L_{p} Norms Thanks: The first and third authors were partially supported by NSERC of Canada Discovery Grant RGPIN 2026-05667. The second author was supported by AEI grant RYC2023-043616-I and by the Spanish State Research Agency through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). The second author also thanks CERCA Programme (Generalitat de Catalunya) for its institutional support. Feng Dai, Egor Kosov, Noel Murasko Abstract . We study empirical L p L_{p} moments of a random vector 𝝋 \boldsymbol{\varphi} based on its i.i.d. copies 𝝋 1 , … , 𝝋 m \boldsymbol{\varphi}^{1},\ldots,\boldsymbol{\varphi}^{m} , that is, 1 m ∑ j = 1 m | ⟨ 𝝋 j , y ⟩ | p \frac{1}{m}\sum_{j=1}^{m}|\langle\boldsymbol{\varphi}^{j},y\rangle|^{p} . Our main result is a new estimate for the expected uniform deviation 𝔼 sup y ∈ D | 1 m ∑ j = 1 m | ⟨ 𝝋 j , y ⟩ | p − 𝔼 | ⟨ 𝝋 , y ⟩ | p | \mathbb{E}\sup_{y\in D}\biggl|\frac{1}{m}\sum_{j=1}^{m}|\langle\boldsymbol{\varphi}^{j},y\rangle|^{p}-\mathbb{E}|\langle\boldsymbol{\varphi},y\rangle|^{p}\biggr| over an arbitrary index set D D . The proof is based on a new bound for Talagrand’s γ \gamma -functional, sharper than the standard Dudley-type entropy estimate. We then apply this estimate to the following two problems. First, for p > 2 p>2 , we study Marcinkiewicz-type discretization of L p L_{p} norms on an N N -dimensional subspace X N ⊂ B ( Ω ) X_{N}\subset B(\Omega) of bounded functions on a probability space ( Ω , μ ) (\Omega,\mu) . We obtain bounds in terms of the norm of the embedding ( X N , ∥ ⋅ ∥ L p ( μ ) ) ↪ B ( Ω ) . (X_{N},\|\cdot\|_{L_{p}(\mu)})\hookrightarrow B(\Omega). In particular, we prove that when this norm is of order N 1 / p N^{1/p} and m ⩾ C ( p ) N log N ( log log N ) p − 1 , m\geqslant C(p)\,N\log N\,(\log\log N)^{p-1}, then m m random samples suffice to approximate the L p ( μ ) L_{p}(\mu) norm uniformly on X N X_{N} by the sampled discrete L p L_{p} norm. This substantially improves the previously known bound in this setting m ⩾ C ( p ) N ( log N ) min { p , 3 } , m\geqslant C(p)\,N(\log N)^{\min\{p,3\}}, and is optimal up to the factor ( log log N ) p − 1 (\log\log N)^{p-1} in the random-sampling setting. Second, for 1 ⩽ p < 2 1\leqslant p<2 , we obtain an L p L_{p} analogue of the restricted isometry property via random sampling for bounded orthogonal systems and, more generally, for N N -element systems 𝒟 N \mathcal{D}_{N} satisfying a Riesz-type condition. We prove that when m ⩾ C ( p ) s log N ( log s ) 2 log log s , m\geqslant C(p)\,s\log N\,(\log s)^{2}\,\log\log s, then m m random samples suffice to guarantee an L p L_{p} restricted isometry-type property uniformly over the class of all s s -sparse functions generated by 𝒟 N \mathcal{D}_{N} . 2020 Mathematics Subject Classification Primary 41A65; Secondary 60E15, 46B20, 42C15, 60B20. 1. Introduction 1.1. The Marcinkiewicz discretization Let (\Omega,\mathcal{F},\mu) be a probability space, where \mathcal{F} is a \sigma -algebra of subsets of \Omega and \mu is a probability measure on \mathcal{F} . For 1\leqslant p<\infty , denote by L_{p}(\mu)\equiv L_{p}(\Omega,\mu) the usual Lebesgue space of measurable functions f\colon\Omega\to\mathbb{C} equipped with the norm \|f\|_{L_{p}(\mu)}=\left(\int_{\Omega}|f|^{p}\,d\mu\right)^{1/p}. Let B(\Omega) denote the space of all bounded functions f\colon\Omega\to\mathbb{C} equipped with the uniform norm \|f\|_{\infty}:=\sup_{x\in\Omega}|f(x)|. Let X_{N}\subset B(\Omega) be an N -dimensional linear space of bounded functions. We assume that any function f\in X_{N} that vanishes \mu -a.e. on \Omega is identically zero (equivalently, \|\cdot\|_{L_{p}(\mu)} defines a norm on X_{N} ). Our goal is to discretize the L_{p} norm on X_{N} by Marcinkiewicz-type inequalities. Specifically, given 1\leqslant p<\infty and \varepsilon\in(0,1) , we seek sampling points \xi^{1},\dots,\xi^{m}\in\Omega (with m\geqslant N ) such that (1.1) (1-\varepsilon)\|f\|_{L_{p}(\mu)}^{p}\leqslant\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leqslant(1+\varepsilon)\|f\|_{L_{p}(\mu)}^{p},\quad\forall\,f\in X_{N}. The main problem is to determine the asymptotically optimal sample size m for which ( 1.1 ) holds on an arbitrary N -dimensional subspace X_{N} under natural structural assumptions. 1.2. Background and motivation In the classical setting, X_{N} typically consists of trigonometric or algebraic polynomials of bounded degree on a compact domain \Omega\subset\mathbb{R}^{d} , equipped with a normalized (possibly weighted) Lebesgue measure. In this case, inequalities of the form ( 1.1 ) are known as Marcinkiewicz–Zygmund inequalities. For these polynomial spaces, such inequalities with an asymptotically optimal sample size m\asymp N have been established on various regular compact domains, such as tori, intervals, spheres, cubes, and C^{2} -smooth domains in \mathbb{R}^{d} ; see, for instance, [ 32 , 33 , 25 , 34 , 24 , 11 , 13 , 57 ] . These inequalities play a fundamental role in the convergence of Fourier series, Lagrange interpolation, and polynomial approximation. However, classical techniques rely heavily on geometric properties of \Omega and often suffer from the curse of dimensionality as the ambient dimension d increases. These limitations motivate a more general high-dimensional theory in which X_{N} is an arbitrary N -dimensional subspace of B(\Omega) . In this general setting, Marcinkiewicz discretization inequalities ( 1.1 ) are governed by the norms of the embeddings (X_{N},\|\cdot\|_{L_{p}})\hookrightarrow B(\Omega) , which are conveniently expressed via Nikolskii-type inequalities. 1.3. Nikolskii-type inequality Given p\in[1,\infty) , an N -dimensional subspace X_{N}\subset B(\Omega) is said to satisfy the (p,\infty) –Nikolskii-type inequality with constant H\geqslant 1 if \|f\|_{\infty}\leqslant H^{1/p}\,\|f\|_{L_{p}(\mu)},\quad\forall\,f\in X_{N}. In this case, we write X_{N}\in\textnormal{NI}_{p,\infty}(H) . It is readily seen that for any p\geqslant 2 , X_{N}\in\textnormal{NI}_{p,\infty}(H)\implies X_{N}\in\textnormal{NI}_{2,\infty}(H). In particular, for p\geqslant 2 , the condition X_{N}\in\textnormal{NI}_{p,\infty}(H) implies that H\geqslant N . Therefore, in this case we may write H=KN for some constant K\geqslant 1 . 1.4. Prior work In recent years, the Marcinkiewicz discretization problem ( 1.1 ) has been extensively studied under the (2,\infty) –Nikolskii-type inequality, namely, in the case when (1.2) X_{N}\in\textnormal{NI}_{2,\infty}(KN), where K\geqslant 1 is fixed (see, for instance, [ 3 , 12 , 26 , 27 , 31 , 15 , 14 , 50 , 29 ] ). The techniques employed in these works are largely drawn from the theory of embeddings of finite-dimensional subspaces (see [ 5 , 23 , 41 , 42 , 44 , 46 , 47 ] ). Although a constant K in ( 1.2 ) always exists by finite-dimensional norm equivalence, its size is crucial. We now recall the main known results under the assumption X_{N}\in\textnormal{NI}_{2,\infty}(KN) . (i) The case p=2 . By [ 31 , 26 ] , building on the groundbreaking work [ 35 ] , the bound m\geqslant C\varepsilon^{-2}KN ensures an L_{2} -discretization inequality of the form ( 1.1 ), up to an additional factor K on the right-hand side (see also [ 41 ] ). (ii) The case 1\leqslant p<2 . It was shown in [ 12 ] , using a refined form of Talagrand’s estimate [ 44 ] *Theorem 16.8.2, that ( 1.1 ) holds whenever m\geqslant C(p,\varepsilon)\begin{cases}(KN)\log(KN),&p=1,\\[2.84526pt] (KN)\log(KN)(\log\log(KN))^{2},&1<p<2.\end{cases} (iii) The case p>2 .