Source-linked AI summary
Minimal Controllability Problems
Alex Olshevsky
TL;DR
The paper studies how to affect only a small number of variables while making a large-scale linear system controllable. It proves logarithmic-factor approximation is NP-hard, then provides a polynomial-time approximation matching that barrier and reports an unresolved theoretical question about an effective randomized heuristic.
Problem
The paper asks how to control large-scale systems when inputs can affect only a small number of variables.
Method
The paper develops randomized and then deterministic polynomial-time algorithms for approximating minimal controllability.
Results
Approximating the sparsest controllability vector or diagonal matrix within c log n is NP-hard, while a polynomial-time algorithm achieves a c′ log n approximation.
Takeaways & Limitations
Up to the constants, the paper resolves the polynomial-time approximability of the minimal controllability problem.
Takeaways & Limitations
The excellent performance of the randomized heuristic in generic settings lacks a theoretical justification and remains an open problem.
Abstract
from arXiv · showhide
Given a linear system, we consider the problem of finding a small set of variables to affect with an input so that the resulting system is controllable. We show that this problem is NP-hard; indeed, we show that even approximating the minimum number of variables that need to be affected within a multiplicative factor of $c \log n$ is NP-hard for some positive $c$. On the positive side, we show it is possible to find sets of variables matching this inapproximability barrier in polynomial time. This can be done by a simple greedy heuristic which sequentially picks variables to maximize the rank increase of the controllability matrix. Experiments on Erdos-Renyi random graphs demonstrate this heuristic almost always succeeds at findings the minimum number of variables.
1 Introduction
The paper studies how to make large linear systems controllable by affecting as few state variables as possible. It establishes a logarithmic-factor hardness barrier and a polynomial-time greedy approximation that is effective on simulated random graphs.
- Problem: Minimal controllability seeks the smallest variable set to observe or affect so the resulting linear system is controllable and observable.By controllability–observability duality, the paper focuses on finding a small affected set that ensures controllability.
- Positioning: The paper distinguishes plain controllability from structural or strong structural controllability and measures sparsity by affected state variables.Related work instead counts driver nodes or studies structural variants.
- Hardness: Approximating the sparsest controllability vector within c log n is NP-hard for some c > 0, including when A is symmetric; the diagonal-matrix variant has the same hardness.Thus even logarithmic-factor approximation is computationally intractable unless P = NP.
- Approximation: A polynomial-time algorithm returns a controllability vector or diagonal matrix with at most c′ log n times the sparsity of the optimum, assuming the feasible set is nonempty.The guarantee matches the hardness barrier up to the constants c and c′.
- Experiments: In Erdős–Rényi simulations, every tested graph was controllable from one or two nodes using the greedy heuristic.The heuristic sequentially adds variables that maximize the rank increase of the controllability matrix.
2 Intractability results for minimal controllability problems
The paper establishes that minimal controllability is hard to approximate, reducing the problem to structured hitting set instances and extending the hardness to symmetric systems and related formulations.
- Hardness reduction: The PBH test reduces minimal controllability to finding a minimum hitting set over supports of left-eigenvectors when A has distinct eigenvalues.The support of the input vector must intersect every left-eigenvector support.
- Hardness reduction: The reduction constructs a matrix from a hitting-set instance, with controllability sparsity tied to the hitting-set optimum.The constructed incidence-based matrix V encodes the collection of subsets.
- Approximation hardness: Approximating the sparsest controllability vector within c log n is NP-hard for some absolute constant c.Such an approximation would yield a comparable approximation for hitting set, contradicting known hardness unless P = NP.
- Matrix inputs: The same intractability extends from sparse vectors to sparse diagonal input matrices through a Gaussian construction and distinct eigenvalues.The sparsest vector and sparsest diagonal matrix have the same number of nonzero entries for the constructed matrix.
- Symmetric systems: A polynomial-time transformation transfers the hardness to symmetric matrices while changing minimal controllability by a factor between 1/3 and 2.The transformed matrix has distinct eigenvalues, and a 3k-sparse controllability vector can be constructed from a k-sparse one.
- Related formulations: Related sparse-input formulations remain NP-hard, including arbitrary-column input matrices and simultaneous controllability and observability with sparse matrices.The latter reduces to the sparse controllability problem already shown NP-hard.
3 Approximating minimal controllability
The paper develops greedy algorithms for minimal controllability that repeatedly add input components maximizing controllability-matrix rank increase. These algorithms achieve logarithmic-factor approximations in polynomial time for vector and diagonal formulations, under stated assumptions.
- Problem setup: The goal is to approximate minimal controllability by finding sparse vectors or diagonal matrices that render the system controllable.The vector formulation minimizes nonzero entries in b, while the diagonal formulation minimizes nonzero entries in B.
- Minimal vector controllability: The randomized vector algorithm repeatedly sets a zero entry to an independent standard Gaussian and chooses the update maximizing rank increase.It stops when no update can increase the controllability-matrix rank.
- Minimal vector controllability: rank(C(A, b)) equals the number of covered vectors t(i, j) when every eigenspace of A is one-dimensional.Coverage is defined through nonzero inner products with rows associated with Jordan blocks.
- Minimal vector controllability: With probability 1, the randomized algorithm returns a controllable vector with O(|b′| log n) nonzero entries whenever B is nonempty.Choosing b′ as the sparsest controllable vector yields an O(log n) approximation.
- Deterministic algorithm: The deterministic algorithm replaces infinite-precision random values while retaining an O(log n) approximation and polynomial running time.It terminates after at most n iterations, using polynomial-time rank calculations via Gaussian elimination.
- Minimal diagonal controllability: The same greedy rank-increase strategy gives an O(log n) approximation for the sparsest diagonal controllability matrix.After O(|B′| log n) iterations, the remaining uncontrollable subspace is empty.
4 Experiments with Erdos-Renyi random graphs
Experiments on directed Erdos-Renyi random graphs evaluated the randomized sparse-vector algorithm for systems up to 100 nodes. Nearly all tested systems were controllable with one nonzero input entry, and all were controllable with two.
- Experimental setup: The simulations used directed Erdos-Renyi graphs with link probability 2 log n/n and excluded matrices with eigenvalues within 0.01.The adjacency matrices served as the system matrices A.
- Results: 10,000 random adjacency matrices were tested across graph sizes up to n = 100.The experiments generated 100 random graphs for each n.
- Results: 9,990 of 10,000 matrices were controllable with a 1-sparse vector, while the remaining 10 required a 2-sparse vector.Thus every tested matrix was controllable with at most two nonzero entries.
- Interpretation: The authors report that the randomized protocol often finds extremely sparse controllable vectors.They do not provide a theoretical explanation for this observed performance in the simulated generic setting.
5 Conclusions
The paper establishes matching logarithmic-scale hardness and approximation results for minimal controllability, resolving its polynomial-time approximability up to constant factors. It also identifies generic-network algorithms and energy-related controllability as open directions.
- Main conclusion: Approximating the minimum number of affected variables within c log n is NP-hard, while a polynomial-time algorithm achieves a c′ log n approximation.The constants c and c′ may differ.
- Main conclusion: The difference between the hardness and algorithmic constants resolves the polynomial-time approximability of minimal controllability up to constants.This conclusion concerns the logarithmic approximation scale established by the paper.
- Open questions: Open questions include algorithms that are always exact but generically polynomial-time, and understanding how network structure affects control energy.The paper notes that real-world networks may possess generic features simplifying minimal controllability.