Calibratable Snapshot Scheduling for Black-Hole Movies

Radio telescopes spread across the Earth can image a black hole only by pairing up. Each pair of stations (a "baseline") measures one spatial-frequency component of the image. Because the atmosphere scrambles the phase each station records, a pair's phase is usable only when it closes a triangle with other working pairs; the station-specific errors then cancel around the loop. To make a movie of a fast-changing source such as Sagittarius A*, observers face a zero-sum choice in every few-minute frame. Integrating longer gives more baselines enough signal to be detected and joined into calibratable loops. Integrating shorter gives more frames and less motion blur. We propose to treat this as a scheduling problem. The goal is to choose which stations to use in each frame and how long to integrate, so that every scheduled measurement stays connected to a trusted calibration anchor. We then ask whether solving this exactly, with the right combinatorial constraints, yields better black-hole movies than the geometric and greedy rules astronomers use now.

The work draws on three literatures. From wireless sensing it borrows the sensing-throughput tradeoff: time spent sensing is time not spent transmitting, and the useful quantity is a product of the two. From sparse interferometry it takes the physics, the data, and the failure mode, which is sparse and anisotropic frequency coverage in short time bins. From parameterized algorithms it takes Cut & Count, an exact technique for connectivity constraints. The requirement that every measurement be connected to an anchor across time is a global connectivity constraint. Standard dynamic programming handles such constraints only by tracking every way the stations can be partitioned into groups. Cut & Count avoids that by counting cuts with parity (odd versus even) arithmetic.

Core Claim

In dynamic very-long-baseline interferometry (VLBI, the technique of linking distant radio dishes into one virtual telescope), the value of a frame is gated by topology. A baseline adds phase information only if it sits in a closed, detected loop. A station's amplitude is trustworthy only if a chain of detected baselines links it to an anchor. The chain can run within a frame, or across adjacent frames for the same station while its gain is stable. That anchor can be an intra-site pair or a well-calibrated large station.

Our claim has two parts. First, with this gating, frame utility is far from submodular (diminishing returns) and the best integration time per frame is coupled across frames. Rules that score frames independently, or add stations greedily, should therefore leave reconstruction quality on the table in the hard, anisotropic parts of a night. Second, the combinatorial core lives on a time-expanded graph. Its nodes are station-frame pairs; its edges are detected baselines within a frame plus gain-stability links between consecutive frames. This graph has path-like structure whose width grows with the number of stations, not the length of the night. Exact optimization under the anchor-connectivity constraint is therefore a bounded-width connectivity problem. For this class, Cut & Count gives running time single-exponential in width, where partition-tracking dynamic programming is Bell-number exponential.

The first part is the scientific claim. The second is an engineering claim that we will test against a generic integer-programming solver rather than assume.

Problem Formulation

Split a night of length $T$ into $F$ candidate frames. In frame $f$, choose a station set $S_f$ from those with the source above the horizon, and an integration time $\tau_f$ from a small discrete menu. A baseline between two chosen stations counts as detected when its predicted signal-to-noise ratio, which grows as $\sqrt{\tau_f}$ times the product of station sensitivities and weather-dependent transmission, exceeds a fringe-detection threshold. We solve

$$\max_{\{S_f,\tau_f\}} \sum_{f=1}^{F} \Big[\, U_f(S_f,\tau_f) - \lambda\, \mathrm{blur}(\tau_f) \Big] \quad \text{subject to} \quad \sum_{f=1}^{F} \big(\tau_f + c\,[\text{frame } f \text{ used}]\big) \le T,$$

with one extra condition: every chosen station-frame node must lie in a connected component of the detected time-expanded graph that contains an anchor. The symbols are defined as follows. $U_f$ is an additive coverage utility: the sum over detected baselines that lie in at least one closed detected triangle, weighted by how under-sampled that baseline's Fourier cell is. $\mathrm{blur}(\tau_f)$ is the motion-smearing penalty for a source whose structure changes on timescale $t_{\text{var}}$, taken as $(\tau_f/t_{\text{var}})^2$ from a small-displacement expansion. $\lambda$ trades the two terms. $c$ is the fixed per-frame overhead for fringe search and calibrator interleaving, the "sensing" cost in the sensing-throughput sense.

The structure mirrors the tradeoff that Zhang et al. formalize for UAV sensing. There, too much sensing makes data stale (their "freshness paradox"). They prove the single-cycle tradeoff is unimodal and schedule tasks with a knapsack-style dynamic program. Their scheduler has no graph constraints. Ours adds exactly the connectivity structure their decomposition cannot express.

Because $U_f$ is additive over edges and nodes after discretization, it fits the weight-tracking version of Cut & Count. Randomized integer weights, via the isolation lemma, break ties so that parity cancellation cannot hide the optimum. The true reconstruction objective is not additive, so the solver optimizes a surrogate. Every schedule is then judged by actual image reconstruction, never by the surrogate.

Research Program

The first component is the physical model. Using ngehtsim and the MERRA-2 weather reanalysis described in the ngEHT reference-array paper, we generate per-frame station availability, baseline signal-to-noise ratio as a function of integration time, and co-located anchor pairs. We do this for two arrays: the 2017 EHT configuration and the ngEHT reference array with its Phase 1 additions.

The second component is the solver. We build a path decomposition that sweeps forward in time. Each bag holds the stations of the current frame plus those being introduced from the next, so its width is about the station count $n$. Cut & Count runs with three states per node (unused, used on the left side of the cut, used on the right side), giving roughly $3^{n}$ states per bag. Two further dimensions are the frame's integration-time choice and a pseudo-polynomial weight index. The method comes directly from Cygan, Nederlof et al.. From the forest-like extensions of Gowda et al. we borrow the way they fold bounded-cycle requirements into parity dynamic programs, and adapt it to the closed-triangle gating in $U_f$.

We state plainly where this is and is not attractive. For $n$ around 8 to 12, brute force or integer programming is probably enough. For $n$ in the high teens to low twenties, $3^n$ stays feasible while Bell-number tracking does not. Beyond that, even $3^n$ fails. Measuring where that window actually falls on realistic instances is part of the work.

The third component is the analysis. We check whether the per-frame tradeoff between integration time and utility is unimodal here, as Zhang et al. proved in their setting. If it is, a cheap one-dimensional search can replace the integration-time dimension of the dynamic program. We also quantify how strongly closure gating breaks submodularity, by counting instances where adding one station raises utility by more than the sum of its pairwise contributions.

Baselines

The naive reference is a uniform schedule: every available station in every frame, with a fixed integration time chosen by a coarse sweep over the whole night, and no anchor constraint. It shows how much of any gain comes from scheduling at all.

The strongest existing method for this exact question is the isotropy-metric windowing of Farah et al.. That method scores instantaneous frequency coverage by angular isotropy and radial uniformity, and images only in high-scoring windows. It is the incumbent because it was built for dynamic Sagittarius A* imaging and validated on it. They report that in high-scoring regions, CLEAN and regularized maximum-likelihood imaging recovered hot-spot orbital position with an RMS error of 0.16–0.20 radians, with errors about tenfold larger in low-scoring regions. They also identify 01:30–03:10 GMST on April 7, 2017 as the best window, with about 40% better coverage quality than other windows. We run their metric on identical simulated observations. We give it the same integration-time menu, picking the best fixed integration time by the same sweep, and let it choose frames by thresholding its score to match our total time budget.

Beating it means two things on the orbiting-hot-spot model at a matched time budget. Our schedule must achieve lower orbital-position RMS error than 0.16–0.20 radians inside the golden window. More importantly, it must substantially shrink the tenfold degradation outside that window, because that is where independent frame scoring should fail.

The second competitor is greedy submodular selection in the spirit of Asif et al.. That paper picks sensors to maximize mutual information under a Gaussian prior and cardinality or matroid constraints. We apply it frame by frame, using our utility $U_f$ as the gain, with the same budget. No reported number on a VLBI benchmark was found on Lacuna for it.

The third competitor is not from the file but is the one a practitioner would reach for: a mixed-integer program. It encodes anchor connectivity with standard flow constraints and is solved by a commercial solver under the same wall-clock limit as our dynamic program. It tests whether Cut & Count is needed as the exact engine.

Two ablations isolate our ingredients. One keeps the exact solver but removes cross-frame gain links, so connectivity is enforced only within frames. The other keeps everything but fixes $\tau_f$, which removes the sensing-throughput choice. Every method's schedule feeds the same imagers: regularized maximum-likelihood with ℓ1 plus total-variation penalties as in Honma et al., and CLEAN. The same hyperparameter tuning, by cross-validation as Honma et al. do, is applied to all.

Why not just…?

Why not just use the isotropy metric to pick good windows? It is fast and it works where coverage is good. Farah et al. report it is about 100,000 times faster than cross-correlation. But it is passive and purely geometric. It ranks Earth-rotation windows for a fixed array. It does not know whether a baseline is detected at a given integration time, whether it closes a loop, or whether spending extra time on one frame would save a neighboring one. The authors also note it can be fooled by pathological configurations in which one long baseline dominates. This is a real threat inside the golden window, where we expect at best a modest gain. The out-of-window comparison settles it: if our schedule does not cut the tenfold error there, the metric is good enough and we will say so.

Why not just add stations greedily? The guarantee behind greedy selection rests on diminishing returns. Closure gating produces the opposite pattern: a baseline contributes no phase information until a third station closes its triangle, and then contributes all at once. Asif et al. themselves note their bounds loosen at low signal-to-noise ratio, which is the regime of short integrations. Our submodularity-violation count measures how often this bites. If violations are rare on realistic instances and greedy matches exact scheduling on reconstruction error, the combinatorial machinery is unnecessary for this application. That would be a publishable negative result.

Why not just solve an integer program, or run ordinary dynamic programming? For small arrays an integer program will likely be as good and simpler, and we expect that. Ordinary tree-decomposition dynamic programming must track every partition of the stations in a bag, which grows like a Bell number. Cut & Count replaces this with about $3^{n}$ states, and Cygan et al. show this base is tight under the Strong Exponential Time Hypothesis for connected vertex cover. Whether that asymptotic edge matters at 15 to 25 stations is an empirical question. If the integer program meets the time limit on ngEHT-scale instances, we will adopt it as the engine and report that Cut & Count was not needed. The scheduling results do not depend on which exact solver produced them.

Why not just improve the imaging algorithm instead of the schedule? Better priors help, as in the patch-prior method of Bouman et al. or the super-resolving regularization of Honma et al.. But Farah et al. show both CLEAN and regularized imaging collapse when a frame's coverage is badly undersampled. No regularizer restores frequencies that were never measured or phases that were never closed. We test this directly by running the strongest imager on every schedule, so any gain we report comes on top of good imaging.

Proposed Experiments

The main experiment uses the three dynamical Sagittarius A* synthetic models from Farah et al.: a rotating elliptical Gaussian, a static ring, and a ring with an orbiting hot spot. We observe them with simulated April 7, 2017 EHT coverage and with the ngEHT reference array, under a decade of MERRA-2 weather draws. The metric is hot-spot orbital-position RMS error in radians, reported separately inside and outside the golden window. Movie-level normalized RMS error and structural similarity against ground truth are secondary metrics. The static ring is a control: scheduling should not hurt it.

A second experiment checks that nothing breaks for static sources. It uses the M87 synthetic models (BL09, DJ1, J2, M16) from Honma et al. and the simulated sets in the VLBI Imaging Benchmark of Bouman et al.. No reported MSE or SSIM values were found on Lacuna for either of those papers, so we compare against our own reruns of their imagers.

A third experiment is purely computational. We compare wall-clock time and optimality gap for Cut & Count, partition-tracking dynamic programming, and the integer program as the station count grows from 8 to 25. The goal is to locate the window, if any, where Cut & Count is the only exact method that finishes. We also measure how often the isolation-lemma randomization fails and has to be repeated.

The decisive checks are three. The central claim fails if exact closure-aware scheduling does not beat the isotropy-metric baseline's out-of-window orbital error at matched time budget. The sensing-throughput component is unnecessary if the fixed-integration ablation matches the full method. The Cut & Count component is unnecessary if the integer program matches its runtime at ngEHT scale. Each outcome is informative, and we will report whichever occurs.