⚡ electrical engineering

BLISS: Global Blind Identification of Linear Systems with Sparse Inputs

This paper bridges linear system identification and sparse dictionary learning by demonstrating that blind identification with sparse inputs is a generalization of dictionary learning, thereby enabling global identifiability guarantees and the development of scalable algorithms to recover system parameters from a single trajectory.

Original authors: Kyle Poe, Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Rene Vidal

Published 2026-04-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kyle Poe, Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Rene Vidal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you only have the footprints left behind, not the person who made them.

In the world of engineering and data science, this is the problem of System Identification. Usually, to figure out how a machine works (its "rules" or "physics"), you need to know two things:

The Inputs: What you pushed, pulled, or fed into the machine.
The Outputs: How the machine reacted.

If you know both, it's like watching someone push a shopping cart and seeing it roll away. You can easily calculate how heavy the cart is or how much friction the floor has. This is a solved problem.

The Mystery: The "Blind" System
But what if you don't know what was pushed? What if the person pushing the cart is invisible, and you only see the cart moving? This is Blind System Identification. It's like seeing a ghost move a chair, but you don't know if the ghost pushed it gently, slammed it, or if it was a strong wind.

Usually, this is impossible to solve. There are too many guesses. However, this paper introduces a clever trick called BLISS (Blind Identification of Linear Systems with Sparse Inputs).

The Secret Clue: "Sparsity"

The paper's big breakthrough relies on a specific assumption: The invisible pusher is lazy.

In math terms, the inputs are sparse. This means that out of all the possible times the machine could have been pushed, it was only pushed a few times. Most of the time, nothing happened.

Analogy: Imagine a room with 100 light switches. In a normal scenario, someone might flip 50 of them randomly. But in our "sparse" scenario, only one or two switches are ever flipped, and the other 98 are left alone.

Because the "pushes" are so rare, the detective (the algorithm) can use that rarity to figure out the rules of the machine.

The Solution: The "Volume" Trick

The authors realized that this problem is mathematically similar to a different puzzle called Dictionary Learning.

Dictionary Learning Analogy: Imagine you have a bag of Lego bricks (the "dictionary"). You see a finished castle (the data). You don't know which bricks were used or how they were stacked. But if you know the castle was built using a very specific, small set of bricks, you can reverse-engineer the design.

The paper connects these two worlds. They propose a method called Volume Minimization.

The Metaphor: Imagine the possible solutions are shapes in a multi-dimensional room. The "true" solution is a shape that fits the data perfectly but is as small and tight as possible.
If you try to fit the data with a huge, sloppy shape, it might work, but it's "wasteful."
The BLISS algorithm acts like a greedy shrink-wrap machine. It keeps squeezing the possible solutions until it finds the smallest, tightest shape that still explains the data. Because the inputs are "sparse" (lazy), the smallest shape that fits the data turns out to be the correct one.

How They Did It (The Algorithm)

They built a computer program (an algorithm) that does this shrinking process. It uses a technique called ADMM (Alternating Direction Method of Multipliers).

Simple Explanation: Think of it like a game of "Hot and Cold."
1. The computer guesses the rules of the machine.
2. It guesses what the invisible pushes were.
3. It checks if the guesses fit the data.
4. If they don't fit perfectly, it adjusts the guesses to make the "volume" (the size of the guess) smaller.
5. It repeats this thousands of times until it can't get any smaller.

The Results

The paper tested this on a computer with 100 variables (a very complex machine).

The Phase Transition: They found a "tipping point." If the inputs were sparse enough and they had enough data (a long enough history of the machine moving), the algorithm solved the mystery 100% of the time.
If the inputs were too frequent (not sparse) or the data was too short, the algorithm failed.
But when the conditions were right, it could perfectly reconstruct the invisible machine and the invisible pushes, even though it started with zero knowledge.

Why This Matters

This is a big deal because many real-world systems are "blind" and "sparse":

Neuroscience: We can see neurons firing (outputs), but we don't know exactly which signals triggered them (inputs). But we know neurons fire rarely (sparsely).
Earthquakes: We see the ground shake, but we don't know exactly where the fault lines slipped.
Fault Detection: If a machine breaks, it might only happen once in a while. This method can find that one break and figure out the machine's health without needing to know the control signals.

In a nutshell: The paper says, "If you are looking for a needle in a haystack, and you know the needle is the only thing in the haystack, you can find it even if you can't see the haystack clearly." They built a mathematical tool that finds the "needle" (the system rules) by assuming the "haystack" (the inputs) is mostly empty.

1. Problem Statement

The paper addresses the Blind System Identification (BSI) problem for fully observed Linear Time-Invariant (LTI) systems.

System Model: The system is defined by $x(k+1) = A^\natural x(k) + B^\natural u(k)$ , where $x$ is the state, $u$ is the input, and $A^\natural, B^\natural$ are unknown system matrices.
The Challenge: Unlike standard system identification where inputs $u$ are known, this work assumes the inputs $u$ are unknown but possess a specific structure: they are sparse (i.e., at any given time step, only a few input channels are active).
Goal: Given only the state trajectory $X = [x(0), \dots, x(T-1)]$ and the next state trajectory $X^+ = [x(1), \dots, x(T)]$ , recover the system matrices $(A^\natural, B^\natural)$ and the sparse input sequence $U^\natural$ .
Context: This bridges two traditionally separate fields: System Identification (where inputs are usually known) and Sparse Dictionary Learning (where the dictionary and sparse codes are both unknown).

2. Methodology

The authors propose a framework called BLISS (Blind Identification of Sparse Signals), which reformulates the problem as a constrained non-convex optimization task.

A. Formulation as Volume Minimization

Inspired by recent advances in complete dictionary learning, the authors formulate the problem as minimizing the volume of the input matrix $B$ subject to data consistency and sparsity constraints:
$\min_{A, B, U} \text{vol}(B) \quad \text{s.t.} \quad X^+ = AX^\top + BU^\top, \quad \max_i \|U_i\|_1 \leq T\mu$

Volume Definition: $\text{vol}(B) = \sqrt{\det(B^\top B)}$ .
Statistical Justification: The authors show this optimization problem is equivalent to the Maximum Likelihood Estimator (MLE) if the input entries are i.i.d. Laplace distributed.
Key Insight: When $A^\natural$ is known, this reduces exactly to complete dictionary learning. The novelty here is handling the unknown $A^\natural$ .

B. Theoretical Condition: Persistent Scattering

To guarantee global identifiability (recovering the true system up to scaling and permutation), the authors introduce a geometric condition called Persistent Scattering.

Fundamental Zonotope: They define a zonotope $Z$ generated by the normalized state and input matrices.
Condition: The pair $(x, u)$ is "persistently scattering" if the zonotope $Z$ contains a scaled ellipsoid $DB^2$ such that the intersection of the ellipsoid's boundary with the zonotope's boundary occurs only at the axes corresponding to the input dimensions.
Significance: This condition is a strengthening of "Persistent Excitation" (standard in system ID) and "Sufficient Scattering" (standard in dictionary learning). It ensures that the unknown $A$ does not introduce ambiguities that prevent unique recovery.

C. Algorithm: Generalized ADMM

The authors develop a Generalized Alternating Direction Method of Multipliers (ADMM) to solve the non-convex problem (P).

Decoupling: They utilize a thin Singular Value Decomposition (SVD) of the projected data to decouple the update of the input matrix $U$ from the geometry of the state space.
Updates:
- $U$ -update: Involves a projection onto a scaled $\ell_1$ -ball (promoting sparsity).
- $\Phi$ -update (related to $B$ ): Involves a proximal operator for the function $f(\Phi) = -\log|\Phi|$ , which has a closed-form solution via SVD.
Regularization: The algorithm employs a primal-dual residual balancing scheme to adapt the penalty parameter $\rho$ dynamically, ensuring convergence.

3. Key Contributions

Problem Formulation: They successfully frame blind system identification with sparse inputs as a constrained non-convex volume maximization problem, unifying system ID and dictionary learning.
Global Identifiability Guarantees: They establish the first global identifiability results for general, unstructured linear systems under unknown sparse inputs. They prove that under the Persistent Scattering condition, the global optimum of their objective function recovers the ground truth $(A^\natural, B^\natural, U^\natural)$ up to scaling and permutation.
Algorithm Design: They introduce the BLISS algorithm, a principled ADMM-based solver with closed-form updates and bounded iterates, capable of handling the specific geometry of the problem.
Theoretical Unification: They demonstrate that blind system identification is a generalization of complete dictionary learning, leveraging techniques from the latter to solve the former.

4. Experimental Results

The authors validate their theory through extensive experiments on synthetic data ( $n=100, m=25$ ).

Phase Transition: The results show a sharp phase transition between perfect recovery and failure. Recovery is successful when inputs are sufficiently sparse and the trajectory length $T$ is large enough.
Sparsity vs. Density: The algorithm performs significantly better with sparser inputs (Laplace distribution) compared to denser inputs (Gaussian), though it still succeeds with Gaussian inputs if sparsity is high enough.
Known vs. Unknown A: As expected, the "Oracle" case (where $A^\natural$ is known, reducing to dictionary learning) performs better than the blind case, but the BLISS algorithm successfully recovers the system even without knowing $A^\natural$ .
Convergence: The algorithm converges rapidly when the penalty parameter $\rho$ is initialized based on the spectral properties of the system (oracle initialization), outperforming fixed small initializations.

5. Significance

Bridging Communities: The paper effectively bridges the gap between the Systems/Control community (focused on dynamics and excitation) and the Machine Learning/Signal Processing community (focused on sparsity and dictionary learning).
Practical Applications: The ability to identify systems with unknown, sparse inputs is crucial for applications such as:
- Biological Neural Networks: Where neuron activation is sparse.
- Fault Detection: Where faults occur as sparse impulses.
- Seismic Processing: Where signals are sparse in time.
- Actuator Scheduling: Where only a subset of actuators is active at any time.
Theoretical Advancement: By providing global guarantees for a non-convex problem in a blind setting, the work moves beyond local minima heuristics often used in previous blind identification literature.

In summary, BLISS provides a rigorous theoretical foundation and a scalable algorithm for identifying linear systems when inputs are unknown but sparse, demonstrating that global recovery is possible under specific geometric conditions derived from the interplay of system dynamics and input sparsity.