Source-linked AI summary
Defense Filters for Robust Learning of Partially Observed Dynamical Systems
Jihun Kim, Javad Lavaei
TL;DR
Partially observed system identification under attacks is difficult because existing finite-sample bounds can require attack probabilities to diminish with target error. The paper designs a defense filter and analyzes a constrained ℓ2-norm estimator, establishing finite-sample error bounds for recovering the Markov parameter matrix at any fixed attack probability below 0.5.
Problem
Prior finite-sample bounds rely on attack probability diminishing as target estimation error decreases, although attacks may occur at a non-vanishing rate.
Source: §1 · p. 1Method
Results
Finite-sample error bounds establish accurate recovery of G* under attacks with any p < 0.5.
Source: §1 · p. 1Takeaways & Limitations
Normalized filter residuals provide a diagnostic signal for separating normal and corrupted timestamps.
Source: §4 · p. 5, §3.3 · p. 5The attack probability must be p < 0.5, attacks enter through a dimensionally restricted filter, and the observation matrix is assumed known.
Source: §2 · p. 2
Abstract
from arXiv · showhide
Robust estimation of unknown system dynamics from partial observations under attack is a core challenge in learning for control, increasingly critical in multi-agent networks subject to adversarial data poisoning. Existing methods either require highly restrictive assumptions on the adversary or yield weak error bounds. In this paper, we consider identifying partially observed linear dynamical systems subject to adversarial attacks with an attack probability $p < 0.5$ at each time. We propose a defense-filtering framework in which a system designer leverages knowledge of the observation matrix to construct a defense filter satisfying full column rank and subspace separability conditions, which enables the evaluation of a single-attack scenario against observed data. Using this framework, we analyze the constrained $\ell_2$-norm estimator and establish finite-sample error bounds for recovering the Markov parameter matrix $G^*$. This is the first approach to provide provable system identification guarantees via a defense filter for partially observed systems subject to harsh attack environments where the attack probability approaches $0.5$.
1. INTRODUCTION
Identifying partially observed dynamics under attack is challenging because unrestricted adversarial injections make state-space identification ill-posed. The paper proposes a defense filter and constrained estimator to provide finite-sample guarantees even when the attack probability is fixed below one half.
1. INTRODUCTION
- Unrestricted arbitrary injections make identifying state-space parameters inherently ill-posed, motivating restricted adversary models.Prior work considered limits on sensor or actuator access, partly reflecting physically protected components and resource-constrained security design.Source: §1 · p. 1
- The defense filter restricts adversarial injections to a lower-dimensional subspace through predetermined channels, allowing selective component protection while preserving normal-operation interfaces.This architecture is framed as consistent with resource-constrained security design.Source: §1 · p. 1
- Earlier approaches' finite-sample bounds require attack probability to diminish as target estimation error decreases, an impractical condition for non-vanishing attacks.The paper addresses this limitation by analyzing a constrained ℓ2-norm estimator at fixed attack probability.Source: §1 · p. 1
- The defense-filter framework supports finite-sample recovery of the Markov parameter matrix under any fixed attack probability p < 0.5.It requires full column rank and subspace separability, which allow a single-attack scenario to be tested against observations.Source: §1 · p. 1
2. PROBLEM FORMULATION
The problem formulation uses known observations to design a defense filter for partially observed linear systems whose dynamics and attacks are otherwise unknown. It targets the order-k Markov parameter matrix and constrains the estimator and filter geometry under stability, noise, and attack assumptions.
2. PROBLEM FORMULATION
- The system has state x_t, control input u_t, and observation y_t; its A, B, and D matrices are unknown, while C is known.The defense filter E is designed from C, and attacks enter the state update through E.Source: §2 · p. 2
- Attacks occur with probability p < 0.5 and are zero otherwise; at attack times, an adversary with access to the filtration may choose them arbitrarily.The filter design requires a necessary dimension condition r ≥ e, so attack dimension cannot exceed observation output dimension.Source: §2 · p. 2
- The target G* is the order-k Markov parameter matrix [D, CB, CAB, …, CA^(k−2)B], whose accurate estimate supports recovery of A, B, and D up to similarity transformation.Subspace identification methods such as Ho-Kalman can yield k-th order balanced realizations once G* is sufficiently accurate.Source: §2 · p. 2
- The constrained ℓ2-norm estimator is used to estimate G* from the designed control inputs and observed trajectory.The stated objective is to identify the input-output mapping through a Markov parameter matrix of order k.Source: §2 · p. 2
- The analysis assumes system stability and bounded sub-Gaussian norms for the initial state and disturbances.Stability requires ||A^t||_2 ≤ ψρ^t with ρ < 1; the sub-Gaussian norm bounds are specified conditionally for disturbances.Source: §2 · p. 2
- Full column rank and subspace separability are jointly equivalent to a filter H satisfying HCE = I_e and H[CAE … CA^(s−1)E] = 0.The separability condition prevents directions generated by CE from being represented by the later CA^iE directions.Source: §2 · pp. 2–3
3. THEORETICAL ANALYSIS AND MAIN RESULT
The analysis builds preliminary objective bounds and uses them to establish a finite-sample estimation guarantee for the constrained ℓ2-norm estimator. It also derives relative-error and attack-detection implications, with convergence depending on the attack probability and the parameter ρ.
3.1 Preliminary Bounds and Objective Decomposition
- The preliminary analysis isolates attack-free input windows and bounds input energy and attack interactions to obtain a universal lower bound on the objective.The set T0 contains times whose attack indicators are zero for lags 2 through s.Source: §3 · p. 3, §3.1 · p. 3
- The control-input analysis also permits sub-Gaussian signals with expected persistence of excitation, beyond strictly Gaussian inputs.Source: §3.1 · p. 3
3.2 Main Finite-Sample Estimation Guarantee
- Theorem 1 shows that estimation error ||Khat||F is proportional to ||Hhat||2 + ||H*||2 and decays exponentially with parameter s whenever p < min{0.5, 1−ρ}.Source: §3.3 · p. 4
3.3 Relative Error Analysis and Implementation Remarks
- Relative-error analysis normalizes away the absolute scale of Hhat and derives a relative estimation bound.Feasibility gives HhatCE = Ie, which lower-bounds ||Hhat||2 by 1/σmin(CE).Source: §3.3 · pp. 4–5
- Filter residuals are small on unattacked periods but can spike under large attacks when normal and corrupted data are clearly separated, enabling detection.Source: §3.3 · p. 5
- A lower-bound constraint on ||H||2 can prevent the sample-time bound from growing when filter norms approach zero, except when CE is square and invertible at s = 1.Source: §3.3 · p. 5
4. CONCLUSION
The paper establishes finite-sample recovery guarantees for partially observed linear systems under attacks with any fixed probability p < 0.5. It also identifies normalized filter residuals as a diagnostic and outlines a two-stage extension for future work.
4. CONCLUSION
- Finite-sample error bounds for recovering G* hold under adversarial attacks with any fixed probability p < 0.5.The framework analyzes a constrained ℓ2-norm estimator using a defense filter satisfying full column rank and subspace separability conditions.Source: §4 · p. 5
- Normalized filter residuals provide a reliable diagnostic signal for separating normal and corrupted data timestamps.Source: §4 · p. 5
- Future work would extend the framework to filter attacked data before re-estimating dynamics on the clean dataset.The proposed two-stage algorithm is intended to provide robust estimation guarantees.Source: §4 · p. 5
A.1 Proof of Lemma 1
The proof bounds trajectory-related quantities using the system dynamics and then applies filtration-based concentration arguments. A union bound combines the resulting probability bounds.
A.1 Proof of Lemma 1
- The proof begins from sub-Gaussian bounds on the initial state, process noise, and observation noise, then uses the dynamics and a geometric sum to bound state norms over time.Source: §A.1 · pp. 5–6
- Writing the filtration in terms of the initial state and past noises permits repeated tower-rule applications, after which Hoeffding’s inequality is used.Source: §A.1 · p. 6
- The proof applies the same filtration argument to another quantity and completes the probability bound with a union bound.Source: §A.1 · p. 6
A.2 Proof of Lemma 2
The proof establishes that a matrix H with the stated action exists exactly when CE has full column rank and its image is disjoint from the image of L. It constructs such an H by defining its action on the sum of those images and extending it to the full space.
A.2 Proof of Lemma 2
- If HCE = I_e and HL = 0, then CE has rank e and the images of CE and L intersect only at zero.Source: §A.2 · p. 6
- Conversely, full column rank of CE and a trivial intersection between the images make the coefficient u unique in each representation CEu + Lv.Source: §A.2 · p. 6
- The proof defines H on the sum of the two images to recover u while annihilating Lv, then extends H to the full space.Source: §A.2 · p. 6
B.1 Proof of Lemma 3
The proofs combine concentration and probability bounds for Lemma 3 with projection-based rank and conditioning arguments for Lemma 4.
B.1 Proof of Lemma 3
- For Lemma 3, the proof bounds the Lipschitz constant using Cauchy–Schwarz and applies Gaussian concentration.Source: §B.1 · p. 6
- The success probability is bounded using a union bound over two failure events.Source: §B.1 · p. 6
B.2 Proof of Lemma 4
- For Lemma 4, the constraint H*L = 0 parameterizes H* using P⊥_L; the projected CE has full column rank and yields a unique minimum spectral-norm solution.Source: §B.2 · p. 7
- The projected matrix satisfies σ_min(P⊥_L CE) ≥ σ_min(CE) sin(θ) > 0, using the smallest singular value of CE and the minimal principal angle θ.Source: §B.2 · p. 7
B.3 Proof of Lemma 5
The proof bounds attack-related fluctuations with a martingale concentration argument and controls large noise realizations through truncation. Under condition (11), it establishes the stated lower bound with probability at least 1 − δ.
B.3 Proof of Lemma 5
- The attack indicator has conditional probability p, and the proof uses a bounded, history-measurable process to control the attack contribution.It centers the bounded contribution around p to form a martingale difference sequence.Source: §B.3 · p. 7
- A sub-Gaussian tail bound controls the probability that the noise norm exceeds the truncation threshold B.The proof uses this tail bound as part of its high-probability noise-truncation event.Source: §B.3 · p. 7
- Under condition (11), the resulting lower bound holds with probability at least 1 − δ.The proof obtains this probability by applying a union bound across the relevant events.Source: §B.3 · p. 7
B.4 Proof of Lemma 6
The proof establishes a uniform lower bound over the parameter set by combining an epsilon-net argument with concentration bounds. A union bound and a covering-number-based time condition yield the final guarantee.
B.4 Proof of Lemma 6
- The proof uses an epsilon-net over S_R to extend a pointwise lower bound to the full parameter set.For each K, it selects a net point within epsilon in Frobenius norm and combines the resulting bound with an additional event.Source: §B.4 · pp. 7–8
- At each fixed net point, Lemma 5 gives Ψ_T( K̃ ) ≥ c*R_T − ρ_s h T with probability at least 1 − δ/(2N_ε).The proof applies a union bound across the N_ε net points to make the lower bound simultaneous.Source: §B.4 · p. 8
- Combining the simultaneous net bound with event (B.7) yields the stated guarantee with probability at least 1 − δ.The proof then takes the infimum over the auxiliary matrix to obtain the bound.Source: §B.4 · pp. 7–8
- The final time bound in (13) is stated as ˜O(e m k s), hiding logarithmic factors.The proof notes that the time requirement for (B.7) is dominated by (13).Source: §B.4 · p. 8