Empirical Approximation of $L_p$ Norms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916068784603136 |
|---|---|
| author | Dai, Feng Kosov, Egor Murasko, Noel |
| author_facet | Dai, Feng Kosov, Egor Murasko, Noel |
| contents | We study empirical $L_p$ moments of a random vector $\pmbφ$ based on its i.i.d.\ copies $\pmbφ^1,\ldots,\pmbφ^m$, that is, $\frac1m\sum_{j=1}^m |\langle \pmbφ^j,y\rangle|^p$. Our main result is a new estimate for the expected uniform deviation \[ \mathbb{E}\sup_{y\in D}\biggl| \frac1m\sum_{j=1}^m |\langle \pmbφ^j,y\rangle|^p -\mathbb{E}|\langle \pmbφ,y\rangle|^p \biggr| \] over an arbitrary index set $D$. The proof is based on a new bound for Talagrand's $γ$-functional, sharper than the standard Dudley-type entropy estimate. We then apply this estimate to the following two problems.
First, for $p>2$, we study Marcinkiewicz-type discretization of $L_p$ norms on an $N$-dimensional subspace $X_N\subset B(Ω)$ of bounded functions on a probability space $(Ω,μ)$. We obtain bounds in terms of the norm of the embedding $
(X_N,\|\cdot\|_{L_p(μ)})\hookrightarrow B(Ω). $
In particular, we prove that when this norm is of order $N^{1/p}$ and \[ m \ge C(p)\, N\log N\,(\log\log N)^{p-1}, \] then $m$ random samples suffice to approximate the $L_p(μ)$ norm uniformly on $X_N$ by the sampled discrete $L_p$ norm. This substantially improves the previously known bound in this setting $
m \ge C(p)\, N(\log N)^{\min\{p,3\}}, $
and is optimal up to the factor $(\log\log N)^{p-1}$ in the random-sampling setting.
Second, for $1\le p<2$, we obtain an $L_p$ analogue of the restricted isometry property via random sampling for bounded orthogonal systems and, more generally, for $N$-element systems $\mathcal D_N$ satisfying a Riesz-type condition. We prove that when \[ m \ge C(p)\, s\log N\,(\log s)^2\,\log\log s, \] then $m$ random samples suffice to guarantee an $L_p$ restricted isometry-type property uniformly over the class of all $s$-sparse functions generated by $\mathcal D_N$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00347 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Empirical Approximation of $L_p$ Norms Dai, Feng Kosov, Egor Murasko, Noel Functional Analysis Numerical Analysis Classical Analysis and ODEs Probability 41A65, 60E15, 46B20, 42C15, 60B20 We study empirical $L_p$ moments of a random vector $\pmbφ$ based on its i.i.d.\ copies $\pmbφ^1,\ldots,\pmbφ^m$, that is, $\frac1m\sum_{j=1}^m |\langle \pmbφ^j,y\rangle|^p$. Our main result is a new estimate for the expected uniform deviation \[ \mathbb{E}\sup_{y\in D}\biggl| \frac1m\sum_{j=1}^m |\langle \pmbφ^j,y\rangle|^p -\mathbb{E}|\langle \pmbφ,y\rangle|^p \biggr| \] over an arbitrary index set $D$. The proof is based on a new bound for Talagrand's $γ$-functional, sharper than the standard Dudley-type entropy estimate. We then apply this estimate to the following two problems. First, for $p>2$, we study Marcinkiewicz-type discretization of $L_p$ norms on an $N$-dimensional subspace $X_N\subset B(Ω)$ of bounded functions on a probability space $(Ω,μ)$. We obtain bounds in terms of the norm of the embedding $ (X_N,\|\cdot\|_{L_p(μ)})\hookrightarrow B(Ω). $ In particular, we prove that when this norm is of order $N^{1/p}$ and \[ m \ge C(p)\, N\log N\,(\log\log N)^{p-1}, \] then $m$ random samples suffice to approximate the $L_p(μ)$ norm uniformly on $X_N$ by the sampled discrete $L_p$ norm. This substantially improves the previously known bound in this setting $ m \ge C(p)\, N(\log N)^{\min\{p,3\}}, $ and is optimal up to the factor $(\log\log N)^{p-1}$ in the random-sampling setting. Second, for $1\le p<2$, we obtain an $L_p$ analogue of the restricted isometry property via random sampling for bounded orthogonal systems and, more generally, for $N$-element systems $\mathcal D_N$ satisfying a Riesz-type condition. We prove that when \[ m \ge C(p)\, s\log N\,(\log s)^2\,\log\log s, \] then $m$ random samples suffice to guarantee an $L_p$ restricted isometry-type property uniformly over the class of all $s$-sparse functions generated by $\mathcal D_N$. |
| title | Empirical Approximation of $L_p$ Norms |
| topic | Functional Analysis Numerical Analysis Classical Analysis and ODEs Probability 41A65, 60E15, 46B20, 42C15, 60B20 |
| url | https://arxiv.org/abs/2606.00347 |