Sparsity in control problems: Recent trends and open challenges

• Economic, energy, bandwidth, and hardware limits constrain control performance and the strategies designers can practically implement.Source: §1 · p. 1
• Large-scale plants face limits on the number and type of devices that can be deployed because of budget, space, or energy constraints.Source: §1 · p. 1
• Resource constraints also arise in distributed control, robotics, social and biological systems, and wireless networks.Examples include reducing communication links, meeting compute and latency limits, limiting interventions, and scheduling transmissions.Source: §1 · p. 1

1 INTRODUCTION 2

• Sparsity captures designs that select or activate only a small subset of available components, leaving the rest zero.Source: §1 · p. 2
• A reference formulation minimizes task-specific cost under problem constraints and an l0 bound on nonzero design variables.A minimal-design alternative penalizes the l0 pseudo-norm to seek the sparsest solution satisfying design constraints.Source: §1 · p. 2
• Because l0 optimization is usually computationally intractable, solution approaches often use l1 relaxations or low-complexity heuristics.The formulations serve mainly as guidelines rather than optimization programs directly solved by design procedures.Source: §1 · p. 2

1.1. Objectives of this survey

• The survey brings together representative control and estimation work to surface connections across literature streams that rarely refer to one another.Source: §1.1 · p. 2
• Topics include minimal controllability, sparse attacks, hands-off and s-sparse control, sparse-input recovery, actuator scheduling, and online optimization.Source: §1.1 · p. 2

1.2. Related surveys and main differences

• Unlike reviews centered on compressed sensing or sparse feedback architectures, this survey emphasizes structured sparse inputs, interventions, and design variables in control.Source: §1.2 · p. 2

2 NOTATION AND PRELIMINARIES 3

• Unlike feedback-controller surveys, this work focuses on sparse control inputs, interventions, and related design variables rather than sparse feedback architectures.Source: §2 · p. 3
• It treats actuator scheduling as a control-cost-coupled problem, unlike broader scheduling work on tasks, transmissions, or resource allocation.Source: §2 · p. 3

1.3. Organization

• The survey covers static controllability, invertibility, and attack estimation; precomputed sparse control and actuator schedules; and online optimization with sparse decisions.It introduces motivations and problems, reviews results and limitations, and discusses future directions for each topic.Source: §1.3 · p. 3

2.1. Linear algebra

• The survey uses standard vector and matrix notation and defines the l0 pseudo-norm as the number of nonzero vector elements.The support of a vector is the set of indices with nonzero elements.Source: §2.1 · p. 3

2.2. Dynamical systems

• Its main models are linear state-space systems in discrete or continuous time, with state, input, and output variables and associated matrices.Source: §2.2 · p. 4

2.3. Graphs

• For directed graphs, distance is the length of the shortest directed path and is infinite when no such path exists.In undirected graphs, distance is symmetric and the in- and out-neighborhoods coincide.Source: §2.3 · p. 4

3.3. Minimal actuator selection

• Unlike minimal design of all input channels, generic actuator selection chooses at most k columns of a given input matrix to optimize a cost, typically assuming a sufficient budget.Budgeted selection emphasizes objective suboptimality rather than feasibility or minimal allocation; recent work bridges the problems by selecting the fewest columns needed for controllability.Source: Difference with actuator selection · p. 5, §3.3 · p. 6

3.2. Minimal Controllability

• Minimal controllability is NP-hard to approximate within c log n, while a deterministic greedy algorithm achieves O(log n) sparsity (Olshevsky, 2014).The PBH test reduces the problem to hitting every left-eigenvector support; greedy selection covers the most remaining eigenvectors at each step.Source: §3.2.3 · p. 5, §3.2.2 · p. 5, §3.2.4 · p. 6

3.2.5. Robust version

• For s faulty actuators, robust minimal controllability is polynomially equivalent to set multicover and admits greedy selection with an O(log n) optimality gap.Each element must be covered s + 1 times; the input matrix has (s + 1)n columns to avoid cases where faults make controllability infeasible.Source: §3.2.5 · p. 6

3.3. Minimal actuator selection

• Minimal actuator selection can be formulated as an integer linear program and, under technical redundancy conditions, as a minimal set multicover problem, establishing NP-completeness even with high-dimensional eigenspaces.When A has distinct eigenvalues, the multicover problem reduces to set cover.Source: §3.3 · pp. 6–7

3.4.2. Why greedy methods fail

• Minimal reachability is inapproximable within 2^Ω(log^(1−δ)n) under standard complexity assumptions, even with zero initial state, identity input matrix, and target error tolerance.Reachability reduces to selecting columns whose span contains a target vector; squared distance to the reachable subspace is not generally submodular, so greedy guarantees fail.Source: §3.4.2 · p. 7, §3.4.1 · p. 7

3.5.1. Diameter and control energy

• Under specified conditions, networks with sublinear diameter have control energy growing exponentially in n, whereas sufficiently anisotropic chains, rings, and asymmetric rings can be easy to control.The difficult-network conditions include bounded weights, DSS dynamics, and a constant fraction of eigenvalues below some modulus μ < 1; an appropriately weighted ring can have single-node control energy bounded independently of n.Source: §3.5.1 · pp. 7–8

3.5.2. Input placement and the longest control chain

• In studied 90-node brain networks, hub inputs with LCC = 3 yield the lowest energy, while primary auditory and visual regions with LCC = 5 require far more (Alizadeh Darbandi et al., 2024).Minimum-cardinality input sets achieving LCC = 1 mix low-, medium-, and high-degree regions, comprise roughly 10% of nodes, and achieve energy comparable to driving all 90 regions.Source: §3.5.2 · p. 8

3.5.3. Graph controllability under Laplacian dynamics

• For Laplacian dynamics, every essentially controllable graph is asymmetric, and any single standard basis input suffices for minimal controllability.Graphs are classified as essentially controllable, completely uncontrollable, or conditionally controllable according to controllability across binary control vectors; controllability is invariant under binary complements.Source: §3.5.3 · p. 8
• Asymmetry alone does not ensure controllability: asymmetric Steiner triple-system block graphs are uncontrollable, and homogeneous leader/follower inputs fail for n≥3.For n≤7, complete uncontrollability requires a repeated eigenvalue; from n=8, it can occur with all eigenvalues distinct.Source: §3.5.3 · p. 8

3.5.4. Strong uncontrollability

• A twin graph whose quotient admits the specified almost equitable partition is strongly uncontrollable (Aguilar, 2020).Twin pairs create eigenvectors orthogonal to binary inputs with equal values at twin vertices; the quotient partition adds eigenvectors orthogonal to the binary inputs those twin vectors miss.Source: §3.5.4 · p. 8
• Strong uncontrollability under the adjacency matrix appears absent for n≤10 (Aguilar, 2020).Source: §3.5.4 · p. 9
• Even with simple eigenvalues, twin graphs may require controlling ⌊(n−1)/2⌋ nodes, exceeding the spectral-multiplicity lower bound.This lower bound follows from the twin-graph construction.Source: §3.5.4 · p. 9

3.6. Limitations and outlook

• Minimal controllability and reachability need study beyond freely assignable diagonal inputs, including general actuator selection, nonlinear dynamics, codesign, and energy minimization.Although graph control energy metrics connect the controllability Gramian to interpretable quantities such as diameter, Laplacian-specific results may not extend to general LTI systems; structured-system controllability may offer a route to broader results.Source: §3.6 · p. 9

4.1. Motivation

• Weak structural controllability requires controllability for some admissible parameter assignment, while strong structural controllability requires it for every assignment and brackets the minimum leader count.The minimum leader count for SSC is an upper bound on the input set needed to guarantee controllability across all realizations; weak structural controllability gives a lower bound.Source: §4.1 · pp. 9–10

Problem statements

• For a graph and leader set, the strong structurally controllable subspace dimension is the worst-case controllability rank; the problems are to bound it or select few leaders for full or partial guarantees.Exact computation of the dimension is generally difficult, and zero-forcing and distance-based approaches provide complementary, efficiently computable lower bounds.Source: §4.2 · p. 10, Problem statements · pp. 10–11

4.3. Zero Forcing and SSC

• Zero forcing exactly characterizes leader sets guaranteeing controllability across all admissible realizations, so the minimum SSC leader count equals the graph’s zero forcing number.The coloring rule repeatedly lets a black node with exactly one white out-neighbor force that neighbor black.Source: §4.3 · p. 11
• Zero forcing remains exact for symmetric edge-weight realizations, but under additional sign constraints it is sufficient and may no longer be necessary for controllability.For the symmetric subclass, controllability over that subclass, over the full qualitative class, and the zero-forcing condition are equivalent.Source: §4.3 · pp. 11–12

ZFS Computation

• Computing a minimum zero forcing set is NP-hard; exact methods have exponential worst-case complexity, while greedy heuristics scale but can be arbitrarily suboptimal.For trees, a minimum zero forcing set can be computed in O(n) time.Source: ZFS Computation · p. 12

4.4. Graph Distances and SSC

• Distance-based bounds use leaders’ shortest-path profiles: sufficiently distinct distances make input effects appear at different powers of the system matrix, yielding independent controllability-matrix columns.The approach combines a distance notion, a realization subclass that preserves distance information, and a pseudo-monotonically increasing sequence.Source: §4.4 · p. 12

Distance and distance-information preserving subclass

• Distance-information-preserving matrices prevent cancellation among shortest-path contributions; the class includes weighted Laplacian and adjacency matrices and equals the full qualitative class for geodetic graphs.A uniform sign for nonzero off-diagonal elements is sufficient, but not necessary, for membership in this subclass.Source: Distance and distance-information… · p. 12

Distance-to-leaders vectors and PMI sequences

• The longest pseudo-monotonically increasing sequence of distance-to-leader vectors gives a lower bound on guaranteed controllability, with each vector closer to some leader than all later vectors.The vectors record each node’s distances from the leaders.Source: Problem statements · p. 11, Distance-to-leaders vectors and PMI… · p. 13
• When every leader has at least two follower out-neighbors, the distance bound exceeds the zero-forcing bound; this also holds for many reachable single-leader graphs unless complete SSC is certified.The bounds do not uniformly dominate one another, so which is more informative depends on the graph.Source: Distance-to-leaders vectors and PMI… · p. 13
• Applying the distance-based construction to the zero-forcing derived set gives a combined bound at least as large as either component bound, and strictly larger on nontrivial graph families.Adding the derived-set nodes to the leader set does not change the controllable subspace.Source: Distance-to-leaders vectors and PMI… · p. 13
• Exact longest-PMI computation takes O(m(n log n + nm)) time after distances are known, while a greedy near-optimal approximation takes O(mn log n) and still yields valid lower bounds.Here, m is the number of leaders and n is the number of nodes; the exact method becomes intractable as leader count grows.Source: Distance-to-leaders vectors and PMI… · p. 13

4.5. Limitations and outlook

• Constrained matching in a bipartite representation gives necessary-and-sufficient SSC tests and can construct leader sets, but finding a minimum-cardinality set remains computationally hard (Jia et al., 2020; Trefois and Delvenne, 2015).Generalized zero-forcing variants extend color-change rules to additional graph classes and matrix subclasses.Source: §4.5 · p. 14
• General directed graphs lack exact SSCS-dimension characterizations, scalable leader-selection algorithms with guarantees are scarce, and unconstrained nonzero edge weights or static graphs may poorly represent real networks.Additional weight, sign, uncertainty, or parameter-correlation structure can make existing SSC conditions conservative or incomplete; many applications also involve changing topology, failures, or attacks.Source: §4.5 · p. 14
• Future directions include unified certificates, controllability–robustness co-design, resilient leader selection under perturbations, and scalable approximation, learning-based, or structural-reduction methods (Abbas et al., 2020, 2021; Mousavi et al., 2017b; Pasqualetti et al., 2018, 2020).Adding edges can improve connectivity and robustness yet disrupt zero-forcing propagation or distance-based certificates; leaky forcing and related variants may support perturbation-resilient leader selection (Abbas, 2025; Alameda et al., 2022, 2023).Source: §4.5 · p. 14

5.3. Classical invertibility

• Classical invertibility requires the zero-state input-to-output map to be injective, and is incompatible with systems whose inputs outnumber their outputs.The section recalls geometric, rank-based, and spectral characterizations of this property.Source: §5.3 · pp. 15–16

5.4. Sparse invertibility

• Sparsity can permit invertibility even when a system has more inputs than outputs, by exploiting restrictions on admissible input supports.The section generalizes classical geometric, rank-based, and spectral characterizations to sparse inputs.Source: §5.4 · p. 16

5.4.1. Geometric characterization

• For geometric characterization, s-sparse invertibility is equivalent to a relaxed condition that exploits sparse-input injectivity rather than requiring unrestricted input injectivity.The discussion relates this relaxation to weakly unobservable states and sparse recovery.Source: §5.4.1 · p. 16

5.4.2. Rank-based characterization

• Every s-sparse invertible system has finite inherent s-sparse delay, but tractable bounds on that delay remain open.The inherent delay is the least delay of any sparse input recovery algorithm.Source: §5.4.2 · p. 16

5.4.3. Spectral characterization and invertibility under periodic sparsity

• A spectral characterization applies to τ-periodically s-sparse inputs, whose support schedules repeat even though input values need not.At τ = 1, the condition reduces to the standard Rosenbrock-matrix condition for constant support; a finite upper bound on τ to check is also available.Source: §5.4.3 · pp. 16–17

5.5.1. Noiseless case with Laplace prior

• In the noiseless Laplace-prior case, exact MAP recovery of every s-sparse input is equivalent to a generalized nullspace condition that uses piecewise sparsity.The proof leverages that piecewise s-sparsity is more restrictive than Ks-sparsity of the stacked input.Source: §5.5.1 · p. 17

5.5.2. Noisy case with Laplace prior; 5.5.3. Noisy case with hierarchical prior

• For noisy Laplace-prior estimation, RKS combines soft-thresholding with Kalman smoothing and has implementation complexity linear in the horizon K.A hierarchical prior permits exact sparse recovery in more instances, at the cost of nonconvexity, and is handled with SBL-RKS.Source: §5.5.2 · pp. 17–18, §5.5.3 · p. 18

5.6. Limitations and Outlook

• Minimal conditions for computationally tractable, stable sparse-input inverses remain unavailable; efficient online methods, recovery phase transitions, and right-invertibility are also open directions.Infinite-horizon sparse-invertibility conditions do not themselves guarantee tractable algorithmic recovery.Source: §5.6 · p. 18

6.1. Motivation

• Sparse sensor attacks matter because compromised measurements can threaten safety in cyber-physical systems, while actuator attacks affect system dynamics and connect to sparse invertibility.The section focuses on state estimation in the presence of sensor attacks.Source: §6 · p. 18, §6.1 · pp. 18–19

6.2. Setup

• Secure state estimation is underdetermined: the model supplies pτ equations for n + pτ unknowns, and adding sensors or measurements also adds attack variables.The setup jointly estimates the system state and sparse attack vector, assuming the attack-free system is observable.Source: §6.2 · p. 19
• Attack sparsity can make the underdetermined estimation problem well posed under suitable conditions, motivating compressed-sensing formulations.Basis Pursuit seeks a sparsest solution, while LASSO uses an ℓ1 relaxation that accounts for measurement noise.Source: §6.2 · pp. 19–20

6.3. Sparse sensor attacks with time-invariant support

• s attacks with constant support are correctable after τ steps exactly when every nonzero state direction satisfies the stated sensor-support condition.The section presents this as a fundamental limitation for secure state estimation.Source: §6.3 · p. 20
• The estimation problem has a unique solution with at most s estimated attacks and constant support if and only if the system is 2s-sparse observable.This means observability persists after removing any set of 2s sensors.Source: §6.3 · p. 20
• Both stated correctability criteria require combinatorial-time verification, and secure state estimation is impossible when more than half the sensors are attacked.Source: §6.3 · p. 20

6.4. Sparse time-invariant sensor attacks

• Constant attacks simplify the dynamics, but sparsity information is still needed because the resulting system may not be observable.The attack is assumed constant over a finite observation horizon in applications where attack dynamics are slower than the CPS.Source: §6.4 · pp. 20–21
• With constant-valued attacks, an eigenvalue of 1 in the attack-free dynamics makes the augmented attacked system unobservable, even if the attack-free system is observable.Such eigenvalues occur in applications including stochastic-matrix dynamics and power networks.Source: §6.4 · pp. 20–21

6.5. Online sparse observers

• For time-invariant attacks, online observers estimate the augmented initial state using only the current measurement, with no delay when τ=1.Source: §6.5 · p. 21
• In the fully online setting τ=1, earlier hard- and soft-thresholding observers do not achieve satisfactory numerical performance.Source: §6.5 · p. 21

6.5.1. Proximal operator-based algorithms

• Proximal online updates combine data consistency, attack-only ℓ1 regularization, and a term that keeps successive estimates close.Source: §6.5.1 · p. 21
• O-PAM replaces O-PGD’s gradient step with a regularized pseudo-inverse, reducing iterations to convergence at the cost of potentially expensive matrix inversion.Source: §6.5.1 · p. 22

6.5.2. Bregman methods

• For online sparse estimation, BLB provides unbiased state and attack estimates, unlike O-PGD.Source: §6.5.2 · p. 22

6.6. Sparse actuator attacks

• Robust minimal controllability tolerates unavailable actuators but does not detect which actuators fail or when, and assumes enough actuators can be allocated to counter faults.Source: §6.6 · p. 22
• Attacks exciting only system zero dynamics are undetectable, linking attack detectability and identifiability to invariant zeros.Source: §6.6 · p. 22
• The reviewed model includes known control input and unknown sensor and actuator attacks; an SMT-based algorithm addresses state estimation with both attack types.Source: §6.6 · p. 22
• State recovery is possible when the CPS is (2r, 2s)-sparse strongly observable.Source: §6.6 · p. 22

6.7. Limitations and outlook

• Offline sparse estimation under sensor attacks is well established, while online sparse observers remain an active research area.Source: §6.7 · p. 22

7 MAXIMUM HANDS-OFF CONTROL 23

• Bregman-method convergence has been rigorously established only for systems with periodic behavior.Source: §7 · p. 23
• Comprehensive theoretical analysis with measurement and process noise, and extensions to nonlinear systems, remain unresolved.Source: §7 · p. 23
• Arbitrarily time-varying attacks make counteraction significantly harder without multiple measurements, and online-observer stability is still under investigation.Source: §7 · p. 23
• Learning-based, game-theoretic, and time-varying convex optimization methods are identified as promising research directions.Source: §7 · p. 23

7.1. Motivation

• Maximum hands-off control minimizes control support length, equivalently maximizing the duration for which the input is exactly zero.Source: §7.1 · p. 23, §7.2 · p. 23
• This temporal sparsity is also called sparse, coasting, or green control and is associated with resource conservation, energy efficiency, and environmental sustainability.Source: §7.1 · p. 23
• Because the L0 objective is highly nonconvex, the section considers L1 relaxation, whose equivalence to L0 depends on assumptions on A and B.Source: §7.1 · p. 23

7.2. Setup

• The formulation uses a continuous-time system over a fixed finite horizon, with the control subject to box constraints.Source: §7.2 · p. 23
• The feasible set is nonempty when T exceeds the minimum admissible-control time T*(x_in), provided that time is finite.Source: §7.2 · p. 23

7.4. Equivalence between 𝐿0 and 𝐿1 optimal control problems

• Under Assumption 1, nonsingular A, and controllability of every single-input pair (A, b_i), weighted L1 relaxation and the original L0 problem have identical solution sets.The resulting controls are bang-off-bang, with no direct switches between +1 and −1; their switch count is bounded by 2nm(1 + Tω/π), where ω is the largest imaginary part of A's eigenvalues.Source: §7.4 · p. 24

7.5. Non-convex optimization for singular cases

• For singular A, including the double integrator, convex relaxation cannot be relied on; instead, a surrogate cost is sought, and under Assumptions 1 and 2 Problem 8 has the same solution set as Problem 6.Theorem 19 states that at least one solution to Problem 8 exists.Source: §7.5 · pp. 24–25

7.6. Limitations and outlook

• The infinite-horizon hands-off problem remains open: receding-horizon control may lose sparsity despite sparse finite-horizon predictions, and simple sufficient equivalence conditions for nonlinear systems are still needed.Oishi et al. (2026) proposed diminishing weights for discrete-time linear time-invariant systems; the general problem remains open.Source: §7.6 · p. 25

8.1. Motivation; 8.2. Setup and 𝑠-sparsity constraint

• Sparse actuator control limits each input vector to at most s nonzero components per time step, with active actuators allowed to vary over time, to meet resource or physical constraints.Applications include communication-limited networked control, infrastructure, social networks, and biological interventions.Source: §8.1 · pp. 25–26, §8.2 · p. 26

8.3. Foundations of 𝑠-sparse controllability

• Sparse controllability is equivalent to both a time-varying actuator-support rank test and a PBH-type test requiring rk([A−λI B]) = n for each eigenvalue and s ≥ max{1, n−rk(A)}.The PBH-type test is more tractable; when rk(A) ≥ n−1, classical controllability implies s-sparse controllability for any s ≥ 1. If s ≥ rk(B), standard and sparse controllability are equivalent.Source: §8.3 · pp. 26–27

Extensions to related system properties

• Sparsity leaves stabilizability equivalent to classical stabilizability, but nonnegative controllability additionally requires s ≥ n−rk(A); complete necessary-and-sufficient conditions for sparse output controllability remain open.The sufficient and necessary output-controllability conditions coincide in cases including diagonalizable A or rk(A) ≥ n−1.Source: Extensions to related system properties · p. 27

8.4. Design of 𝑠-sparse actuator control inputs

• Sparse-input design can be formulated as sparse recovery of a stacked input vector that steers the system between states, allowing compressed-sensing methods such as convex Basis Pursuit.At most n control inputs need be considered, and the input support may change over time.Source: §8.4 · p. 27
• Standard sparse recovery requires the whole stacked control input to be sparse, unlike attack recovery that sparsifies only the attack component; guarantees depend on reachability-matrix structure such as coherence or restricted isometry.Greedy compressed-sensing methods can iteratively select columns that best match the residual.Source: §8.4 · p. 28
• Piecewise sparsity limits active actuators at each time step while minimizing total nonzero inputs; piecewise OMP and compressive sampling matching pursuit enforce this constraint.Each time-step group contains at most s nonzero entries.Source: §8.4 · p. 28

8.5. Limitations and outlook

• Piecewise sparse recovery addresses per-time-step limits, but remains underexplored theoretically and algorithmically despite established foundations for s-sparse control.Standard formulations promote sparsity across the entire stacked input rather than explicitly enforcing its desired temporal structure.Source: §8.5 · p. 28
• Open design challenges include jointly optimizing sparsity and control energy, reducing per-state-pair recovery costs relative to least squares, and respecting actuator saturation bounds.Standard sparse-recovery and greedy-selection algorithms do not account for saturation.Source: §8.5 · p. 28
• Preselected state-independent actuator schedules can guarantee controllability and avoid combinatorial pattern search, but may not be optimal for a particular initial–final state pair.For sparse controllable systems, schedule existence follows from statement (b) of Theorem 20.Source: §8.5 · p. 28

9.1. Motivation

• Time-varying schedules optimize resource use under budgets and can address transmission limits, mechanical stress, and improved stability or performance; actuator schedules select reusable supports rather than one-time sparse inputs.Unlike static selection, a schedule changes the active actuator or sensor set over time.Source: §9.1 · p. 29

9.2. Optimal sensor schedules via tree pruning

• For finite-horizon Kalman sensor scheduling, Vitus et al. (2012) prune redundant branches using monotonicity and concavity of the Riccati map, with an ε-relaxed variant trading accuracy for speed.The relaxed method's excess cost grows at most linearly in ε, but retained characteristic pairs can still grow prohibitively, motivating a further ε-redundant variant.Source: §9.2 · p. 29

9.3. Kalman filter: fundamental limits

• Ye et al. (2018) show static Kalman sensor selection admits no constant-factor polynomial-time approximation, while common covariance metrics generally lack submodularity and multi-step guarantees require restrictive conditions.Jawaid and Smith (2015) show common covariance metrics, including terminal log-determinant, are generally not submodular over schedules; under restrictive noiseless-system assumptions, normalized log-determinant is sequence-submodular and greedy achieves roughly 0.47 of optimal. Tzoumas et al. (2016) establish a positive static result under independent state measurements.Source: §9.3.1 · pp. 29–30, §9.3.2 · p. 30

9.4.1. Gramian sparsification under average budget

• A deterministic spectral-sparsification algorithm produces one weighted schedule that approximates every systemic Gramian metric, with a meaningful approximation possible when dT > n.It recasts actuator-time contributions as rank-one terms and sparsifies their whitened Gramian; fewer than n total activations cannot yield a full-rank Gramian.Source: §9.4.1 · pp. 30–31

9.4.2. 𝑠-sparse actuator scheduling

• For s-sparse schedules, naive greedy selection can reach a dead end, but Ballotta et al. (2024) use sufficient controllability conditions to guide search over feasible schedules.The conditions identify independently selectable actuator subsets sufficient for controllability at each time; a modified greedy method builds from these subsets, with an MCMC variant that replaces actuators among feasible schedules.Source: §9.4.2 · p. 31

9.5. Optimal control-based actuator scheduling

• Under perfect state transitions, Chamon et al. (2019) derive a greedy suboptimality bound for weakly supermodular LQG cost; Jiao et al. (2023) provide a consistent convex relaxation for unitary budgets.An integer solution of Jiao et al.'s relaxation recovers an optimal schedule; in general the relaxation is real-valued, and their recovery algorithm has a provable suboptimality gap.Source: §9.5 · p. 32
• Ye et al. (2024) study data-driven actuator selection in episodic and non-episodic settings, establishing sublinear regret under technical conditions on episode duration and changes in optimal actuator sets.Their non-episodic method groups a trajectory into virtual episodes, while a large-scale extension uses parallel Exp3.S instances and analyzes the weaker c-regret.Source: §9.5 · pp. 32–33

9.6. Limitations and outlook

• Only a few works formally guarantee time-varying schedules for Gramian metrics and LQG cost, addressing Problems 11 to 13.Both point-wise and average budget constraints need further study; average budgets appear unaddressed in linear quadratic control optimization, while Problem 13 is its point-wise-budget counterpart.Source: §9.6 · p. 33
• Greedy selection lacks formal suboptimality guarantees, apart from weak supermodularity of noiseless-state-transition LQG cost (Jiao et al., 2023).The passage calls for investigation under more general conditions and for other cost functions.Source: §9.6 · p. 33
• Sparse actuator-scheduling algorithms remain in their infancy, motivating approaches that improve performance, guarantee feasibility or suboptimality, and address computational bottlenecks.Examples include checking submatrix ranks (Ballotta et al., 2024) and searching large design spaces.Source: §9.6 · p. 33

10. Sparse convex online optimization

• The section’s scope is online updating of sparse minimizers as new cost functions arrive, with dynamic-regret guarantees for centralized and distributed methods.Source: §10 · p. 33

10.1. Motivation

• Unstructured methods use revealed problems without prior evolution information, whereas structured methods exploit learned models to predict how minima evolve.The section reviews dynamic-regret analyses of proximal gradient descent and Douglas–Rachford methods for unpredictable sparse signals.Source: §10.1 · pp. 33–34

10.2. Setup

• Online methods update estimates when each cost is revealed because large dimensions and fast time scales can make solving each optimization problem infeasible.The setup uses dynamic regret to assess tracking of the time-varying minimizers.Source: §10.2 · p. 34

10.3. Dynamic regret of proximal-based algorithms

• For O-PGD, dynamic regret includes a quadratic path-length-like term, yet linearly decreasing changes between successive minimizers still yield sublinear regret.The theorem assumes bounded sensing-matrix and signal norms and a step size below the stated threshold.Source: §10.3 · p. 35
• Fosson (2021) reports that O-DR retains O-PGD’s regret bound and is faster and more responsive under switching or smoothly time-varying system-identification parameters.The bound carries additional technicalities from O-DR’s auxiliary variable.Source: §10.3 · p. 35

10.4. Distributed online algorithms

• Fosson (2021) extends dynamic-regret analysis to distributed O-DISTA, whose regret is bounded in relation to variability in the minimizers being tracked.The bound is described as analogous to the path-length-dependent centralized bound.Source: §10.4 · p. 36
• A distributed subgradient method that shares only node-state signs has dynamic regret linear in path length under compactness constraints on the state space.Source: §10.4 · p. 36

10.5. Limitations and outlook

• Model-based structured methods are more developed for smooth online optimization; extending them to sparse online optimization remains open.Source: §10.5 · p. 36

• Nonconvex regularizers have yielded faster proximal-gradient algorithms than 𝓁1-regularized problems, but their convergence analysis is more challenging.Source: §11 · p. 37
• Using the regularization parameter 𝜆 as a control input can reduce proximal-gradient sparsity overshoot, the transient before the estimate exhibits the desired sparsity pattern.Source: §11 · p. 37
• The control-theoretic approach is presented as a way to estimate sparse-signal support more responsively, particularly in time-varying settings.Source: §11 · p. 37

• The surveyed work shares a structure of selecting only a limited number of active control actions, actuators, measurements, or optimization variables, but remains divided across research streams.Source: §11 · p. 37
• Necessary and sufficient structural conditions in minimal actuator selection, strong structural controllability, and sparse input recovery can be difficult to exploit computationally at scale.The survey calls for scalable approximations with rigorous feasibility, recovery, or suboptimality guarantees.Source: §11 · p. 37
• Much existing theory assumes linear models, fixed networks, noiseless measurements, known observation models, or finite horizons, while practical settings may change over time.The survey identifies uncertain, nonlinear, and adversarial settings as common extensions to pursue.Source: §11 · p. 37
• Sparse control can reduce actuation while increasing control effort, so sparsity must be considered alongside other system-level objectives.The survey also names robustness, estimation accuracy, actuation constraints, and computational cost as relevant objectives.Source: §11 · p. 37
• The survey proposes stronger cross-fertilization and rigorous links between computational approaches and classical structural guarantees for increasingly complex systems.Source: §11 · p. 37