Abstract
Optimal sensor and actuator placement is a central challenge in high-dimensional estimation and control. Nearly all subsequent control decisions are affected by these sensor/actuator locations, and optimal placement amounts to an intractable brute-force search among the combinatorial possibilities. In this work, we exploit balanced model reduction and greedy optimization to efficiently determine sensor and actuator placements that optimize observability and controllability. In particular, we determine locations that optimize scalar measures of observability and controllability via greedy matrix QR pivoting on the dominant modes of the direct and adjoint balancing transformations. Pivoting runtime scales linearly with the state dimension, making this method tractable for high-dimensional systems. The results are demonstrated on the linearized Ginzburg-Landau system, for which our algorithm approximates well-known optimal placements computed using costly gradient descent methods.
The Combinatorial Challenge in High-Dimensional Systems
In modern engineering—ranging from autonomous drones to climate modeling—systems often involve thousands or millions of state variables. Placing sensors and actuators in such high-dimensional spaces is a "combinatorial nightmare." For instance, selecting 10 sensor locations out of 100 possibilities yields over 17 trillion combinations, making brute-force search impossible. Traditional heuristics often rely on intuition, while gradient-based optimization requires computationally expensive repeated simulations. This work addresses the need for a mathematically rigorous, computationally efficient method that scales linearly with system size.
Methodology: Balanced Model Reduction and QR Pivoting
The proposed method combines two mathematical frameworks: Balanced Model Reduction (BMR) and QR pivoting. BMR identifies a coordinate system where the most "observable" directions (captured by sensors) and "controllable" directions (affected by actuators) are aligned and ranked. This transformation produces direct and adjoint modes that represent the system's most critical dynamics.
Instead of an exhaustive search, the algorithm employs QR decomposition with column pivoting on these balanced modes. This greedy approach iteratively selects the most "informative" or "unique" locations. The authors demonstrate that maximizing the log-determinant of the system's Gramians—a measure of the "volume" of the observable/controllable subspace—is an effective proxy for optimizing the $H_2$ norm. QR pivoting is specifically designed to find sub-matrices that maximize this volume.
Key Results and Performance
The algorithm's performance was validated using random state-space systems and the linearized Ginzburg-Landau equation, a benchmark for fluid flow instabilities. In synthetic tests, the QR-pivoting method consistently outperformed 99.95% of all possible random configurations.
For the Ginzburg-Landau system, the greedy QR algorithm produced placements that nearly perfectly matched those found by state-of-the-art gradient descent methods, but at a fraction of the computational cost. Notably, the algorithm naturally tends to "collocate" sensors and actuators, aligning with physical intuition for many vibration and flow control problems.
Conclusion and Future Work
By leveraging balanced modes and greedy matrix factorizations, this approach provides a scalable solution for sensor and actuator placement in massive systems. The linear scaling of the runtime ensures applicability to increasingly complex simulations. Future research will focus on extending these techniques to data-driven models where the underlying equations are unknown, and adapting the framework for highly nonlinear regimes.
Summary updated