Input matrix construction and approximation using a graphic approach

ABSTRACT

Given a state transition matrix (STM), we reinvestigate the problem of constructing the sparsest input matrix with a fixed number of inputs to guarantee controllability of the associated system. A new and simple graph-theoretic characterisation is obtained for the sparsity pattern of input matrices to guarantee controllability for a general STM admitting multiple eigenvalues, and a deterministic procedure with polynomial time complexity is suggested for constructing real valued input matrices satisfying the controllability requirement with an arbitrarily prescribed sparsity pattern. Based on this criterion, some novel results on sparsely controlling a system are obtained. It is proven that the minimal number of inputs to guarantee controllability equals the maximum geometric multiplicity of the STM under the constraint that some states can not be directly actuated by inputs (provided such problem is feasible), extending the existing results. Moreover, the minimal sparsity of an input matrix to ensure system controllability can be affected by the number of independent inputs. Furthermore, a graphic submodular function is built, leading to a greedy algorithm which efficiently approximates the minimal states needed to be directly actuated by inputs to ensure controllability for general STMs. To approximate the sparsest input matrices with a fixed number of inputs, we propose a simple greedy algorithm (non-submodular) and a two-stage algorithm, and demonstrate that the latter algorithm, inspired from graph colouring, has a provable approximation guarantee. Finally, we present some numerical results to show the efficiency and effectiveness of our approaches.

KEYWORDS:

• Input selection
• controllability
• submodularity
• matroid intersection
• greedy algorithms
• networked system

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. A state that is directly affected by an actuator is called an ‘actuated state’ in this paper for simplicity of notion. This state is associated with a nonzero row of the system input matrix.

2. More precisely, some algebraic elements are also involved in this characterisation. Since such characterisation is presented in terms of the input-state-mode digraph defined in Section 3, we still call it as graph-theoretic in a broad sense.

3. A 3-dimensional matching is a generalisation of bipartite matching. Given three disjoint sets X, Y , Z and a set T which consists of triples $(x,y,z)$ such that $x\in X$, $y\in Y$ and $z\in Z$, a three-dimensional matching is a set $M\subseteq T$ satisfying the following property: for any two distinct triples $(x_1,y_1,z_1)\in M$ and $(x_2,y_2,z_2)\in M$, we have $x_1\ne x_2$, $y_1\ne y_2$, $z_1\ne z_2$.

4. Given a collection $\mathcal{C}=\{{\mathcal{C}}_1,\dots ,{\mathcal{C}}_m\}$ of subsets of $\mathcal{M}$, a hitting set is a set ${\mathcal{C}}^{\ast }\subseteq \mathcal{M}$, such that ${\mathcal{C}}^{\ast }$ intersects with ${\mathcal{C}}_i$ for $i=1,\dots ,m$.

5. Notice that it is NP-hard to find the smallest number of colours to colour a given graph, under the setting that the number of available colours is fixed and to avoid colouring confliction a vertex can be assigned more than one colour simultaneously. If such problem is polynomially solved, then determining whether a graph has a k colouring is polynomially solved too, contradicting to the well-known fact that determining whether graphs admit a k colouring is NP-complete for $k\ge 3$.

6. To ensure that X is invertible, we transform X to be row diagonally dominant through adding the sum of absolutes of all entries in each row with the addition of 1 to be the corresponding diagonal entry.

Additional information

Funding

This work was supported in part by the National Natural Science Foundation of China (NNSFC) under Grant 61573209 and 61733008.