49 citations · 234 across the 21 of their papers we have counts for
3 papers · 1 filter
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi +1
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a…
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size added to an \Erdos-\Renyi graph $G \si…
Tensor principal component analysis via sum-of-squares proofs
Samuel B. Hopkins, Jonathan Shi, David Steurer
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- tensor of the form $T = τ\cdot v_0^{\oti…