skip to main content


Title: All-or-Nothing Phenomena: From Single-Letter to High Dimensions
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 real-valued 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 mean-squared error (MMSE) has been characterized by a single-letter (additive Gaussian scalar) channel. In this paper, we show that if the MMSE function of the single-letter 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 mean-squared error of the (MSE-optimal) approximate message passing algorithm also converges to a step function with a larger threshold, providing evidence for the presence of a computational-statistical gap between the two thresholds.  more » « less
Award ID(s):
1750362 1718494
NSF-PAR ID:
10139968
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
Page Range / eLocation ID:
654 to 658
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We study the problem of estimating a $k$-sparse signal ${\boldsymbol \beta }_{0}\in{\mathbb{R}}^{p}$ from a set of noisy observations $\mathbf{y}\in{\mathbb{R}}^{n}$ under the model $\mathbf{y}=\mathbf{X}{\boldsymbol \beta }+w$, where $\mathbf{X}\in{\mathbb{R}}^{n\times p}$ is the measurement matrix the row of which is drawn from distribution $N(0,{\boldsymbol \varSigma })$. We consider the class of $L_{q}$-regularized least squares (LQLS) given by the formulation $\hat{{\boldsymbol \beta }}(\lambda )=\text{argmin}_{{\boldsymbol \beta }\in{\mathbb{R}}^{p}}\frac{1}{2}\|\mathbf{y}-\mathbf{X}{\boldsymbol \beta }\|^{2}_{2}+\lambda \|{\boldsymbol \beta }\|_{q}^{q}$, where $\|\cdot \|_{q}$  $(0\le q\le 2)$ denotes the $L_{q}$-norm. In the setting $p,n,k\rightarrow \infty $ with fixed $k/p=\epsilon $ and $n/p=\delta $, we derive the asymptotic risk of $\hat{{\boldsymbol \beta }}(\lambda )$ for arbitrary covariance matrix ${\boldsymbol \varSigma }$ that generalizes the existing results for standard Gaussian design, i.e. $X_{ij}\overset{i.i.d}{\sim }N(0,1)$. The results were derived from the non-rigorous replica method. We perform a higher-order analysis for LQLS in the small-error regime in which the first dominant term can be used to determine the phase transition behavior of LQLS. Our results show that the first dominant term does not depend on the covariance structure of ${\boldsymbol \varSigma }$ in the cases $0\le q\lt 1$ and $1\lt q\le 2,$ which indicates that the correlations among predictors only affect the phase transition curve in the case $q=1$ a.k.a. LASSO. To study the influence of the covariance structure of ${\boldsymbol \varSigma }$ on the performance of LQLS in the cases $0\le q\lt 1$ and $1\lt q\le 2$, we derive the explicit formulas for the second dominant term in the expansion of the asymptotic risk in terms of small error. Extensive computational experiments confirm that our analytical predictions are consistent with numerical results.

     
    more » « less
  2. null (Ed.)
    Abstract. This work measured $ \mathrm{d}\sigma/\mathrm{d}\Omega$ d σ / d Ω for neutral kaon photoproduction reactions from threshold up to a c.m. energy of 1855MeV, focussing specifically on the $ \gamma p\rightarrow K^0\Sigma^+$ γ p → K 0 Σ + , $ \gamma n\rightarrow K^0\Lambda$ γ n → K 0 Λ , and $ \gamma n\rightarrow K^0 \Sigma^0$ γ n → K 0 Σ 0 reactions. Our results for $ \gamma n\rightarrow K^0 \Sigma^0$ γ n → K 0 Σ 0 are the first-ever measurements for that reaction. These data will provide insight into the properties of $ N^{\ast}$ N * resonances and, in particular, will lead to an improved knowledge about those states that couple only weakly to the $ \pi N$ π N channel. Integrated cross sections were extracted by fitting the differential cross sections for each reaction as a series of Legendre polynomials and our results are compared with prior experimental results and theoretical predictions. 
    more » « less
  3. Abstract Hausel and Rodriguez-Villegas (2015, Astérisque 370, 113–156) recently observed that work of Göttsche, combined with a classical result of Erdös and Lehner on integer partitions, implies that the limiting Betti distribution for the Hilbert schemes $(\mathbb {C}^{2})^{[n]}$ on $n$ points, as $n\rightarrow +\infty ,$ is a Gumbel distribution . In view of this example, they ask for further such Betti distributions. We answer this question for the quasihomogeneous Hilbert schemes $((\mathbb {C}^{2})^{[n]})^{T_{\alpha ,\beta }}$ that are cut out by torus actions. We prove that their limiting distributions are also of Gumbel type. To obtain this result, we combine work of Buryak, Feigin, and Nakajima on these Hilbert schemes with our generalization of the result of Erdös and Lehner, which gives the distribution of the number of parts in partitions that are multiples of a fixed integer $A\geq 2.$ Furthermore, if $p_{k}(A;n)$ denotes the number of partitions of $n$ with exactly $k$ parts that are multiples of $A$ , then we obtain the asymptotic $$ \begin{align*} p_{k}(A,n)\sim \frac{24^{\frac k2-\frac14}(n-Ak)^{\frac k2-\frac34}}{\sqrt2\left(1-\frac1A\right)^{\frac k2-\frac14}k!A^{k+\frac12}(2\pi)^{k}}e^{2\pi\sqrt{\frac1{6}\left(1-\frac1A\right)(n-Ak)}}, \end{align*} $$ a result which is of independent interest. 
    more » « less
  4. Abstract We obtain new quantitative estimates on Weyl Law remainders under dynamical assumptions on the geodesic flow. On a smooth compact Riemannian manifold ( M ,  g ) of dimension n , let $$\Pi _\lambda $$ Π λ denote the kernel of the spectral projector for the Laplacian, $$\mathbb {1}_{[0,\lambda ^2]}(-\Delta _g)$$ 1 [ 0 , λ 2 ] ( - Δ g ) . Assuming only that the set of near periodic geodesics over $${W}\subset M$$ W ⊂ M has small measure, we prove that as $$\lambda \rightarrow \infty $$ λ → ∞ $$\begin{aligned} \int _{{W}} \Pi _\lambda (x,x)dx=(2\pi )^{-n}{{\,\textrm{vol}\,}}_{_{{\mathbb {R}}^n}}\!(B){{\,\textrm{vol}\,}}_g({W})\,\lambda ^n+O\Big (\frac{\lambda ^{n-1}}{\log \lambda }\Big ), \end{aligned}$$ ∫ W Π λ ( x , x ) d x = ( 2 π ) - n vol R n ( B ) vol g ( W ) λ n + O ( λ n - 1 log λ ) , where B is the unit ball. One consequence of this result is that the improved remainder holds on all product manifolds, in particular giving improved estimates for the eigenvalue counting function in the product setup. Our results also include logarithmic gains on asymptotics for the off-diagonal spectral projector $$\Pi _\lambda (x,y)$$ Π λ ( x , y ) under the assumption that the set of geodesics that pass near both x and y has small measure, and quantitative improvements for Kuznecov sums under non-looping type assumptions. The key technique used in our study of the spectral projector is that of geodesic beams. 
    more » « less
  5. A bstract Using a data sample of 980 fb − 1 collected with the Belle detector at the KEKB asymmetric-energy e + e − collider, we study the processes of $$ {\Xi}_c^0\to \Lambda {\overline{K}}^{\ast 0} $$ Ξ c 0 → Λ K ¯ ∗ 0 , $$ {\Xi}_c^0\to {\Sigma}^0{\overline{K}}^{\ast 0} $$ Ξ c 0 → Σ 0 K ¯ ∗ 0 , and $$ {\Xi}_c^0\to {\Sigma}^{+}{K}^{\ast -} $$ Ξ c 0 → Σ + K ∗ − for the first time. The relative branching ratios to the normalization mode of $$ {\Xi}_c^0\to {\Xi}^{-}{\pi}^{+} $$ Ξ c 0 → Ξ − π + are measured to be $$ {\displaystyle \begin{array}{c}\mathcal{B}\left({\Xi}_c^0\to \Lambda {\overline{K}}^{\ast 0}\right)/\mathcal{B}\left({\Xi}_c^0\to {\Xi}^{-}{\pi}^{+}\right)=0.18\pm 0.02\left(\mathrm{stat}.\right)\pm 0.01\left(\mathrm{syst}.\right),\\ {}\mathcal{B}\left({\Xi}_c^0\to {\Sigma}^0{\overline{K}}^{\ast 0}\right)/\mathcal{B}\left({\Xi}_c^0\to {\Xi}^{-}{\pi}^{+}\right)=0.69\pm 0.03\left(\mathrm{stat}.\right)\pm 0.03\left(\mathrm{syst}.\right),\\ {}\mathcal{B}\left({\Xi}_c^0\to {\Sigma}^{+}{K}^{\ast -}\right)/\mathcal{B}\left({\Xi}_c^0\to {\Xi}^{-}{\pi}^{+}\right)=0.34\pm 0.06\left(\mathrm{stat}.\right)\pm 0.02\left(\mathrm{syst}.\right),\end{array}} $$ B Ξ c 0 → Λ K ¯ ∗ 0 / B Ξ c 0 → Ξ − π + = 0.18 ± 0.02 stat . ± 0.01 syst . , B Ξ c 0 → Σ 0 K ¯ ∗ 0 / B Ξ c 0 → Ξ − π + = 0.69 ± 0.03 stat . ± 0.03 syst . , B Ξ c 0 → Σ + K ∗ − / B Ξ c 0 → Ξ − π + = 0.34 ± 0.06 stat . ± 0.02 syst . , where the uncertainties are statistical and systematic, respectively. We obtain $$ {\displaystyle \begin{array}{c}\mathcal{B}\left({\Xi}_c^0\to \Lambda {\overline{K}}^{\ast 0}\right)=\left(3.3\pm 0.3\left(\mathrm{stat}.\right)\pm 0.2\left(\mathrm{syst}.\right)\pm 1.0\left(\mathrm{ref}.\right)\right)\times {10}^{-3},\\ {}\mathcal{B}\left({\Xi}_c^0\to {\Sigma}^0{\overline{K}}^{\ast 0}\right)=\left(12.4\pm 0.5\left(\mathrm{stat}.\right)\pm 0.5\left(\mathrm{syst}.\right)\pm 3.6\left(\mathrm{ref}.\right)\right)\times {10}^{-3},\\ {}\mathcal{B}\left({\Xi}_c^0\to {\Sigma}^{+}{K}^{\ast 0}\right)=\left(6.1\pm 1.0\left(\mathrm{stat}.\right)\pm 0.4\left(\mathrm{syst}.\right)\pm 1.8\left(\mathrm{ref}.\right)\right)\times {10}^{-3},\end{array}} $$ B Ξ c 0 → Λ K ¯ ∗ 0 = 3.3 ± 0.3 stat . ± 0.2 syst . ± 1.0 ref . × 10 − 3 , B Ξ c 0 → Σ 0 K ¯ ∗ 0 = 12.4 ± 0.5 stat . ± 0.5 syst . ± 3.6 ref . × 10 − 3 , B Ξ c 0 → Σ + K ∗ 0 = 6.1 ± 1.0 stat . ± 0.4 syst . ± 1.8 ref . × 10 − 3 , where the uncertainties are statistical, systematic, and from $$ \mathcal{B}\left({\Xi}_c^0\to {\Xi}^{-}{\pi}^{+}\right) $$ B Ξ c 0 → Ξ − π + , respectively. The asymmetry parameters $$ \alpha \left({\Xi}_c^0\to \Lambda {\overline{K}}^{\ast 0}\right) $$ α Ξ c 0 → Λ K ¯ ∗ 0 and $$ \alpha \left({\Xi}_c^0\to {\Sigma}^{+}{K}^{\ast -}\right) $$ α Ξ c 0 → Σ + K ∗ − are 0 . 15 ± 0 . 22(stat . ) ± 0 . 04(syst . ) and − 0 . 52 ± 0 . 30(stat . ) ± 0 . 02(syst . ), respectively, where the uncertainties are statistical followed by systematic. 
    more » « less