Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

This paper focuses on learning efficient sensor allocations that ensure observability of unknown high-dimensional linear systems using only a small number of sensors. Existing methods either require an impractically large number of sensors or assume access to an observable allocation in advance. We propose a two-stage framework that overcomes these limitations: first, a novel system identification algorithm integrates information from multiple trajectories, each observing different subsets of state coordinates; then, a classic sensor allocation method is adapted to operate on the learned system parameters. Our non-asymptotic guarantees show that the proposed approach learns a sensor allocation with a near-optimal number of sensors when sensors can be allocated on any state coordinate. We further extend the results to settings with inaccessible state coordinates that are unavailable for sensor allocation.