78 citations · 436 across the 33 of their papers we have counts for
18 papers · 1 filter
From Weak to Strong Testing in Gaussian Models
Ansh Nagda, Alexander S. Wein
We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix. Below the "B…
Statistical inference of a ranked community in a directed graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein +1
We study the problem of detecting or recovering a planted ranked subgraph from a directed graph, an analog for directed graphs of the well-studied planted dense subgraph model. We…
Tensor cumulants for statistical inference on invariant distributions
Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretic…
Information-Theoretic Thresholds for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth , representin…
Precise Error Rates for Computationally Efficient Testing
Ankur Moitra, Alexander S. Wein
We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is o…
Detection-Recovery Gap for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biolog…
Is it easier to count communities than find them?
Cynthia Rush, Fiona Skerman, Alexander S. Wein +1
Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting…
Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
Andrea Montanari, Alexander S. Wein
We consider the problem of estimating an unknown parameter vector , given noisy observations ${\boldsymbol Y} = {\boldsymbol θ}{\boldsymbol θ}^{\to…
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins +3
Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for su…
Optimal Spectral Recovery of a Planted Vector in a Subspace
Cheng Mao, Alexander S. Wein
Recovering a planted vector in an -dimensional random subspace of is a generic task related to many problems in machine learning and statistics, such as dicti…
Computational Barriers to Estimation from Low-Degree Polynomials
Tselil Schramm, Alexander S. Wein
One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-d…
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1
In compressed sensing, the restricted isometry property (RIP) on sensing matrices (where ) guarantees efficient reconstruction of sparse vectors. A matrix has t…
Computationally efficient sparse clustering
Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretic…
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensio…
Subexponential-Time Algorithms for Sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1
We study the computational cost of recovering a unit-norm sparse principal component planted in a random matrix, in either the Wigner or Wishart spiked model (…
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira +1
A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, introduced by Johnstone, in which a prominent eigenvector (or "spike") is…
Estimation under group actions: recovering orbits from invariants
Afonso S. Bandeira, Ben Blum-Smith, Joe Kileel +3
We study a class of orbit recovery problems in which we observe independent copies of an unknown element of , each linearly acted upon by a random element of some gro…
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira +1
A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, in which a prominent eigenvector is planted into a random matrix. These d…