Sparse Recovery in Linear Dynamical Systems

22 concepts5 papers1 proposal

In classical control theory, understanding a system's internal state or identifying its external inputs typically requires a number of measurements proportional to the system's full dimension. However, many modern physical systems are governed by sparsity: only a few components of the initial state are non-zero, or only a few actuators are active at any given moment. By leveraging this sparsity, researchers have developed methods to reconstruct system behavior with far less data than traditional observability theory would suggest.

The Intuition of Information Mixing

The core challenge in state estimation is that we rarely observe the full state directly; we see a projection of it through an observation matrix. If the initial state is sparse, the goal is to ensure that the system's dynamics "spread" the information of those few non-zero components across the observations over time.

Wei Dai and Serdar Yuksel demonstrate in Observability of a Linear System Under Sparsity Constraints that this process is highly efficient when the system dynamics exhibit rotational invariance. In stochastic or uncertain systems, this property ensures that the sparse components are effectively "mixed" into the measurement stream. Consequently, the authors show that one can recover the initial state using significantly fewer observations than the system's dimension, provided the sparsity is known.

Geometry of Sparse Reconstruction

Why does minimizing the $\ell_1$-norm (the sum of absolute values) allow us to recover the exact sparse signal? The answer lies in the geometry of convex sets. Mark D Plumbley explores this in Polar Polytopes and Recovery of Sparse Representations, providing a unified framework using polar polytopes.

Intuitively, the $\ell_1$ ball has "pointy" vertices that align with the axes of the coordinate system. When we look for the smallest $\ell_1$ ball that touches the subspace of possible solutions, it is highly likely to hit one of these vertices, which corresponds to a sparse solution. The author connects these geometric properties to established recovery criteria like the Exact Recovery Condition (ERC), making the abstract math of sparse optimization more visually intuitive.

From Sparse States to Sparse Inputs

While early work focused on sparse initial states, recent research shifts the focus to input sparsity. In many networked systems, external disturbances or control signals affect only a small subset of the state space at any time.

In Blind identification of fully observed linear time-varying systems via sparse recovery, Roel Dobbe et al. apply this to "blind" identification. They argue that even if the system parameters themselves are dense and complex, the fact that inputs are sparse makes the problem tractable. By formulating the identification as a compressive sensing problem, the authors prove that one can simultaneously recover both the unknown system dynamics and the sparse inputs that drove them.

Establishing Theoretical Boundaries

As the field matured, the focus moved from "does it work?" to "exactly when does it work?". Early guarantees for $\ell_1$ recovery were often sufficient but overly conservative, meaning they might predict failure for systems that actually perform well in practice.

Kyle Poe et al. addressed this gap in Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by ℓ1 -Minimization. By representing the system dynamics within a specific block matrix structure, the authors provided the first precise boundaries for joint recovery.

This work was extended to the concept of left invertibility—the ability to uniquely determine the input sequence from the output sequence. In Invertibility of Discrete-Time Linear Systems with Sparse Inputs, Kyle Poe et al. established direct analogs to classical control theory (such as rank-based and spectral conditions) specifically for the sparse case. They show that for systems that are "sparse invertible," an inverse can be constructed with only a finite delay, providing a rigorous foundation for designing real-time recovery algorithms.

Key Foundational Work

Observability of a Linear System Under Sparsity Constraints (2013) — contributed 6 concept elements to this direction.
Polar Polytopes and Recovery of Sparse Representations (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_input_sparsity_assumption_7edf5801,
  title = {input sparsity assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/input-sparsity-assumption/rdr_7edf5801f67649d192c692435f195624},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_input_sparsity_assumption_7edf5801_v1,
  title = {input sparsity assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/input-sparsity-assumption/rdr_7edf5801f67649d192c692435f195624/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake