78 citations · 436 across the 33 of their papers we have counts for
5 papers · 1 filter
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 (…
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…
Overcomplete Independent Component Analysis via SDP
Anastasia Podosinnikova, Amelia Perry, Alexander Wein +3
We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous al…