We consider the problem of estimating a $p$ dimensional vector $\beta$ from $n$ observations $Y=X\beta+W$ , where $\beta_{j}\mathop{\sim}^{\mathrm{i.i.d}.}\pi$ for a realvalued distribution $\pi$ with zero mean and unit variance’ $X_{ij}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,1)$ , and $W_{i}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,\ \sigma^{2})$ . In the asymptotic regime where $n/p\rightarrow\delta$ and $p/\sigma^{2}\rightarrow$ snr for two fixed constants $\delta,\ \mathsf{snr}\in(0,\ \infty)$ as $p\rightarrow\infty$ , the limiting (normalized) minimum meansquared error (MMSE) has been characterized by a singleletter (additive Gaussian scalar) channel. In this paper, we show that if the MMSE function of the singleletter channel converges to a step function, then the limiting MMSE of estimating $\beta$ converges to a step function which jumps from 1 to 0 at a critical threshold. Moreover, we establish that the limiting meansquared error of the (MSEoptimal) approximate message passing algorithm also converges to a step function with a larger threshold, providing evidence for the presence of a computationalstatistical gap between the two thresholds.
more »
« less
Universality for 1d Random Band Matrices: SigmaModel Approximation
The paper continues the development of the rigorous supersymmetric transfer matrix approach to the random band matrices started in (J Stat Phys 164:1233–1260, 2016; Commun Math Phys 351:1009–1044, 2017). We consider random Hermitian block band matrices consisting of $W\times W$ random Gaussian blocks (parametrized by $j,k \in\Lambda=[1,n]^d\cap \mathbb{Z}^d$) with a
fixed entry's variance $J_{jk}=\delta_{j,k}W^{1}+\beta\Delta_{j,k}W^{2}$, $\beta>0$ in each block. Taking the limit $W\to\infty$ with fixed $n$ and $\beta$, we
derive the sigmamodel approximation of the second correlation function similar to Efetov's one.
Then, considering the limit $\beta, n\to\infty$, we prove that in the dimension $d=1$ the behaviour of the sigmamodel approximation in the bulk of the spectrum, as $\beta\gg n$, is determined by the classical Wigner  Dyson statistics.
more »
« less
 Award ID(s):
 1700009
 NSFPAR ID:
 10055605
 Date Published:
 Journal Name:
 Journal of Statistical Physics
 ISSN:
 00224715
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Abstract We study the extent to which divisors of a typical integer n are concentrated. In particular, defining $$\Delta (n) := \max _t \# \{d  n, \log d \in [t,t+1]\}$$ Δ ( n ) : = max t # { d  n , log d ∈ [ t , t + 1 ] } , we show that $$\Delta (n) \geqslant (\log \log n)^{0.35332277\ldots }$$ Δ ( n ) ⩾ ( log log n ) 0.35332277 … for almost all n , a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set $${\textbf{A}} \subset {\mathbb {N}}$$ A ⊂ N by selecting i to lie in $${\textbf{A}}$$ A with probability 1/ i . What is the supremum of all exponents $$\beta _k$$ β k such that, almost surely as $$D \rightarrow \infty $$ D → ∞ , some integer is the sum of elements of $${\textbf{A}} \cap [D^{\beta _k}, D]$$ A ∩ [ D β k , D ] in k different ways? We characterise $$\beta _k$$ β k as the solution to a certain optimisation problem over measures on the discrete cube $$\{0,1\}^k$$ { 0 , 1 } k , and obtain lower bounds for $$\beta _k$$ β k which we believe to be asymptotically sharp.more » « less


The paper continues (Shcherbina and Shcherbina in Commun Math Phys 351:1009–1044, 2017); Shcherbina in Commun Math Phys 328:45–82, 2014) which study the behaviour of second correlation function of characteristic polynomials of the special case of $n \times n$ onedimensional Gaussian Hermitian random band matrices, when the covariance of the elements is determined by the matrix $𝐽=(W^2\triangle+1)^{1}$. Applying the transfer matrix approach, we study the case when the bandwidth W is proportional to the threshold $\sqrt{n}$more » « less

Abstract We determine the asymptotics of the number of independent sets of size $\lfloor \beta 2^{d1} \rfloor$ in the discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $\beta \in (0,1)$ as $d \to \infty$ , extending a result of Galvin for $\beta \in (11/\sqrt{2},1)$ . Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hardcore model at any fixed fugacity $\lambda>0$ . In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.more » « less