Scheduling Fusion-Frame Reconstruction for Anytime Accuracy

When a signal is measured by many distributed sensors, each sensor often sees only a slice of it. For example, a small cluster of microphones on a spherical array hears the sound field only through its own directional sensitivities. The mathematics of fusion frames treats each slice as a projection of the signal onto a low-dimensional subspace, and recombines the slices with a dual operator, the inversion rule that maps the redundant pieces back to one signal. Redundancy is the point: the signal can be recovered even when some pieces are missing or perturbed. In a real processing pipeline, this means reconstruction does not have to wait for every piece. Some processors are slow, some pieces are expensive to compute, and a usable estimate exists as soon as enough of the right pieces have arrived. The theory of dual frames already says how reconstruction quality degrades when pieces are missing or perturbed. Scheduling theory already says how to order jobs so that average waiting time is small. Nobody has joined the two.

We propose to schedule the per-subspace reconstruction jobs by predicted error reduction per second of compute. This is Smith's ratio rule, a classical scheduling rule that orders jobs by weight divided by processing time. Here each job's weight comes from a frame-theoretic prediction of how much the reconstruction error drops if that subspace is added next. The objective is not makespan, meaning the time until every job finishes. It is the weighted average time until each signal's reconstruction first falls below a target error. We will test this on real multi-channel acoustics from Spatial LibriSpeech, under straggler patterns drawn from the production trace in ATLAS. The same experiments also check, for the first time on physical data, whether the perturbation bounds of dual frame theory predict real reconstruction error.

Core Claim

The claim has two parts. The first is that, in distributed subspace reconstruction, the order in which subspace jobs finish matters as much as how fast they run. The second is that an error-aware priority rule reaches a target accuracy sooner on average than size-based or fair-share queues run on the same hardware. The second part is only interesting if error reduction per job is poorly correlated with job size. If the most informative subspaces are also simply the cheapest, shortest-job-first already captures the gain, and the proposal says so and stops. That correlation is therefore measured first.

Where This Sits

Frame theory supplies the prediction but has never been confronted with latency or data. Kutyniok, Paternostro and Philipp prove that canonical duals of fusion frames stay stable under small perturbations of the subspaces. They leave alternate duals open and give no computational or empirical treatment. Aldroubi proves that reconstruction error depends continuously on sampling jitter, device imperfections and generator drift, but with non-constructive constants. We use these results as the motivating theory, and our experiments fill the numeric gap they leave. Reconstructing from a subset of subspaces is itself a dual of a subframe, so measuring its error along the schedule gives an empirical probe of the alternate-dual question. It is not a proof.

Casazza et al. and Kutyniok et al. supply the modeling choice that sensor nodes correspond to subspaces. Boufounos, Kutyniok and Rauhut supply the block-sparse extension, which recovers signals active in only a few subspaces by minimizing a sum of per-subspace energies. They report a "blessing of dimensionality": failure probability decays roughly as $e^{-m}$ in the subspace dimension $m$. That paper constrains our design, because the cost of one projection grows roughly as $m^3$. Accuracy and latency therefore pull in opposite directions as $m$ grows, and our dimension sweep measures that trade-off.

The closest systems work is Parallel Compressed Sensing Reconstruction, which splits a sparse vector across identical processors and balances them with a random permutation. It reports 4.02 s centralized versus 0.85 s with four segments, for signals of length 1200 with 60 nonzero entries. It differs from our proposal on three counts. It partitions scalar coefficients rather than subspaces. It assumes identical, straggler-free machines. It optimizes finish-everything time rather than time-to-accuracy.

On the scheduling side, Select and permute and Jansen et al. give weighted-completion-time algorithms with worst-case guarantees but no experiments. ATLAS shows that such theory must be tested on skewed production workloads, where size-aware scheduling reached a completion-time ratio of 1.106 against 1.975 for Round Robin. Those works supply the method family and the empirical standard. None of them has a notion of a job whose value depends on which other jobs have already finished, and that dependence is the new ingredient here.

Research Program

Consider a fusion frame of subspaces $W_1,\dots,W_n$ with orthogonal projections $P_i$ and weights $v_i$. Each incoming signal $x$ (one short-time frequency bin of one audio frame) generates $n$ jobs, one per subspace, with processing times $p_i$ that depend on the subspace dimension and the machine. We learn a signal covariance $\Sigma$ from training rooms and fix a measurement noise level. From these, for any set $J$ of completed jobs, we can compute $E(J)$, the expected squared error of the best linear reconstruction from the projections $\{P_i x\}_{i\in J}$. This is a closed-form trace expression, and it equals the error of the canonical dual of the subframe when that subframe spans the space.

To account for perturbations, we inflate $E(J)$ by a robustness term. This term is proportional to the estimated calibration error of each subspace divided by the lower frame bound $A_J$ of the subframe, which is the form suggested by the Kutyniok–Paternostro–Philipp deviation bounds. When a machine frees up, the scheduler picks the pending job that maximizes

$$\rho_i(J) = \frac{E(J) - E(J\cup\{i\})}{\hat p_i},$$

where $\hat p_i$ is the predicted processing time on that machine. This is an adaptive Smith ratio: the weight is recomputed as the set of finished pieces grows. The objective is

$$\min \; \sum_s w_s\, T_s(\varepsilon), \qquad T_s(\varepsilon) = \min\{t : E_s(J_s(t)) \le \varepsilon\},$$

where $J_s(t)$ is the set of signal $s$'s jobs finished by time $t$, $w_s$ is a per-signal importance, and $\varepsilon$ is the target error. This is a total weighted completion time objective in which a signal "completes" when it becomes accurate enough, not when all its jobs are done. Because $E$ has diminishing returns in $J$, we expect greedy ordering to be near-optimal in the single-machine case. We will check that expectation against an exact time-indexed integer program on small instances, using the cutting planes of this formulation.

The concrete build has three pieces. The first is a fusion-frame encoder for the 19-channel spherical array in Spatial LibriSpeech. Neighboring microphone capsules are grouped into $n$ nodes, and each node's steering vectors span a subspace of spherical-harmonic coefficient space whose dimension grows with the harmonic order. The second is a discrete-event scheduler on a pool of 8 to 32 CPU workers. Per-worker slowdowns are resampled from ATLAS job-duration and recurrence statistics, which replaces the synthetic Pareto slowdowns the empirical-gap literature warns against. The third is a measurement harness that logs, for every signal, the realized error over time alongside the predicted $E(J)$ and the perturbation-inflated bound. Calibration is perturbed in controlled ways, through capsule position jitter and gain error, so that we can report explicit numerical perturbation thresholds where Aldroubi's are non-constructive. A secondary block-sparse track reconstructs few-source scenes with the mixed-norm objective of Boufounos et al. It tests whether the priority rule still helps when the reconstruction is nonlinear.

Baselines

The naive reference is first-in-first-out dispatch with a barrier: every signal waits until all of its subspace jobs finish, and is then reconstructed. This is what a pipeline built directly from the static dual-frame formulas would do. Round Robin across signals is included alongside it, because ATLAS reports Round Robin as the default at a completion-time ratio of 1.975 on its workload. That number is for ML cluster jobs, not reconstruction. We expect a similar ordering but will not assume the value transfers.

The makespan-oriented baseline assigns the longest jobs first to balance machines, combined with the structured permutation balancing of Fang et al.. It is the strongest method for finishing everything, and it tests whether time-to-accuracy is really a different target from makespan. We first rerun their synthetic setting (length 1200, 60 nonzeros, four segments) to confirm our implementation reproduces the reported 4.02 s to 0.85 s speedup qualitatively.

The strongest competitor for our objective is shortest-predicted-job-first with the same processing-time predictor we use. This is the size-based rule that won in ATLAS with a completion-time ratio of 1.106. It will be combined with partial reconstruction, meaning it may also emit an estimate as soon as $E(J)\le\varepsilon$, so the only difference from our method is the job ordering. For time-to-accuracy on fusion-frame acoustic reconstruction, no reported result was found on Lacuna, so this baseline's number will be measured by us.

The ablations are as follows:

  • Static Smith ratio. Weights are fixed at the fusion weights $v_i^2$, which isolates the value of recomputing error reduction as pieces arrive.
  • No robustness term. The perturbation term is removed, which isolates the contribution of dual stability theory.
  • Random order. Jobs are processed in random order with partial reconstruction, which isolates the value of partial reconstruction itself.

Every method uses the same workers, the same straggler traces, the same random seeds, the same reconstruction solver, and the same processing-time predictor, tuned once on held-out rooms. We will call it a win if our rule reduces mean weighted $T(\varepsilon)$ by at least 15% relative to shortest-predicted-job-first, with non-overlapping 95% bootstrap intervals over test rooms, while not increasing makespan by more than 5%.

Why not just…?

Why not just run one well-tuned iterative solver centrally and stop when it is good enough? Iterative frame algorithms are naturally "anytime," and a single fast machine avoids scheduling entirely. This is a real threat when data are small. It becomes weaker once acquisition is spread across nodes and the central machine must wait for data to arrive, because then arrival order dominates. We include a warm-started conjugate-gradient solver on the strongest single worker, given the same total compute, as a baseline. If it matches us at realistic array sizes, we will report that distributed scheduling is unnecessary in that regime.

Why not just use shortest-job-first, which already won on ATLAS? If error reduction per job is roughly proportional to job size, the two rules coincide. In that case the ATLAS result settles the question and our frame-theoretic weights add nothing. We measure the rank correlation between $E(J)-E(J\cup\{i\})$ and $p_i$ across rooms and harmonic orders before running anything else. We expect low correlation where cheap low-dimensional nodes are also redundant with each other, but if the correlation is high we will narrow the claim to the settings where it is low.

Why not just take a least-squares pseudoinverse of whatever has arrived, without any dual frame theory? That is what our reconstructor does. Dual theory is not needed to reconstruct. It is needed to predict error before a job runs, and to discount subspaces whose calibration is uncertain, as Duits et al. and Rondepierre et al. warn that poorly conditioned inversions amplify small errors. The no-robustness ablation shows directly whether that discount matters under jitter.

Why not just replicate every job and take whichever copy finishes first? Replication fights stragglers without any modeling. At equal total compute, though, it halves throughput. We run it as an equal-budget baseline. It may win at low load, and we will report the load level at which the priority rule overtakes it.

Decisive Checks

We will run three decisive checks.

  1. Correlation screen. We measure the rank correlation between predicted error reduction and processing time on Spatial LibriSpeech rooms. If the correlation exceeds 0.9, the idea is not worth pursuing.
  2. Head-to-head comparison. We compare mean weighted $T(\varepsilon)$ on held-out rooms against shortest-predicted-job-first under ATLAS-derived stragglers. This is the main result.
  3. Calibration check. On real room acoustics with injected capsule jitter, we compare predicted $E(J)$ and the perturbation-inflated bound against measured error. This yields explicit perturbation thresholds for this array, which is exactly the numeric content missing from the stability literature.

A final dimension sweep over spherical-harmonic order traces how accuracy and time-to-accuracy change with subspace dimension $m$. It reports whether the $e^{-m}$ accuracy gain survives once latency is counted.