# Exact Recovery for System Identification with More Corrupt Data than Clean Data

arXiv: https://arxiv.org/abs/2305.10506 · HTML: https://mlsanity.com/paper/2305.10506/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 17 May 2023.

## Builds on (most cited first, 19 of 19)

- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Safe Learning of Quadrotor Dynamics Using Barrier Certificates](https://mlsanity.com/paper/1710.05472/) (2017)
- [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020)
- [Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator](https://mlsanity.com/paper/2003.07937/) (2020)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [On the Regret Analysis of Online LQR Control with Predictions](https://mlsanity.com/paper/2102.01309/) (2021)
- [Learning Sparse Dynamical Systems from a Single Sample Trajectory](https://mlsanity.com/paper/1904.09396/) (2019)
- [Online Robust Regression via SGD on the l1 loss](https://mlsanity.com/paper/2007.00399/) (2020)
- [Control Barrier Functions and Input-to-State Safety with Application to Automated Vehicles](https://mlsanity.com/paper/2206.03568/) (2022)
- [Nonparametric Finite Time LTI System Identification](https://mlsanity.com/paper/1902.01848/) (2019)
- [Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees](https://mlsanity.com/paper/2111.00411/) (2021)
- [Learning of Dynamical Systems under Adversarial Attacks -- Null Space Property Perspective](https://mlsanity.com/paper/2210.01421/) (2022)
- [Analysis of A Nonsmooth Optimization Approach to Robust Estimation](https://mlsanity.com/paper/1402.1899/) (2014)
- [On a class of optimization-based robust estimators](https://mlsanity.com/paper/1705.02837/) (2017)

## Built on by (most cited first, 2 of 2)

- [Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks](https://mlsanity.com/paper/2409.00276/) (2024)
- [Subgradient Method for System Identification with Non-Smooth Objectives](https://mlsanity.com/paper/2503.16673/) (2025)

## Abstract (arXiv)

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.