  This paper investigates the system identification problem for linear
discrete-time systems under adversaries and analyzes two lasso-type estimators.
We examine both asymptotic and non-asymptotic properties of these estimators in
two separate scenarios, corresponding to deterministic and stochastic models
for the attack times. Since the samples collected from the system are
correlated, the existing results on lasso are not applicable. We prove that
when the system is stable and attacks are injected periodically, the sample
complexity for exact recovery of the system dynamics is linear in terms of the
dimension of the states. When adversarial attacks occur at each time instance
with probability p, the required sample complexity for exact recovery scales
polynomially in the dimension of the states and the probability p. This result
implies almost sure convergence to the true system dynamics under the
asymptotic regime. As a by-product, our estimators still learn the system
correctly even when more than half of the data is compromised. We highlight
that the attack vectors are allowed to be correlated with each other in this
work, whereas we make some assumptions about the times at which the attacks
happen. This paper provides the first mathematical guarantee in the literature
on learning from correlated data for dynamical systems in the case when there
is less clean data than corrupt data.
