3 citations · 4 across the 14 of their papers we have counts for
8 papers · 1 filter
Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
Zhangsong Li
We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \[ \boldsymbol{Y}=\frac{1}{\sqrt{n}} \…
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
Zhangsong Li
The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, t…
Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
Shuyang Gong, Dong Huang, Zhangsong Li
We consider the problem of community detection from the joint observation of a high-dimensional covariate matrix and sparse networks, all encoding noisy, partial information ab…
Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
Zhangsong Li
We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple…
The Algorithmic Phase Transition in Correlated Spiked Models
Zhangsong Li
We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices $$ X=\tfracλ{\sqrt{n}} xu^{\top}+W, \quad Y=\tfracμ{\sqrt{n}} yv^{\top}+…
A Smooth Computational Transition in Tensor PCA
Zhangsong Li
We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order- tensor PCA problem where is a fixed integ…
Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection
Shuyang Gong, Zhangsong Li, Qiheng Xu
For a -uniform random hypergraph on vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is , the projection of such a…
The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
Shuyang Gong, Zhangsong Li
Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permuta…