Choosing which few nodes of a large network to drive with actuators (or to watch with sensors) so that steering it costs little energy is a classic hard subset-selection problem. The usual tool is greedy selection: add, one at a time, the candidate that most improves an energy score computed from the controllability Gramian. The Gramian is the matrix that records how strongly the inputs can push the state in each direction. Greedy works remarkably well in practice, reaching over 90% of the optimum on 50-state networks. It is also slow. Every candidate's score requires solving a matrix equation of size $N \times N$ (a Lyapunov equation), so one greedy step costs roughly $N$ such solves. The fast randomized fixes developed for sensor selection sample only a few candidates per step, but they have a specific weakness here. When the hardest-to-control direction of the network is localized in a small corner of the graph, only a handful of candidates matter, and a random sample can miss all of them.
This note proposes a deterministic alternative. All the standard Gramian energy scores are concave functions of the Gramian, and the Gramian is additive over chosen actuators. Together these facts give a valid upper bound on every candidate's improvement. That bound can be computed for all candidates at once from a single "adjoint" Lyapunov solve per step. The bounds let us run exact greedy while computing true scores for only a short list of candidates. They also yield a cheap certificate: a number stating how far the chosen set can be from the true optimum, available on networks far too large for brute force.
Core Claim
Let $W(S) = \sum_{i \in S} W_i$ be the Gramian of actuator set $S$, where $W_i$ solves $A W_i + W_i A^\top + b_i b_i^\top = 0$ for a stable system matrix $A$ and candidate input column $b_i$. Let $f$ be an energy score that is concave and monotone in the positive-semidefinite order. This covers the negative average energy $-\mathrm{tr}(W^{-1})$, the log-determinant, and the worst-case score $\lambda_{\min}(W)$, where any supergradient $vv^\top$ from the minimum eigenspace works. For $f$ of this kind, concavity gives, for every candidate $i$,
$$ f(W + W_i) - f(W) \;\le\; \langle G, W_i \rangle \;=\; b_i^\top X\, b_i, \qquad A^\top X + X A + G = 0, $$
where $G$ is a (super)gradient of $f$ at the current Gramian $W$ and $X$ is the solution of the adjoint Lyapunov equation shown. The equality follows from taking traces of the two Lyapunov equations. It means that one solve for $X$ produces upper bounds $s_i = b_i^\top X b_i$ for every candidate. This holds for arbitrary input columns, including the 2,701 candidate HVDC links in the European grid model, where the number of candidates far exceeds the 148 states.
Two consequences follow. First, exact greedy only needs true scores for candidates taken in descending order of $s_i$, stopping once the next bound falls below the best true gain found. This is lazy evaluation made provably correct. Unlike classical lazy greedy, it does not rely on submodularity (the property that an element's gain can only shrink as the set grows), so it stays exact for the non-submodular $\lambda_{\min}$. Second, additivity and concavity give $f(S^\star) \le f(S \cup S^\star) \le f(S) + \sum_{i \in S^\star} s_i(S)$, and the last sum is at most the sum of the $k$ largest bounds. Every greedy iterate therefore yields an instance-specific upper bound on the optimum. This addresses the open problem that the $\gamma$/curvature guarantees of Summers and Kamgarpour are far looser than what greedy actually achieves. By duality with observability Gramians, the same construction applies unchanged to sensor selection.
Research Program
The method borrows its screening idea from Karimireddy et al., who replace the full coordinate scan in greedy coordinate descent with a gradient-based search. Our version differs in two ways. The "gradient" of a set-function step is obtained through a matrix-equation adjoint rather than stored explicitly. And the screen is an exact bound, not an approximate nearest-neighbour lookup.
The program has three parts. The first is algorithmic. We compute one Schur decomposition of $A$ and reuse it, so that each Lyapunov solve (adjoint or candidate) costs $O(N^2)$–$O(N^3)$ with a small constant. At each step we perform one adjoint solve, compute bounds for all candidates, and evaluate exactly in bound order. Candidate Gramians are never precomputed, which removes the $O(N^3)$-per-candidate memory that standard greedy needs.
The second part handles singular Gramians. Early in selection $W$ is rank-deficient, and inverse-based scores are undefined. We adopt the $\epsilon$-regularized score of Tzoumas et al., which bounds control effort for a point-to-point transfer, and apply it to $W + \epsilon I$. The regularized score remains concave, so the bounds and certificate hold for it. We will report how the certificate on the regularized objective translates to the unregularized one as $\epsilon$ shrinks, rather than claim more. This replaces the two-stage rank-then-energy heuristic of Cortesi et al., which has no joint guarantee.
The third part is analytical. We will relate the length of the short list, meaning the number of exact evaluations per step, to the curvature of $f$ along the greedy path. The expectation is that low curvature (bounds close to true gains) yields short lists. This is exactly the regime where Summers and Kamgarpour report near-optimal greedy behaviour. In the worst case the short list is the whole ground set, so the method is never worse than exact greedy plus one extra solve per step.
A noted inconsistency in the literature is whether $-\mathrm{tr}(W^{-1})$ is submodular: Cortesi et al. say yes, Summers and Kamgarpour treat it as non-submodular. Our method does not depend on how this is resolved, because it uses only concavity and monotonicity. That independence is part of its appeal.
Baselines
The naive reference points are uniform random placement and structural or centrality-based placement (degree and betweenness). They are run with the same budget $k$ and scored with the same energy metric. Prior work shows random sets are poor: greedy beat 99.93% of random combinations in Cortesi et al.. Structural placement is known to cause energy blow-ups (Doostmohammadian et al., Li et al.). These baselines anchor the objective scale.
The strongest quality baseline is full exact greedy as in Summers and Kamgarpour and Cortesi et al.. It achieves "over 90% of the globally optimal value" on 50-state ER, BA and L-mesh systems, and "approximately 98%" of the optimal log-determinant on a 25-state, 7-actuator system. Our method must return the identical set, verified by equality at every step. It counts as beating this baseline if it needs substantially fewer Lyapunov solves and less wall-clock time at the same Schur-reuse implementation, with the gap growing with $N$.
The strongest speed baseline is stochastic greedy from Mirzasoleiman et al., which samples $(N/k)\log(1/\epsilon)$ candidates per step. It reports 10x–100x speedups over lazy greedy on 10K Tiny Images. We also include its weak-submodular variant with matrix-inversion updates from Hashemi et al., which reports being "nearly 28 times faster than the standard greedy approach" for Kalman error. No reported result was found on Lacuna for stochastic or randomized greedy on controllability Gramian metrics, so we implement both on the same Schur-reuse Lyapunov solver and give them the same wall-clock budget. Beating them means matching or exceeding their energy score at equal time, and never suffering their failure mode on localized-weak-mode instances.
The strongest heuristic baseline is QR pivoting on balanced modes from Manohar et al.. On random systems its placements beat "99.95% of all possible random configurations", and it approximated gradient-descent placements "nearly perfectly" on the linearized Ginzburg-Landau system. We run it with the balancing rank tuned over a small grid. Two ablations isolate the key ingredient. The first uses the bound $s_i$ alone to pick candidates, with no exact verification, which removes the certificate of greedy exactness. The second replaces bound-ordering with uniform subsampling of the same short-list size, which removes the adjoint information.
Why not just…?
Why not just use stochastic greedy with lazy evaluation? On well-mixed Erdős-Rényi graphs this is a real threat and may match us at equal time. The risk lies in structured networks. As Tsekenis et al. and Li et al. show, energy is dominated by distant nodes and long control paths, so the useful actuators for the weakest direction may be a handful out of thousands. A random sample of size $(N/k)\log(1/\epsilon)$ then misses them with non-negligible probability, and its guarantee holds only in expectation and only for submodular $f$. Our localized-weak-mode experiments (below) measure this failure rate directly. If stochastic greedy loses nothing there, our contribution reduces to the certificate, and we will report that plainly.
Why not just run classical lazy greedy (priority queue of stale gains)? Its correctness requires submodularity, which fails for $\lambda_{\min}(W)$ (Summers et al.). Its first step also still needs all $N$ exact evaluations. Our bounds are valid at every step without submodularity and cost one solve to initialize. We compare solve counts directly for $\log\det$, where lazy greedy is exact, so that the comparison is fair on its home ground.
Why not just use QR pivoting on balanced modes? It is fast and often excellent. However, it maximizes modal volume, a proxy for log-determinant, and can leave a single direction poorly controlled, which is exactly what $\mathrm{tr}(W^{-1})$ and $\lambda_{\min}$ penalize. It also has no optimality bound, and it degrades when the actuator count differs from the truncation rank (Karnik et al.). Our certificate can be evaluated at QR's output as well, so we can state for the first time how close QR is to optimal on large instances. It may turn out to be close for log-determinant and worse for worst-case energy.
Why not just solve a convex relaxation and round? Hashemi et al. found randomized greedy "orders of magnitude faster" than semidefinite relaxations, with better error after rounding. We include a relaxation only at $N \le 200$ as a sanity check and do not expect it to compete.
Proposed Experiments
For ground truth we use ER, BA and L-mesh systems with 16 states, where brute force is possible, following the setup of Summers and Kamgarpour. We report the fraction of the optimum achieved and how tight the certificate is relative to the true optimum. For scale we use the same families at $N = 50, 200, 1000, 2000$. We measure Lyapunov solves per step, wall clock, short-list length, and certified gap, for all three energy scores.
Real systems are the Continental European grid model with 2,701 candidate links and $k = 10$ from Cortesi et al., and the IEEE 118-bus system used by Pasqualetti et al., whose boundary-node placement we add as a further structural baseline. For sensors and actuators together, we use the linearized Ginzburg-Landau benchmark from Manohar et al., running the observability-Gramian dual of our method against QR pivoting.
The decisive checks are three. First, identical selections to exact greedy on every instance, with short lists far smaller than $N$. Second, a family of planted localized-weak-mode networks: BA or ER cores with long pendant chains or mesh corners. On these we sweep localization and plot the success rate of stochastic greedy against ours at equal time. Third, certified gaps on the grid and on 2,000-state systems. If those gaps are within a few percent, we can make statements about near-optimality that were previously possible only at 16 states. If they are loose, that is itself informative, since it bounds how much any method could still gain.
References
- Performance guarantees for greedy maximization of non-submodular controllability metrics
- Efficient Greedy Coordinate Descent for Composite Problems.
- Minimal actuator placement with optimal control constraints
- Submodularity of Energy Related Controllability Metrics
- On the Observability and Controllability of Large-Scale IoT Networks: Reducing Number of Unmatched Nodes via Link Addition
- Sufficient control of complex networks
- Lazier Than Lazy Greedy
- Randomized Greedy Sensor Selection: Leveraging Weak Submodularity
- Optimal Sensor and Actuator Placement using Balanced Model Reduction.
- Spectrum of controlling and observing complex networks
- On Submodularity and Controllability in Complex Dynamical Networks
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Controllability Metrics, Limitations and Algorithms for Complex Networks