English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 anarbitrary way. Recent work [dLN+21, dNS21] has introduced efficient algorithmsfor consistent recovery of the parameter vector. These algorithms cruciallyrely on the design matrix being well-spread (a matrix is well-spread if itscolumn span is far from any sparse vector).  In this paper, we show that there exists a family of design matrices lackingwell-spreadness such that consistent recovery of the parameter vector in theabove robust linear regression model is information-theoretically impossible.  We further investigate the average-case time complexity of certifyingwell-spreadness of random matrices. We show that it is possible to efficientlycertify whether a given $n$-by-$d$ Gaussian matrix is well-spread if the numberof observations is quadratic in the ambient dimension. We complement thisresult by showing rigorous evidence -- in the form of a lower bound againstlow-degree polynomials -- of the computational hardness of this samecertification problem when the number of observations is $o(d^2)$.

On the well-spread property and its relation to linear regression