A monitoring center that can poll only a few of its many sensors per time slot has to decide which ones to refresh. Age of Information, which measures how long ago the monitor's latest reading from a sensor was generated, answers with a clock: refresh whatever is oldest. Readings from correlated sensors such as freeway loop detectors or temperature probes mostly move together along a few shared patterns. A stale reading from a sensor whose current value is predictable from its fresh neighbors costs nothing. A fresh-looking reading from a sensor that has started doing something its neighbors are not doing hides real error. We propose replacing elapsed time with residual age: the part of a sensor's current value that the monitor cannot reconstruct from fresher data. The scheduler then samples sensors at random, with probabilities set by two quantities from randomized linear algebra. The first is a leverage score, meaning how much a sensor's row pins down the shared low-dimensional pattern. The second is an age-inflated residual, meaning how far the sensor's last reading fell outside that pattern, grown by how long it has gone unchecked.
The opportunity is that each of the three literatures solves one piece in isolation. Adaptive residual sampling finds unexplained directions in a static matrix. Leverage scores identify structurally irreplaceable rows. AoI scheduling handles the clock and the channel. No existing method lets the monitor learn a drifting correlation structure from its own sparse, aged observations while spending bandwidth only where that structure fails. The deliverable is a scheduler and an analysis showing that, at equal bandwidth, it matches age-based schedulers on worst-case time to notice a new localized event, within a constant factor, while reducing the time-averaged error of reconstructing the full sensor field.
Core Claim
Suppose the field of $n$ sensor values at time $t$ is approximately $x(t) = U c(t) + e(t)$. Here $U$ is an $n \times r$ basis of shared patterns that drifts slowly, $c(t)$ holds the $r$ pattern coefficients, and $e(t)$ is a sensor-specific misfit that is usually small but can grow abruptly at a few sensors. When the monitor reconstructs $x(t)$ from the fresh readings at a set $S$, its expected squared error at an unpolled sensor $i$ splits into two terms.
The first is an in-subspace residual, $$v_i(S) = u_i^\top \left(I + \sigma^{-2} U_S^\top U_S\right)^{-1} u_i .$$ In this expression, $u_i$ is the $i$-th row of the current basis estimate $\hat U$, $U_S$ holds the rows of the sensors in $S$, and $\sigma^2$ is the observation noise level. The quantity $v_i(S)$ measures how poorly the fresh sensors determine sensor $i$'s share of the shared patterns. With no fresh sensors it equals $\|u_i\|^2$, the classical leverage score. As sensors are added to $S$, it shrinks into the sequential residual used to decompose volume sampling.
The second is an out-of-subspace residual, $m_i(t) = e_i^2 + \kappa_i \Delta_i(t)$. Here $e_i$ is the misfit observed at sensor $i$'s last poll, $\Delta_i(t)$ is its ordinary age, and $\kappa_i$ is an estimated rate of misfit growth. The linear growth in age follows from modeling the misfit as a random walk, whose variance grows in proportion to elapsed time.
The scheduler fills its $k$ polls per slot one at a time. It draws each sensor with probability $$p_i \propto (1-\gamma)\big[v_i(S) + m_i(t)\big] + \gamma / n ,$$ then adds the draw to $S$ and recomputes $v$ before the next draw. The small uniform floor $\gamma$ protects against a wrong basis.
Each direction plays a distinct role in this rule. Leverage scores make the first draw. Adaptive residual sampling governs the following draws within a slot and detects new directions. Age acts only as the clock that inflates misfit for sensors left unchecked. The claim is that randomizing over this score, rather than taking its maximum or ordering by age, is what lets the monitor both exploit the current subspace and discover where it has gone wrong.
Relation to Prior Work
The methods come from three sources.
The first is the residual-sampling line. Matrix approximation and projective clustering via volume sampling shows that sampling in proportion to squared residuals makes approximation error decay exponentially over rounds. Efficient volume sampling for row/column subset selection shows that joint volume sampling decomposes exactly into such sequential residual steps, which is why our within-slot draws are sequential. All of these assume a static, fully available matrix. Our matrix is a stream that the monitor sees only through its own polls, and each column grows stale at a different rate.
The second is the missing-data adaptive line, which supplies the subspace-update step. Column Subset Selection with Missing Data via Active Sampling projects partially observed columns onto the complement of the selected subspace so that budget is not spent on redundant columns. Low-Rank Matrix and Tensor Completion via Adaptive Sampling tests each column's membership in the current subspace with a few entries and samples the full column only when a residual appears, which removes the need for row incoherence. We reuse that membership test: a polled sensor with misfit well above noise triggers a rank-one basis expansion. We replace their repeated decompositions with incremental rank-$r$ updates, because the file notes that explicit SVDs are the bottleneck on streams. Both papers assume queries are answered instantly and that the matrix does not change while it is being queried. Neither holds over a lossy channel.
The third is the leverage-score line. Randomized algorithms for matrices and data establishes leverage scores as the filter that keeps rare directions. Statistical and Computational Trade-Offs in Kernel K-Means shows that ridge leverage scores, which add a regularizer, retain statistical accuracy from a fraction of the data. Our $v_i(S)$ is a ridge leverage score conditioned on the sensors already polled. Computational Efficiency under Covariate Shift in Kernel Ridge Regression constrains the design: it finds that a mismatch between training and test distributions undermines leverage approximations. This is why we never freeze the scores and why the uniform floor exists.
The AoI work motivates the problem and supplies constraints. Information Freshness for Timely Detection of Status Changes proves that plain age stops tracking detection delay in non-stationary models, while an entropy-based generalized age keeps an affine relation to it. That paper is restricted to scalar discrete chains. Residual age is our multivariate, continuous-valued analogue of this generalized age.
Age of Information Optimization and State Error Analysis for Correlated Multi-Process Multi-Sensor Systems jointly optimizes age and estimation error for correlated processes. It finds abrupt regime switches in the optimal sensing strategy, but assumes the coupling is known and fixed. We estimate the coupling online and let it drift.
Two papers constrain the channel model. Optimizing Age-of-Information in a Multi-class Queueing System shows that zero-buffer queues that drop stale packets avoid age blow-up, so we drop rather than queue. Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things shows that sampling immediately after each delivery is suboptimal under energy constraints. That result bears directly on the conflict with adaptive sampling's instinct to query immediately; we treat idling as an explicit option in one experiment.
Correlated Age-of-Information Bandits exploits correlation among channels, but only with binary rewards. Distributed State Estimation over Time-Varying Graphs: Exploiting the Age-of-Information uses age only as a passive filter that accepts strictly fresher neighbor estimates. Neither paper chooses what to observe based on subspace geometry.
Research Program
The work has three parts.
The first part is the algorithm. It consists of the sequential sampler above, an incremental basis tracker driven only by polled values, and per-sensor estimates of $\kappa_i$ obtained from misfit increments between successive polls. Each poll passes through a zero-buffer channel with random service time and erasure probability $\epsilon$. Lost polls leave $\Delta_i$ growing. The monitor reconstructs the full field each slot by ridge regression of the fresh readings onto $\hat U$.
The second part is the analysis. We will prove that the error decomposition holds under the stated model, so that the sampling rule targets an upper bound on reconstruction error. We will then prove two guarantees. The first is a detection-delay guarantee: a sensor whose misfit begins growing at rate $\kappa$ is polled within an expected delay bounded by the smaller of $n/(\gamma k (1-\epsilon))$ and a term that falls as its accumulated $\kappa \Delta$ comes to dominate the total score. The second is a tracking guarantee: after detection, the sensor is revisited at a rate proportional to its share of residual mass.
We expect the first-detection bound to be no better than round-robin's $n/k$ up to constants. That is the honest price of randomization. The gain should appear in average error, because predictable sensors stop consuming polls.
We will also check whether the gap between the $r^{3/2}$ and $k^2$ dependence on rank in theory and the linear dependence seen empirically in the missing-data papers persists in our streaming setting.
The third part is the empirical study described under Proposed Experiments.
Baselines
The naive reference is round-robin polling at the same $k$ polls per slot over the same channel. It has the best possible worst-case age and uses no structure.
The standard age-based scheduler is Max-Age-First: each slot, poll the $k$ oldest sensors. Where per-sensor rates rather than slot-by-slot choices are being tuned, we use the peak-age rate optimization of Optimizing Age-of-Information in a Multi-class Queueing System. Both are run with identical bandwidth, erasure rate, and reconstruction step, so they differ from our method only in which sensors get polled.
Static leverage placement computes ridge leverage scores once on the training split and polls the top-scoring sensors by age thereafter. This reflects the offline-placement view, and the drift and spatiotemporal-mirage observations in Spatial-Temporal-Decoupled Masked Pre-training for Spatiotemporal Forecasting suggest it should degrade under drift.
The strongest competitor is a plug-in greedy variance-reduction scheduler, which reflects the classical Kalman-filter view of scheduling. It runs our own online basis tracker but deterministically polls the sensors that most reduce the posterior variance of the reconstruction, with age entering through the same random-walk misfit model. It shares every ingredient with our method except randomization, and it is what a careful practitioner would build first. Its submodular cousin, distributed online greedy selection, has a reported result: Online Distributed Sensor Selection reports that its method "reached 95% of the performance of an offline algorithm … within just 100 rounds" on the Intel Berkeley temperature data. That is a coverage-utility metric, not reconstruction error under age, so it is not directly comparable. For greedy variance-reduction scheduling evaluated by reconstruction error under age, no reported result found on Lacuna. We will tune its noise and drift hyperparameters on the validation split with the same search budget as ours.
Three ablations isolate the key ingredients. The argmax version of our score removes only the randomness. Dropping $m_i$ leaves leverage and volume sampling with no age term. Dropping $v_i$ leaves pure age-inflated misfit.
Beating the strongest baseline means two things on at least three of the four datasets: lower time-averaged reconstruction root-mean-square error (RMSE) at equal bandwidth, and detection delay for injected events no worse than twice Max-Age-First's.
Why not just…?
Why not just poll the oldest sensor? Max-Age-First spends polls on sensors whose current value the fresh set already determines, and age alone stops tracking change once the process is non-stationary, as Information Freshness for Timely Detection of Status Changes shows. Its real strength is worst-case detection. We will therefore report detection delay alongside RMSE, and we concede the claim if our method loses on detection by more than a constant factor.
Why not just run greedy variance reduction with an online covariance estimate? This is the real threat. When the basis estimate is correct, greedy selection is likely near-optimal. Its failure mode is structural: a sensor that has low leverage under a wrong basis, and has recently shown little misfit, is never chosen, so a new pattern there is noticed only through the age term. The argmax ablation and the baseline above test exactly this. If deterministic greedy matches us under injected subspace changes, the randomization claim fails, and the contribution reduces to the residual-age score itself.
Why not let sensors send-on-delta, transmitting only when their value has moved enough? This sensor-side trigger needs no central model and is a strong simple alternative. It cannot see correlation, however. A shared shock fires every correlated sensor at once, causing collisions on a zero-buffer channel and redundant information, which is the waste that orthogonal projection avoids in Column Subset Selection with Missing Data via Active Sampling. It also requires continuous local sensing, which carries energy costs of the kind analyzed in Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things. We include it with tuned thresholds and the same channel. A regime of rare, uncorrelated events where it wins would be reported as a boundary of our claim.
Proposed Experiments
We use four benchmarks. PEMS04 and PEMS08 are freeway flow data at 5-minute intervals with the standard 6:2:2 train/validation/test split. The Intel Berkeley temperature deployment has 46 sensors, and the Pacific Northwest precipitation records cover 167 regions; both are used in Online Distributed Sensor Selection. We also use the correlated multi-process $M/M/1/1$ simulation of Age of Information Optimization and State Error Analysis for Correlated Multi-Process Multi-Sensor Systems, extended so that the coupling drifts. On the real data, the full recorded streams serve as ground truth, and each scheduler sees only the values it polls.
We sweep the bandwidth fraction $k/n$ from 2% to 20% and the erasure probability $\epsilon$ from 0 to 0.3. We report time-averaged reconstruction RMSE and mean absolute error over all sensors, along with ordinary average age for reference.
The first decisive check injects localized events into test streams: a misfit ramp at a single sensor, or a new rank-one pattern across a small cluster. We measure the delay until each scheduler's reconstruction error at the affected sensors falls back below twice the noise level. This check separates our method from deterministic greedy.
The second check runs the synthetic coupling drift through the regime-switch threshold reported in Age of Information Optimization and State Error Analysis for Correlated Multi-Process Multi-Sensor Systems, $\lambda_2 \approx 3.18$. It tests whether residual age reproduces the switch from specialized to distributed sensing without being told the coupling.
The third check adds an idle option, polling fewer than $k$ sensors when total residual mass is small, under an energy budget. It asks whether the idle regions predicted by Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things emerge from the residual score. That paper reports up to 33% lower average age than zero-wait under equal energy; we will check whether a comparable gap appears in reconstruction error rather than age.
Finally, on the synthetic low-rank setting of Low-Rank Matrix and Tensor Completion via Adaptive Sampling, we vary the rank $r$ over 10, 50, and 100 and record how the polls needed to reach a target error scale with rank.
References
- Matrix approximation and projective clustering via volume sampling
- Efficient Volume Sampling for Row/Column Subset Selection
- Column Subset Selection with Missing Data via Active Sampling
- Low-Rank Matrix and Tensor Completion via Adaptive Sampling
- Randomized Algorithms for Matrices and Data
- Statistical and Computational Trade-Offs in Kernel K-Means
- Computational Efficiency under Covariate Shift in Kernel Ridge Regression
- Information Freshness for Timely Detection of Status Changes
- Age of Information Optimization and State Error Analysis for Correlated Multi-Process Multi-Sensor Systems
- Optimizing age-of-information in a multi-class queueing system
- Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things
- Correlated Age-of-Information Bandits
- Distributed State Estimation Over Time-Varying Graphs: Exploiting the Age-of-Information
- Spatial-Temporal-Decoupled Masked Pre-training for Spatiotemporal Forecasting
- Online distributed sensor selection