List-Decodable Regression via Expander Sketching

Herbod Pourali, Sajjad Hashemian, Ebrahim Ardeshir-Larijani

We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log (1/\hat{I}´))/\hat{I}\pm )$, list size $O(1/\hat{I}\pm )$, and near inpu…