We show that for primes
- Award ID(s):
- 1800689
- NSF-PAR ID:
- 10176650
- 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
-
with , the class number of is divisible by . Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that when , there is always a cusp form of weight and level whose th Fourier coefficient is congruent to modulo a prime above , for all primes . We use the Galois representation of such a cusp form to explicitly construct an unramified degree- extension of . -
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
-
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
-
For each odd integer
, we construct a rank-3 graph with involution whose real -algebra is stably isomorphic to the exotic Cuntz algebra . This construction is optimal, as we prove that a rank-2 graph with involution can never satisfy , 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 involutionwhose real -algebra is stably isomorphic to the suspension . In the Appendix, we show that the -fold suspension is stably isomorphic to a graph algebra iff . -
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.