Sandip Roy

Lintao Ye, Sandip Roy, Shreyas Sundaram

Given a linear dynamical system, we consider the problem of selecting (at design-time) an optimal set of sensors (subject to certain budget constraints) to minimize the trace of the steady state error covariance matrix of the Kalman filter. Previous work has shown that this problem is NP-hard for certain classes of systems and sensor costs; in this paper, we show that the problem remains NP-hard even for the special case where the system is stable and all sensor costs are identical. Furthermore, we show the stronger result that there is no constant-factor (polynomial-time) approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering.

Mengran Xue, Sandip Roy

The controllability of networks comprising homogeneous multi-input multi-output linear subsystems with linear couplings among them is examined, from a modal perspective. The eigenvalues of the network model are classified into two groups: 1) network-invariant modes, which have very high multiplicity regardless of the network's topology; and 2) special-repeat modes, which are repeated for only particular network topologies and have bounded multiplicity. Characterizations of both types of modes are obtained, in part by drawing on decentralized-fixed-mode and generalized-eigenvalue concepts. We demonstrate that network-invariant modes necessarily prevent controllability unless a sufficient fraction of the subsystems are actuated, both in the network as a whole and in any weakly-connected partition. In contrast, the multiplicities of special-repeat modes have no influence on controllability. Our analysis highlights a distinction between built networks where subsystem interfaces may be unavoidable barriers to controllability, and multi-agent systems where protocols can be designed to ensure controllability.

Sandip Roy, Mengran Xue

Principal submatrices of the controllability Gramian and their inverses are examined, for a network-consensus model with inputs at a subset of network nodes. Specifically, several properties of the Gramian submatrices and their inverses -- including dominant eigenvalues and eigenvectors, diagonal entries, and sign patterns -- are characterized by exploiting the special doubly-nonnegative structure of the matrices. In addition, majorizations for these properties are obtained in terms of cutsets in the network's graph, based on the diffusive form of the model. The asymptotic (long time horizon) structure of the controllability Gramian is also analyzed. The results on the Gramian are used to study metrics for target control of the network-consensus model.

Sinan G. Aksoy, Ryan Bennink, Yuzhou Chen et al.

We present and discuss seven different open problems in applied combinatorics. The application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems.

Sandip Roy

The identifiability analysis of a networked Markov chain model known as the influence model, as described in a recent contribution to Arxiv, is examined. Two errors in the identifiability analysis -- one related to the unidentifiability of the partially-observed influence model, the second related to an omission of an additional recurrence criterion for identifiability -- are noted. In addition, some concerns about the formulation of the identifiability problem and the proposed estimation approach are noted.

Mengran Xue, Sandip Roy

A hybrid model for opinion dynamics in complex multi-agent networks is introduced, wherein some continuous-valued agents average neighbors' opinions to update their own, while other discrete-valued agents use stochastic copying and voting protocols. A statistical and graph-theoretic analysis of the model is undertaken, and consensus is shown to be achieved whenever the network matrix is ergodic. Also, the time required for consensus is characterized, in terms of the network's graph and the distribution of agents of different types.

Sandip Roy, Mengran Xue

Conditions for the detectability of topology variations in dynamical networks are developed in a recent article in the IEEE Transactions on Control of Network Systems [1]. Here, an example is presented which illustrates an error in the network-theoretic conditions for detectability developed in [1].