  Motivated by the construction of tractable robust estimators via convex
relaxations, we present conditions on the sample size which guarantee an
augmented notion of Restricted Eigenvalue-type condition for Gaussian designs.
Such a notion is suitable for high-dimensional robust inference in a Gaussian
linear model and a multivariate Gaussian model when samples are corrupted by
outliers either in the response variable or in the design matrix. Our proof
technique relies on simultaneous lower and upper bounds of two random bilinear
forms with very different behaviors. Such simultaneous bounds are used for
balancing the interaction between the parameter vector and the estimated
corruption vector as well as for controlling the presence of corruption in the
design. Our technique has the advantage of not relying on known bounds of the
extreme singular values of the associated Gaussian ensemble nor on the use of
mutual incoherence arguments. A relevant consequence of our analysis, compared
to prior work, is that a significantly sharper restricted eigenvalue constant
can be obtained under weaker assumptions. In particular, the sparsity of the
unknown parameter and the number of outliers are allowed to be completely
independent of each other.
