The disclosed embodiments relate to a system for performing prognostic surveillance operations on sensor data. During operation, the system obtains a group of signals from sensors in a monitored system during operation of the monitored system. Next, if possible, the system performs a clustering operation, which divides the group of signals into groups of correlated signals. Then, for one or more groups of signals that exceed a specified size, the system randomly partitions the groups of signals into smaller groups of signals. Next, for each group of signals, the system trains an inferential model for a prognostic pattern-recognition system based on signals in the group of signals. Then, for each group of signals, the system uses a prognostic pattern-recognition system in a surveillance mode and the inferential model to detect incipient anomalies that arise during execution of the monitored system.