Chi-squared Amplification: Identifying Hidden Hubs

Ravi Kannan, Santosh Vempala

We consider the following general hidden hubs model: an $n\times n$ random matrix $A$ with a subset $S$ of $k$ special rows (hubs): entries in rows outside $S$ are generated from…