Steady State Covariance Steering via Sparse Intervention

1. Problem Formulation

The paper addresses the problem of steady-state covariance steering for linear dynamical systems. The goal is to modify the system's dynamics such that the steady-state distribution of the state vector matches a target Gaussian distribution.

• System Model: The system is a discrete-time linear dynamical system subject to intervention:
  $$x(k + 1) = (A + U) x(k) + B w(k)$$
  Where $x \in \mathbb{R}^n$ is the state, $w \sim \mathcal{N}(0, I)$ is Gaussian noise, $A$ and $B$ are constant matrices, and $U$ is the intervention matrix designed by the controller.
• Objective: Minimize the Kullback-Leibler (KL) divergence between the steady-state covariance $\Sigma_U$ (induced by $U$) and a reference covariance $\Sigma_{\text{ref}}$.
• Constraints:
  1. Lyapunov Constraint: The steady-state covariance must satisfy the Lyapunov equation: $(A+U)\Sigma(A+U)^\top - \Sigma + BB^\top = 0$.
  2. Structural Sparsity: The intervention matrix $U$ must be sparse. Specifically, non-zero entries are restricted to a predefined set of indices $V$, and the $L_1$ norm of $U$ is bounded ($\|U\|_1 \leq m$) to promote sparsity. This models practical limitations where only specific structural connections can be altered (e.g., in genetic networks or traffic systems).

2. Methodology

The authors propose a Proximal Gradient-based Algorithm to solve the non-convex optimization problem subject to the nonlinear Lyapunov constraint.

A. Analytical Gradient Derivation

A key theoretical contribution is the derivation of the analytical gradient of the objective function $J(\Sigma) = \text{KL}(\Sigma \| \Sigma_{\text{ref}})$ with respect to the intervention matrix $U$.

• Adjoint Method: The authors utilize the adjoint method to handle the Lyapunov constraint efficiently.
• Gradient Expression: The gradient $\frac{dJ}{dU}$ is characterized by the solutions to two Lyapunov equations:
  1. Primal Equation: Solves for the state covariance $\Sigma$.
  2. Adjoint Equation: Solves for the Lagrange multiplier matrix $\Lambda$.
     The resulting gradient is given by:
     $$\frac{dJ}{dU} = 2\Lambda (A + U) \Sigma$$
     This analytical form allows for scalable computation even in high-dimensional systems, avoiding the need for finite-difference approximations.

B. Optimization Algorithm

The solution employs a Proximal Gradient Descent framework to handle the $L_1$ regularization term, which enforces sparsity.

1. Gradient Step: Update an intermediate variable $V$ using the analytical gradient:
   $$V^{(l+1)} = U^{(l)} - \eta \frac{dJ}{dU}$$
2. Proximal Step (Soft-Thresholding): Apply the proximal operator for the $L_1$ norm to $V$ to obtain the updated $U$:
   $$U^{(l+1)} = \text{prox}_{\eta\lambda}(V^{(l+1)})$$
   This step performs soft-thresholding, shrinking small values to exactly zero, thereby enforcing the sparsity constraint directly within the optimization loop.

3. Key Contributions

1. Analytical Gradient Characterization: The paper provides a closed-form expression for the gradient of the KL divergence with respect to the intervention matrix. This expression relies on solving two Lyapunov equations (primal and adjoint), offering a computationally efficient alternative to numerical differentiation.
2. Sparse Structural Intervention: The formulation explicitly targets structural changes (modifying the system matrix $A$) rather than dynamic feedback control. The integration of $L_1$ regularization ensures that the resulting intervention is sparse, making it applicable to large-scale systems where only a few parameters can be manipulated.
3. Algorithm Development: The development of a specialized proximal gradient algorithm that simultaneously handles the nonlinear Lyapunov constraint and the non-smooth $L_1$ penalty.

4. Numerical Results

The authors validated the algorithm using a 5-dimensional linear system.

• Setup: The system was steered from an initial state distribution to a target reference covariance $\Sigma_{\text{ref}}$. The intervention matrix $U$ was constrained to have a limited $L_1$ norm.
• Performance:
  • Covariance Steering: The algorithm successfully steered the state distribution. Visualizations (scatter plots projected onto principal components) showed that without control, the state spread widely, whereas with the computed sparse intervention, the states concentrated tightly within the target covariance ellipsoid (containing 99% of the probability mass).
  • Convergence: The objective function (KL divergence) converged to approximately 1.4 within 100 iterations.
  • Sparsity: The final intervention matrix $U$ contained only 4 non-zero elements ($U_{11}, U_{33}, U_{51}, U_{55}$), demonstrating the algorithm's ability to identify minimal structural changes.
• Trade-off Analysis: By varying the regularization parameter $\lambda$, the authors demonstrated a clear trade-off: increasing $\lambda$ reduced the number of non-zero elements (increasing sparsity) but resulted in a higher final objective value (slightly worse steering performance).

5. Significance and Future Work

• Practical Applicability: The approach is highly relevant for fields like medical interventions (e.g., gene regulatory networks where only specific interactions can be targeted) and traffic management (e.g., signal control or tolling). It addresses the reality that in complex systems, full control is often impossible or too costly; sparse, targeted interventions are preferred.
• Scalability: The use of Lyapunov-based gradients makes the method scalable to high-dimensional systems, overcoming the computational bottlenecks of traditional manifold optimization.
• Future Directions: The authors plan to apply this framework to healthcare and transportation systems. They also aim to extend the theory to investigate instability induction, exploring how sparse interventions can deliberately destabilize specific modes of a stable system to trigger desired state transitions.