skip to main content


Title: Averages Along the Primes: Improving and Sparse Bounds
Abstract Consider averages along the prime integers ℙ given by {\mathcal{A}_N}f(x) = {N^{ - 1}}\sum\limits_{p \in \mathbb{P}:p \le N} {(\log p)f(x - p).} These averages satisfy a uniform scale-free ℓ p -improving estimate. For all 1 < p < 2, there is a constant C p so that for all integer N and functions f supported on [0, N ], there holds {N^{ - 1/p'}}{\left\| {{\mathcal{A}_N}f} \right\|_{\ell p'}} \le {C_p}{N^{ - 1/p}}{\left\| f \right\|_{\ell p}}. The maximal function 𝒜 * f = sup N |𝒜 N f | satisfies ( p , p ) sparse bounds for all 1 < p < 2. The latter are the natural variants of the scale-free bounds. As a corollary, 𝒜 * is bounded on ℓ p ( w ), for all weights w in the Muckenhoupt 𝒜 p class. No prior weighted inequalities for 𝒜 * were known.  more » « less
Award ID(s):
1800689
NSF-PAR ID:
10176650
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Concrete Operators
Volume:
7
Issue:
1
ISSN:
2299-3282
Page Range / eLocation ID:
45 to 54
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We show that for primesN,p≥<#comment/>5N, p \geq 5withN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, the class number ofQ(N1/p)\mathbb {Q}(N^{1/p})is divisible bypp. Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that whenN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, there is always a cusp form of weight22and levelΓ<#comment/>0(N2)\Gamma _0(N^2)whoseℓ<#comment/>\ellth Fourier coefficient is congruent toℓ<#comment/>+1\ell + 1modulo a prime abovepp, for all primesℓ<#comment/>\ell. We use the Galois representation of such a cusp form to explicitly construct an unramified degree-ppextension ofQ(N1/p)\mathbb {Q}(N^{1/p}).

     
    more » « less
  2. An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications. 
    more » « less
  3. For each odd integern≥<#comment/>3n \geq 3, we construct a rank-3 graphΛ<#comment/>n\Lambda _nwith involutionγ<#comment/>n\gamma _nwhose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>n,γ<#comment/>n)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)is stably isomorphic to the exotic Cuntz algebraEn\mathcal E_n. This construction is optimal, as we prove that a rank-2 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda ,\gamma )can never satisfyCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)∼<#comment/>MEEnC^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda , \gamma )whose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )is stably isomorphic to the suspensionSRS \mathbb {R}. In the Appendix, we show that theii-fold suspensionSiRS^i \mathbb {R}is stably isomorphic to a graph algebra iff−<#comment/>2≤<#comment/>i≤<#comment/>1-2 \leq i \leq 1.

     
    more » « less
  4. A bstract We report the measurement of the two-photon decay width of χ c 2 (1 P ) in two-photon processes at the Belle experiment. We analyze the process γγ → χ c 2 (1 P ) → J/ψγ , J/ψ → ℓ + ℓ − ( ℓ = e or μ ) using a data sample of 971 fb − 1 collected with the Belle detector at the KEKB e + e − collider. In this analysis, the product of the two-photon decay width of χ c 2 (1 P ) and the branching fraction is determined to be $$ {\Gamma}_{\gamma \gamma}\left({\chi}_{c2}(1P)\right)\mathcal{B}\left({\chi}_{c2}(1P)\to J/\psi \gamma \right)\mathcal{B}\left(J/\psi \to {\ell}^{+}{\ell}^{-}\right)=14.8\pm 0.3\left(\textrm{stat}.\right)\pm 0.7\left(\textrm{syst}.\right) $$ Γ γγ χ c 2 1 P B χ c 2 1 P → J / ψγ B J / ψ → ℓ + ℓ − = 14.8 ± 0.3 stat . ± 0.7 syst . eV, which corresponds to Γ γγ ( χ c 2 (1 P )) = 653 ± 13(stat.) ± 31(syst.) ± 17(B.R.) eV, where the third uncertainty is from $$ \mathcal{B} $$ B ( χ c 2 (1 P ) → J/ψγ ) and $$ \mathcal{B} $$ B ( J/ψ → ℓ + ℓ − ). 
    more » « less
  5. Abstract

    This paper investigates robust versions of the general empirical risk minimization algorithm, one of the core techniques underlying modern statistical methods. Success of the empirical risk minimization is based on the fact that for a ‘well-behaved’ stochastic process $\left \{ f(X), \ f\in \mathscr F\right \}$ indexed by a class of functions $f\in \mathscr F$, averages $\frac{1}{N}\sum _{j=1}^N f(X_j)$ evaluated over a sample $X_1,\ldots ,X_N$ of i.i.d. copies of $X$ provide good approximation to the expectations $\mathbb E f(X)$, uniformly over large classes $f\in \mathscr F$. However, this might no longer be true if the marginal distributions of the process are heavy tailed or if the sample contains outliers. We propose a version of empirical risk minimization based on the idea of replacing sample averages by robust proxies of the expectations and obtain high-confidence bounds for the excess risk of resulting estimators. In particular, we show that the excess risk of robust estimators can converge to $0$ at fast rates with respect to the sample size $N$, referring to the rates faster than $N^{-1/2}$. We discuss implications of the main results to the linear and logistic regression problems and evaluate the numerical performance of proposed methods on simulated and real data.

     
    more » « less