Zero-Norm Distance to Controllability of Linear Dynamic Networks

In this article, we consider the 'nearest distance' from a given uncontrollable dynamical network to the set of controllable ones. We consider networks whose behaviors are represented via linear dynamical systems. The problem of interest is then finding the smallest number of entries/parameters in the system matrices, corresponding to the smallest number of edges of the networks, that need to be perturbed to achieve controllability. Such a value is called the zero-norm distance to controllability (ZNDC). We show genericity exists in this problem, so that other matrix norms (such as the 2-norm or the Frobenius norm) adopted in this notion are nonsense. For ZNDC, we show it is NP-hard to compute, even when only the state matrices can be perturbed. We then provide some nontrivial lower and upper bounds for it. For its computation, we provide two heuristic algorithms. The first one is by transforming the ZNDC into a problem of structural controllability of linearly parameterized systems, and then greedily selecting the candidate links according to a suitable objective function. The second one is based on the weighted l₁-norm relaxation and the convex-concave procedure, which is tailored for ZNDC when additional structural constraints are involved in the perturbed parameters. Finally, we examine the performance of our proposed algorithms on several typical uncontrollable networks arising in multiagent systems.