Abstract For $$p\geq 1$$ and $$(g_{ij})_{1\leq i,j\leq n}$$ being a matrix of i.i.d. standard Gaussian entries, we study the $$n$$-limit of the $$\ell _p$$-Gaussian–Grothendieck problem defined as $$\begin{align*} & \max\Bigl\{\sum_{i,j=1}^n g_{ij}x_ix_j: x\in \mathbb{R}^n,\sum_{i=1}^n |x_i|^p=1\Bigr\}. \end{align*}$$The case $p=2$ corresponds to the top eigenvalue of the Gaussian orthogonal ensemble; when $$p=\infty $$, the maximum value is essentially the ground state energy of the Sherrington–Kirkpatrick mean-field spin glass model and its limit can be expressed by the famous Parisi formula. In the present work, we focus on the cases $$1\leq p<2$$ and $$2<p<\infty .$$ For the former, we compute the limit of the $$\ell _p$$-Gaussian–Grothendieck problem and investigate the structure of the set of all near optimizers along with stability estimates. In the latter case, we show that this problem admits a Parisi-type variational representation and the corresponding optimizer is weakly delocalized in the sense that its entries vanish uniformly in a polynomial order of $$n^{-1}$$. more »« less
Ivanisvili, P; Nazarov, F
(, International Mathematics Research Notices)
null
(Ed.)
Abstract Let $$1\leq p \leq q <\infty $$ and let $$w \in \mathbb{C}$$. Weissler conjectured that the Hermite operator $$e^{w\Delta }$$ is bounded as an operator from $$L^{p}$$ to $$L^{q}$$ on the Hamming cube $$\{-1,1\}^{n}$$ with the norm bound independent of $$n$$ if and only if $$\begin{align*} |p-2-e^{2w}(q-2)|\leq p-|e^{2w}|q. \end{align*}$$It was proved in [ 1], [ 2], and [ 17] in all cases except $$2<p\leq q <3$$ and $$3/2<p\leq q <2$$, which stood open until now. The goal of this paper is to give a full proof of Weissler’s conjecture in the case $p=q$. Several applications will be presented.
Wang, Ruosong; Woodruff, David P.
(, ACM Transactions on Algorithms)
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.
LECHNER, RICHARD; MOTAKIS, PAVLOS; MÜLLER, PAUL F.X.; SCHLUMPRECHT, THOMAS
(, Mathematical Proceedings of the Cambridge Philosophical Society)
Abstract In this paper we consider the following problem: let X k , be a Banach space with a normalised basis ( e (k, j) ) j , whose biorthogonals are denoted by $${(e_{(k,j)}^*)_j}$$ , for $$k\in\N$$ , let $$Z=\ell^\infty(X_k:k\kin\N)$$ be their l ∞ -sum, and let $$T:Z\to Z$$ be a bounded linear operator with a large diagonal, i.e. , $$\begin{align*}\inf_{k,j} \big|e^*_{(k,j)}(T(e_{(k,j)})\big|>0.\end{align*}$$ Under which condition does the identity on Z factor through T ? The purpose of this paper is to formulate general conditions for which the answer is positive.
Yeon, Kiseok
(, International Mathematics Research Notices)
Abstract Let $$k_i\ (i=1,2,\ldots ,t)$$ be natural numbers with $$k_1>k_2>\cdots >k_t>0$$, $$k_1\geq 2$$ and $$t<k_1.$$ Given real numbers $$\alpha _{ji}\ (1\leq j\leq t,\ 1\leq i\leq s)$$, we consider polynomials of the shape $$\begin{align*} &\varphi_i(x)=\alpha_{1i}x^{k_1}+\alpha_{2i}x^{k_2}+\cdots+\alpha_{ti}x^{k_t},\end{align*}$$and derive upper bounds for fractional parts of polynomials in the shape $$\begin{align*} &\varphi_1(x_1)+\varphi_2(x_2)+\cdots+\varphi_s(x_s),\end{align*}$$by applying novel mean value estimates related to Vinogradov’s mean value theorem. Our results improve on earlier Theorems of Baker (2017).
Fournodavlos, Grigorios; Luk, Jonathan
(, American Journal of Mathematics)
abstract: We prove existence, uniqueness and regularity of solutions to the Einstein vacuum equations taking the form $$ {}^{(4)}g = -dt^2 + \sum_{i,j=1}^3 a_{ij}t^{2 p_{\max\{i,j\}}}\,{\rm d} x^i\,{\rm d} x^j $$ on $$(0,T]_t\times\Bbb{T}^3_x$$, where $$a_{ij}(t,x)$$ and $$p_i(x)$$ are regular functions without symmetry or analyticity assumptions. These metrics are singular and asymptotically Kasner-like as $$t\to 0^+$$. These solutions are expected to be highly non-generic, and our construction can be viewed as solving a singular initial value problem with Fuchsian-type analysis where the data are posed on the ``singular hypersurface'' $$\{t=0\}$$. This is the first such result without imposing symmetry or analyticity. To carry out the analysis, we study the problem in a synchronized coordinate system. In particular, we introduce a novel way to perform (weighted) energy estimates in such a coordinate system based on estimating the second fundamental forms of the constant-$$t$$ hypersurfaces.
Chen, Wei-Kuo, and Sen, Arnab. On ℓ p -Gaussian–Grothendieck Problem. Retrieved from https://par.nsf.gov/biblio/10336967. International Mathematics Research Notices . Web. doi:10.1093/imrn/rnab311.
Chen, Wei-Kuo, & Sen, Arnab. On ℓ p -Gaussian–Grothendieck Problem. International Mathematics Research Notices, (). Retrieved from https://par.nsf.gov/biblio/10336967. https://doi.org/10.1093/imrn/rnab311
@article{osti_10336967,
place = {Country unknown/Code not available},
title = {On ℓ p -Gaussian–Grothendieck Problem},
url = {https://par.nsf.gov/biblio/10336967},
DOI = {10.1093/imrn/rnab311},
abstractNote = {Abstract For $p\geq 1$ and $(g_{ij})_{1\leq i,j\leq n}$ being a matrix of i.i.d. standard Gaussian entries, we study the $n$-limit of the $\ell _p$-Gaussian–Grothendieck problem defined as $$\begin{align*} & \max\Bigl\{\sum_{i,j=1}^n g_{ij}x_ix_j: x\in \mathbb{R}^n,\sum_{i=1}^n |x_i|^p=1\Bigr\}. \end{align*}$$The case $p=2$ corresponds to the top eigenvalue of the Gaussian orthogonal ensemble; when $p=\infty $, the maximum value is essentially the ground state energy of the Sherrington–Kirkpatrick mean-field spin glass model and its limit can be expressed by the famous Parisi formula. In the present work, we focus on the cases $1\leq p<2$ and $2<\infty .$ For the former, we compute the limit of the $\ell _p$-Gaussian–Grothendieck problem and investigate the structure of the set of all near optimizers along with stability estimates. In the latter case, we show that this problem admits a Parisi-type variational representation and the corresponding optimizer is weakly delocalized in the sense that its entries vanish uniformly in a polynomial order of $n^{-1}$.},
journal = {International Mathematics Research Notices},
author = {Chen, Wei-Kuo and Sen, Arnab},
}
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.
An official website of the United States government
