When a few actuators fail or an attacker compromises a handful of nodes in a power grid, the operator sees only a small number of sensor readings. They must work out both the hidden internal state and which input channels were hit, and by how much. For linear systems this is now well understood. If the unknown inputs are sparse (only a few of the $m$ channels are active), they can be recovered exactly by $\ell_1$-minimization, the convex stand-in for "find the sparsest explanation." This holds even with fewer sensors than inputs, and there are sharp conditions that say in advance when recovery will succeed. Real plants, however, are nonlinear, and every one of those guarantees rests on linear superposition. The nonlinear work closest to this question changes the problem rather than solving it. It treats attacks as rare-in-time outliers to be filtered out, not as signals to be reconstructed. It also skips estimating the hidden state.
This note proposes a local but verifiable theory and algorithm for jointly recovering the initial state and channel-sparse unknown inputs of a nonlinear system $x_{t+1}=f(x_t)+Bu_t$, $y_t=h(x_t)$. The central object is a certificate: a small linear program, evaluated at the solution the algorithm returns, that either proves the reconstructed sparse input is the unique sparsest explanation of the data nearby, or flags it as untrustworthy. The claim is that this certificate, together with a matching necessary condition, brackets the empirical success rate of nonlinear sparse recovery as tightly as the linear theory does. That turns "did we find the right attack?" from a hope into a test.
Core Claim
Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by ℓ1 -Minimization supplies the method we build on. It stacks outputs as $y=\mathcal{O}_N x_0+\Gamma_N u_N$. It then removes the initial state by projecting onto the orthogonal complement of the range of $\mathcal{O}_N$, and states a nullspace condition on the projected input matrix. On 25,000 random linear systems, the empirical phase transition sat between that paper's necessary and sufficient curves. The companion paper Invertibility of Discrete-Time Linear Systems with Sparse Inputs shows that systems with more inputs than outputs can still be uniquely invertible with finite delay under sparsity. That result motivates working in the $p<m$ regime. Both papers acknowledge that nonlinearity breaks the construction. The set of unforced output trajectories $\{h(f^t(x_0))\}$ is a curved manifold, and no fixed linear projection can cancel it.
Our observation is that cancellation is only needed locally, on the tangent space of that manifold at the true trajectory. Write the stacked output map as $F(x_0,u)$ over a window of length $N$. Let $J_x$ and $J_u$ be its Jacobians with respect to the initial state and the input sequence at the true pair $(x_0^\star,u^\star)$, and let $P^\perp$ be the projection that annihilates the range of $J_x$. Suppose two quantities are known: a nullspace constant $\gamma<1$ for $P^\perp J_u$ on the support $S$ of $u^\star$, in the sense of Poe et al., and a smallest restricted singular value $\sigma>0$ of $J_u$ on that support. Suppose further that $F$ has second derivative bounded by $L$ on a neighborhood. Then we expect that no other pair $(x_0,u)$ that fits the data and has $\|u\|_1\le\|u^\star\|_1$ exists within a radius
$$ r \;\gtrsim\; \frac{(1-\gamma)\,\sigma}{L}, $$
where $r$ is measured in the joint state-input norm. The form comes from a standard argument: the second-order Taylor remainder, of size $L r^2$, has to be smaller than the first-order gap that the nullspace margin guarantees, of size $(1-\gamma)\sigma r$. With measurement noise of size $\epsilon$, the same argument should give a reconstruction error of order $\epsilon/((1-\gamma)\sigma)$ inside that radius.
The linear theory gives conditions that can be checked in advance. These conditions cannot, because they depend on the unknown true trajectory. The practical payoff is therefore an a posteriori version. At the returned estimate $(\hat x_0,\hat u)$, we search by linear program for a dual vector $w$ satisfying four conditions: $J_x^\top w=0$, $(J_u^\top w)_S=\mathrm{sign}(\hat u_S)$, $|(J_u^\top w)_{S^c}|\le 1-\delta$, and injectivity of the projected Jacobian restricted to $S$. This is the nonlinear analogue of the exact-recovery dual certificate, whose geometric meaning Polar Polytopes and Recovery of Sparse Representations explains through the faces of the $\ell_1$ ball. Combined with an estimated curvature bound, a certificate with margin $\delta$ proves local uniqueness of what was found. Producing it costs one linear program per window.
Research Program
The algorithm is deliberately plain. Over a sliding window, we alternate two steps. First, we relinearize $F$ around the current estimate. Second, we solve the $\ell_1$ program from Poe et al. on the resulting linear time-varying problem, applying the projection to the current state Jacobian. A trust-region step keeps the iterate inside the region where the linearization holds. The estimator is initialized by the unforced fit with $u=0$, and the window slides with the finite delay suggested by the linear invertibility test applied to the Jacobians.
Three analyses accompany the algorithm. The first is the local recovery theorem above, with the projection taken onto the tangent space rather than a global subspace. It covers inputs entering additively through a known $B$ and partial observation through a smooth $h$. This combination is the setting Blind identification of fully observed linear time-varying systems via sparse recovery cannot reach, because that paper requires every state to be measured and keeps a linear state update.
The second analysis is a matching necessary condition. Recovery fails whenever the projected Jacobian has a $2s$-sparse nullspace direction that is tangent to the data-consistent set. This mirrors the "$2s$" argument of the invertibility paper and gives the lower curve of the sandwich.
The third is a sensor-placement procedure. Sensors are chosen to maximize the certificate margin averaged over sampled operating trajectories. This is a tractable surrogate for the combinatorial arrangement test that Poe et al. conjecture to be NP-hard.
We explicitly do not lift the system into a Koopman latent space, a coordinate system in which nonlinear dynamics evolve linearly. As Deep learning for universal linear embeddings of nonlinear dynamics builds them, these embeddings are for autonomous dynamics. A nonlinear encoder also mixes physically sparse inputs across all latent coordinates, which destroys the alignment that $\ell_1$ recovery depends on. Working in physical coordinates with exact Jacobians keeps sparsity in the basis where it actually lives.
The method assumes $f$ and $h$ are known or have been identified beforehand. When they are learned, model error enters as structured noise, and we measure its effect directly rather than assume it away.
Baselines
The naive reference point is a Tikhonov-regularized, or minimum-norm, least-squares inversion of the same linearized windows. It spreads energy over all channels and is expected to misidentify which channels are active. Including it calibrates how much of any gain comes from sparsity at all. On the Sharp Input-Output Analysis of Nonlinear Systems under Adversarial Attacks reports that plain least squares "failed completely" under sparse attacks in its own identification setting. That result constrains the design but is not a reported number for input recovery.
The strongest existing competitor is a direct $\ell_1$-penalized nonlinear moving-horizon estimator. It minimizes output misfit plus $\lambda\|u\|_1$ over $(x_0,u)$ with a general nonlinear-programming solver, using several random restarts. It is strongest because it optimizes the same objective without our structure. If it finds the true sparse input as often as we do, our algorithmic contribution is nil. It is run on identical windows, models, and noise, with the same wall-clock budget per window, and $\lambda$ is tuned on a held-out set of trajectories with a tuning budget equal to ours.
A second strong competitor is the fixed-linearization approach. Here the system is linearized once around a nominal trajectory, and the linear method of Poe et al. is applied unchanged. This isolates the value of relinearizing around the estimate.
The temporal-outlier approach of Kim et al. is adapted for comparison. Its $\ell_2$-norm, median-like estimator fits the input-output map, and the attack is then estimated as the residual. This represents the best existing nonlinear treatment of sparse adversaries.
Finally, a supervised recurrent network is trained to map output windows to inputs. It receives as many simulated training trajectories as it needs, which favors it.
On the identification side, A Sparse Bayesian Deep Learning Approach for Identification of Cascaded Tanks Benchmark reports a long-term simulation RMSE of 0.344, against 0.777 for an unregularized deep network, on the Cascaded Tanks benchmark. We use that model class to supply the learned $f$ in one experiment, so its error level sets the noise floor we must tolerate. No reported result was found on Lacuna for joint state and sparse-input recovery error on any nonlinear benchmark. Our comparisons therefore stand against baselines we run ourselves.
Beating the baselines means two things. The method must achieve higher exact-support recovery and lower input error than the $\ell_1$ nonlinear estimator at matched compute in the $p<m$ regime. Separately, among windows where the certificate fires, the false-certification rate must stay below 1%, with a non-trivial coverage of windows. The key ablation removes the certificate and the tangent projection while keeping relinearization. Its purpose is to show whether the projection, rather than iteration alone, drives the separation between state and input.
Why not just…?
Why not just linearize once around a nominal trajectory and apply the linear theory? Unknown inputs push the trajectory away from the nominal path, so the Jacobians used for the projection become wrong exactly when an attack is large. The SINDYc paper, Sparse Identification of Nonlinear Dynamics with Control (SINDYc), illustrates this kind of departure from local behavior on the forced Lorenz system. The fixed-linearization baseline will settle the question. We expect it to match our method for small attack amplitudes and to degrade as amplitude grows. If it does not degrade, relinearizing is unnecessary and we will say so.
Why not just solve $\ell_1$-penalized nonlinear least squares with an off-the-shelf solver? This is the real threat. On easy instances it may recover the same inputs, and our iteration is close to what such a solver does internally. The honest answer is that the main contribution is not the point estimate but the certificate and its matching necessary condition. A generic solver returns an answer with no way to tell whether a different sparse attack explains the data equally well. The decisive test is whether the certificate, applied to that solver's output, separates its correct reconstructions from its incorrect ones. If it does, the certificate is valuable regardless of which solver wins on raw accuracy.
Why not just treat attacks as rare outliers, as Kim et al. do? Their $\ell_2$ estimator provably needs the attack probability per step to stay below $1/(2\tau)$, where $\tau$ is the memory length. It also does not reconstruct the attack or the state. Persistent faults on a few grid nodes violate that timing assumption by construction. We run their estimator on persistent, channel-sparse attacks to confirm the predicted breakdown above the threshold, and on intermittent attacks, where it should be competitive.
Why not just train a neural network to invert the system? A network can be accurate inside its training distribution. It gives no indication of when an output window is ambiguous, and in the $p<m$ regime ambiguity is the central issue. We will report its accuracy on in-distribution attacks and on attack supports and amplitudes held out of training. We will also check whether its errors concentrate on windows our certificate rejects, which would show the certificate detects genuine ambiguity rather than solver weakness.
Proposed Experiments
The first experiment reproduces the phase-transition methodology of Poe et al. in a nonlinear setting. We use random contractive tanh networks with state dimension up to $n=100$, following the synthetic suite of Kim et al., and vary sensors $p$, inputs $m>p$, sparsity $s$, and the nonlinearity's gain. For each configuration we record exact-support recovery. We then check whether the empirical transition falls between our necessary and sufficient curves, evaluated at the true trajectory. The decisive outcome is a sandwich comparable to the linear one. If it appears only at low gain, the local radius is too conservative to matter in practice.
The second experiment tests persistent channel-sparse attacks on the power-grid swing-dynamics systems used by Kim et al., with fewer phase-angle sensors than attackable buses. It compares support recovery, input error, certificate coverage, and false-certification rate against all baselines. This experiment also sweeps attack timing across the $1/(2\tau)$ threshold.
The third experiment revisits the 4-node network from the invertibility paper with a nonlinear coupling added. It asks whether sensor placements chosen by certificate margin coincide with those the linear arrangement test certifies at small amplitude, and how they diverge at large amplitude.
The fourth experiment uses the Cascaded Tanks benchmark, with 1,024 training and 1,024 test samples, plus an injected sparse pump fault. The tank dynamics are learned rather than known. This measures how identification error, at the 0.344 RMSE level reported for the sparse Bayesian model, erodes both recovery and certificate reliability.
Across all four experiments, the check that decides the proposal's value is the same. Among windows the certificate accepts, reconstructions must be correct almost always. Among windows it rejects, the generic $\ell_1$ solver and the neural inverse must fail substantially more often than on accepted windows.
References
- Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by ℓ1 -Minimization
- Invertibility of Discrete-Time Linear Systems with Sparse Inputs
- Polar Polytopes and Recovery of Sparse Representations
- Blind identification of fully observed linear time-varying systems via sparse recovery
- Deep learning for universal linear embeddings of nonlinear dynamics
- On the Sharp Input-Output Analysis of Nonlinear Systems under Adversarial Attacks
- A Sparse Bayesian Deep Learning Approach for Identification of Cascaded Tanks Benchmark
- Sparse Identification of Nonlinear Dynamics with Control (SINDYc)