On the well-spread property and its relation to linear regression
We consider the robust linear regression model $\boldsymbol{y} = X\beta^* +
\boldsymbol{\eta}$, where an adversary oblivious to the design $X \in
\mathbb{R}^{n \times d}$ may choose $\boldsymbol{\eta}$ to corrupt all but a
(possibly vanishing) fraction of the observations $\boldsymbol{y}$ in an
arbitrary way. Recent work [dLN+21, dNS21] has introduced efficient algorithms
for consistent recovery of the parameter vector. These algorithms crucially
rely on the design matrix being well-spread (a matrix is well-spread if its
column span is far from any sparse vector).
  In this paper, we show that there exists a family of design matrices lacking
well-spreadness such that consistent recovery of the parameter vector in the
above robust linear regression model is information-theoretically impossible.
  We further investigate the average-case time complexity of certifying
well-spreadness of random matrices. We show that it is possible to efficiently
certify whether a given $n$-by-$d$ Gaussian matrix is well-spread if the number
of observations is quadratic in the ambient dimension. We complement this
result by showing rigorous evidence -- in the form of a lower bound against
low-degree polynomials -- of the computational hardness of this same
certification problem when the number of observations is $o(d^2)$.