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
Energy Counterexamples in Two Weight Calderón–Zygmund Theory
We show that the energy conditions are not necessary for boundedness of Riesz transforms in dimension $n\geq 2$. In dimension $n=1$, we construct an elliptic singular integral operator $H_{\flat } $ for which the energy conditions are not necessary for boundedness of $H_{\flat }$. The convolution kernel $K_{\flat }\left ( x\right ) $ of the operator $H_{\flat }$ is a smooth flattened version of the Hilbert transform kernel $K\left ( x\right ) =\frac{1}{x}$ that satisfies ellipticity $ \vert K_{\flat }\left ( x\right ) \vert \gtrsim \frac{1}{\left \vert x\right \vert }$, but not gradient ellipticity $ \vert K_{\flat }^{\prime }\left ( x\right ) \vert \gtrsim \frac{1}{ \vert x \vert ^{2}}$. Indeed the kernel has flat spots where $K_{\flat }^{\prime }\left ( x\right ) =0$ on a family of intervals, but $K_{\flat }^{\prime }\left ( x\right ) $ is otherwise negative on $\mathbb{R}\setminus \left \{ 0\right \} $. On the other hand, if a one-dimensional kernel $K\left ( x,y\right ) $ is both elliptic and gradient elliptic, then the energy conditions are necessary, and so by our theorem in [30], the $T1$ theorem holds for such kernels on the line. This paper includes results from arXiv:16079.06071v3 and arXiv:1801.03706v2.
more » « less- NSF-PAR ID:
- 10125346
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)A bstract We present a method to determine the leading-order (LO) contact term contributing to the nn → ppe − e − amplitude through the exchange of light Majorana neutrinos. Our approach is based on the representation of the amplitude as the momentum integral of a known kernel (proportional to the neutrino propagator) times the generalized forward Compton scattering amplitude n ( p 1 ) n ( p 2 ) W + ( k ) → $$ p\left({p}_1^{\prime}\right)p\left({p}_2^{\prime}\right){W}^{-}(k) $$ p p 1 ′ p p 2 ′ W − k , in analogy to the Cottingham formula for the electromagnetic contribution to hadron masses. We construct model-independent representations of the integrand in the low- and high-momentum regions, through chiral EFT and the operator product expansion, respectively. We then construct a model for the full amplitude by interpolating between these two regions, using appropriate nucleon factors for the weak currents and information on nucleon-nucleon ( NN ) scattering in the 1 S 0 channel away from threshold. By matching the amplitude obtained in this way to the LO chiral EFT amplitude we obtain the relevant LO contact term and discuss various sources of uncertainty. We validate the approach by computing the analog I = 2 NN contact term and by reproducing, within uncertainties, the charge-independence-breaking contribution to the 1 S 0 NN scattering lengths. While our analysis is performed in the $$ \overline{\mathrm{MS}} $$ MS ¯ scheme, we express our final result in terms of the scheme-independent renormalized amplitude $$ {\mathcal{A}}_{\nu}\left(\left|\mathbf{p}\right|,\left|\mathbf{p}^{\prime}\right|\right) $$ A ν p p ′ at a set of kinematic points near threshold. We illustrate for two cutoff schemes how, using our synthetic data for $$ {\mathcal{A}}_{\nu } $$ A ν , one can determine the contact-term contribution in any regularization scheme, in particular the ones employed in nuclear-structure calculations for isotopes of experimental interest.more » « less
-
more » « less
Abstract Let $f(z) = \sum_{n=1}^\infty a_f(n)q^n$ be a holomorphic cuspidal newform with even integral weight $k\geq 2$, level N, trivial nebentypus and no complex multiplication. For all primes p, we may define $\theta_p\in [0,\pi]$ such that $a_f(p) = 2p^{(k-1)/2}\cos \theta_p$. The Sato–Tate conjecture states that the angles θp are equidistributed with respect to the probability measure $\mu_{\textrm{ST}}(I) = \frac{2}{\pi}\int_I \sin^2 \theta \; d\theta$, where $I\subseteq [0,\pi]$. Using recent results on the automorphy of symmetric power L-functions due to Newton and Thorne, we explicitly bound the error term in the Sato–Tate conjecture when f corresponds to an elliptic curve over $\mathbb{Q}$ of arbitrary conductor or when f has square-free level. In these cases, if $\pi_{f,I}(x) := \#\{p \leq x : p \nmid N, \theta_p\in I\}$ and $\pi(x) := \# \{p \leq x \}$, we prove the following bound: $$ \left| \frac{\pi_{f,I}(x)}{\pi(x)} - \mu_{\textrm{ST}}(I)\right| \leq 58.1\frac{\log((k-1)N \log{x})}{\sqrt{\log{x}}} \qquad \text{for} \quad x \geq 3. $$ As an application, we give an explicit bound for the number of primes up to x that violate the Atkin–Serre conjecture for f.
-
Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ( ( log n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 .more » « less
-
The classic graphical Cheeger inequalities state that if $M$ is an $n\times n$ \emph{symmetric} doubly stochastic matrix, then \[ \frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))} \] where $\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in S,j\not\in S}M_{i,j}\right)$ is the edge expansion of $M$, and $\lambda_{2}(M)$ is the second largest eigenvalue of $M$. We study the relationship between $\phi(A)$ and the spectral gap $1-\re\lambda_{2}(A)$ for \emph{any} doubly stochastic matrix $A$ (not necessarily symmetric), where $\lambda_{2}(A)$ is a nontrivial eigenvalue of $A$ with maximum real part. Fiedler showed that the upper bound on $\phi(A)$ is unaffected, i.e., $\phi(A)\leq\sqrt{2\cdot(1-\re\lambda_{2}(A))}$. With regards to the lower bound on $\phi(A)$, there are known constructions with \[ \phi(A)\in\Theta\left(\frac{1-\re\lambda_{2}(A)}{\log n}\right), \] indicating that at least a mild dependence on $n$ is necessary to lower bound $\phi(A)$. In our first result, we provide an \emph{exponentially} better construction of $n\times n$ doubly stochastic matrices $A_{n}$, for which \[ \phi(A_{n})\leq\frac{1-\re\lambda_{2}(A_{n})}{\sqrt{n}}. \] In fact, \emph{all} nontrivial eigenvalues of our matrices are $0$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $n$), by showing that for any doubly stochastic matrix $A$, \[ \phi(A)\geq\frac{1-\re\lambda_{2}(A)}{35\cdot n}. \] As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of $n^{\alpha}$ for $\frac{1}{2}\leq\alpha\leq1$ in lower bounding $\phi$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $R$ with nonnegative entries, to obtain a two-sided \emph{gapped} refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such $R$, there is a nonnegative eigenvalue $r$ such that all eigenvalues of $R$ lie within the closed disk of radius $r$ about $0$. Further, if $R$ is irreducible, which means $\phi(R)>0$ (for suitably defined $\phi$), then $r$ is positive and all other eigenvalues lie within the \textit{open} disk, so (with eigenvalues sorted by real part), $\re\lambda_{2}(R)
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
