78 citations · 436 across the 33 of their papers we have counts for
9 papers · 1 filter
Beyond Frequency Marching: Orbit Recovery in Dihedral and Projected Multireference Alignment
Tait Weicht, Alexander S. Wein
Multireference alignment (MRA) is the task of recovering a hidden "signal" vector, given many noisy copies that have been cyclically shifted by unknown offsets. This task belongs t…
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Abhishek Dhawan, Cheng Mao, Alexander S. Wein
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergr…
Near-optimal fitting of ellipsoids to random points
Aaron Potechin, Paxton Turner, Prayaag Venkat +1
Given independent standard Gaussian points in dimension , for what values of does there exist with high probability an origin-symmetric ellipsoid tha…
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize over $\|\mathbf{x}\…
The Kikuchi Hierarchy and Tensor PCA
Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the…
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Given a random symmetric matrix drawn from the Gaussian orthogonal ensemble (GOE), we consider the problem of certifying an upper bound on the maximum…
Spectral Methods from Tensor Networks
Ankur Moitra, Alexander S. Wein
A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problem…
How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, Alexander S. Wein
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by de…
A semidefinite program for unbalanced multisection in the stochastic block model
Amelia Perry, Alexander S. Wein
We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove…