Exact Centralized Uplink Combining over a Tree of Backhaul Hubs Built from Hypertree Decompositions

In a cell-free or cloud radio network, many distributed antenna sites (access points, APs) jointly decode many users. The best linear receiver, minimum mean-square-error (MMSE) combining, needs every AP's raw antenna samples at one central processor, and the transport links that carry those samples ("backhaul") cannot keep up. Current systems therefore choose among three compromises. They can compress the raw samples and ship them to a central star hub, they can combine locally at each AP and discard most of the joint-processing gain, or they can break the network into disjoint clusters. This note observes that the central MMSE problem has a structure the database and constraint-solving communities know well. Each AP contributes a term that involves only the users it actually hears, so the joint problem is a hypergraph: users are the vertices, and each AP is a hyperedge covering its served users. If that hypergraph has a low-width tree decomposition, the exact central solution can be computed on a tree of aggregation hubs. On such a tree, each link carries information only about the few users shared across the cut, the "separator", and never raw antenna samples.

The proposal builds this pipeline and measures when it wins. It borrows the parallel balanced-separator machinery of log-k-decomp and BalancedGo. These algorithms decompose large hypergraphs by repeatedly splitting them at small "balanced separators", pieces whose removal leaves halves of similar size, and log-k-decomp does this in logarithmic recursion depth. We use them to turn a wireless network into a hub tree whose per-link load is bounded by separator size and whose number of hops grows only logarithmically. The hop bound matters because latency accumulates per hop, and radio protocols impose hard deadlines such as the 3 ms retransmission loop cited by Simeone et al..

Core Claim

Consider the uplink model $y_a = H_a x_{U_a} + n_a$ at AP $a$. Here $U_a$ is the set of users AP $a$ keeps after pruning weak links, $x_{U_a}$ is their transmitted symbols, $H_a$ is the channel from those users to the AP's antennas, and $n_a$ is noise plus the residual power of the pruned users. The central MMSE estimate solves $J\hat{x} = h$, where

$$J = \frac{1}{p}I + \sum_a \frac{1}{\sigma_a^2} H_a^{H} H_a, \qquad h = \sum_a \frac{1}{\sigma_a^2} H_a^{H} y_a,$$

with $p$ the user transmit power and $\sigma_a^2$ the effective noise variance at AP $a$. Each summand is nonzero only on the block $U_a \times U_a$. So $J$ has the sparsity pattern of the hypergraph whose hyperedges are the sets $U_a$.

Take any tree decomposition of this hypergraph that places each $U_a$ inside some bag. Gaussian elimination can then proceed from the leaves to the root of that tree, exactly as in junction-tree inference. Once per coherence block, a tree link whose separator has $s$ users carries an $s \times s$ Schur-complement matrix, which summarizes everything below the link in terms of the separator users. Once per symbol, it carries an $s$-dimensional information vector. The root recovers the exact central estimate, and a top-down pass hands each subtree its decoded users.

The link to hypertree width is direct. Suppose each AP serves at most $d$ users, the per-AP cap that Bashar et al. already impose for backhaul reasons. Then a decomposition of generalized hypertree width $k$ has bags of at most $kd$ users, so every message on the tree has dimension at most $kd$. In this setting $k$ also has a physical meaning: it is the number of AP streams whose contributions a single hub must merge.

What is new is using a hypertree decomposition to produce a transport architecture. The width bounds per-link backhaul. Log-depth balanced separators bound the hop count. And the solution is exact rather than an approximation of central processing.

Relation to Prior Work

Two wireless papers motivate the gap. Bashar et al. compare raw forwarding to a star processor against local maximum-ratio combining. Local combining multiplies each AP's samples by its own channel conjugates and forwards the result, which is cheaper but lossy. They show that pruning weak user–AP links raises the minimum rate, but their topology is a flat star and their pruning is greedy and per-link. Jain et al. take a different route. They enforce group sparsity on a multicell equalizer, form clusters with spectral ratio cuts, and decentralize the design with ADMM (the alternating direction method of multipliers, an iterative scheme in which neighbors repeatedly exchange estimates until they agree). Their model is pairwise, and it needs dozens of message rounds.

Our approach differs from both. Users shared between regions are neither dropped nor handled by iteration; each crosses a tree link once, as a small Gaussian message.

Zhou et al. supply the strongest centralized competitor. They use Wyner–Ziv compression, in which each AP compresses its samples knowing the processor already holds correlated data from nearby APs, and they set each AP's quantization noise in proportion to its background noise. This gets within 1 bit per base station of the sum capacity of a star network. We treat it as the bar to beat at equal total backhaul, not as something to replace.

On the decomposition side, log-k-decomp, BalancedGo, and the HyperTrac overview supply the method. That includes the hybrid strategy of splitting in parallel with separators and then handing small subproblems to a sequential solver, Det-K-Decomp, below a size threshold. These tools were designed for database queries and constraint problems with unweighted hyperedges. We change the objective: separator size is counted in users, and separators must be placeable at a physical aggregation site.

PASCO and parallel multilevel hypergraph partitioning produce flat partitions. They serve as the disjoint-clustering reference point, not as the method.

One constraint must be stated up front. User–AP hypergraphs are geometric, so the separator of a two-dimensional deployment should grow roughly like the square root of the number of users crossing a cut line; this follows from standard planar-separator reasoning. The width will not stay constant as networks grow unless pruning cuts it down. The central object of study is therefore a three-way trade-off between the rate lost to width-reducing pruning, per-link backhaul, and tree depth.

Research Program

The first component is a width-aware pruning and decomposition loop. We start from Bashar-style large-scale-fading pruning. We then run a modified balanced-separator search in the style of log-k-decomp that scores candidate separators by user count weighted by the users' residual signal power. It rejects separators whose APs are more than a latency radius apart, which directly addresses the tension between choosing separators at arbitrary positions and the geography that fixes latency. When a separator exceeds a user budget $s_{\max}$, the weakest links crossing it are pruned and their power is moved into $\sigma_a^2$.

The second component is message quantization. Schur complements and information vectors are quantized with a per-link bit budget. We test whether the 12–14-bit saturation point that Bashar et al. report for raw samples also holds for these messages.

The third component is analysis. We will prove exactness of the tree computation when quantization is disabled. We will bound per-link load by $kd$ and depth by the logarithmic recursion guarantee of log-k-decomp. We will also characterize how $s$ grows with deployment density under a fixed pruning threshold.

Parallel computation matters in practice because the decomposition must be recomputed every scheduling epoch as users move. We will report wall-clock recomputation time against network size and core count. Log-k-decomp's own speedups are near-linear only up to 4 cores, so parallel speed is a secondary objective, not the headline claim.

Baselines

The naive reference point is Case 2 local maximum-ratio combining from Bashar et al. with uniform bit allocation, run at the same total backhaul. It shows how much joint processing is worth at all. The fully centralized upper bound is Case 1 with unquantized forwarding, which our method must match exactly at infinite bits.

The strongest cell-free competitor is the full Bashar et al. pipeline: max-min power control, receiver-weight optimization, and greedy pruning. They report a minimum user rate of 1.55 bits/s/Hz with pruning against 1.37 bits/s/Hz without. We will reproduce their Monte Carlo setup and run our method with identical AP and user drops, pilots, power limits, and total backhaul bits per coherence block. Beating them means a higher minimum or 5th-percentile user rate at equal total backhaul, or equal rate at lower maximum per-link load.

For the star with compression, the baseline is Zhou et al. Wyner–Ziv coding with the proportional quantization rule. It saves up to 25% of backhaul against uniform allocation and sits within 1 bit per base station of capacity. It will be run in the 19-cell hexagonal setup those authors used. Because a star places the entire backhaul load on the hub's links, the comparison reports both total backhaul and the busiest link's load.

For clustered cooperation, the baseline is Jain et al. sparse equalizer plus spectral clustering plus ADMM. They report 36% of the full-cooperation error reduction at 12% of the backhaul. We will count ADMM's iteration traffic and rounds in the same bit and latency units as our tree messages.

Two ablations isolate the key ingredients. The first replaces the hypertree search with an ordinary min-fill tree decomposition of the user interaction graph, which tests whether the hypergraph view and the separator scoring matter at all. The second replaces balanced separators with purely sequential Det-K-Decomp, which tests whether logarithmic depth matters for latency.

Why not just…?

Why not just use disjoint clusters from spectral or partition-based clustering? This is the zero-separator special case of our method. Users at cluster borders are either split across clusters or treated as noise. Jain et al.'s 36%-at-12% result suggests large gains remain between clustering and full cooperation. Our experiments sweep $s_{\max}$ from zero upward to show directly how much of that remaining gap a small separator recovers per extra bit.

Why not just compress everything to a central star with Wyner–Ziv coding? This is a real threat when total backhaul is the only metric, because Zhou et al.'s scheme is near-optimal for a star. Our case rests on per-link load and hop-constrained topologies, where a star forces every AP's stream onto the links into one site. If per-link load and total backhaul both favor the star at every density we test, the claim fails. We will report that outcome as a negative result.

Why not just use an ordinary tree decomposition via min-fill? For the elimination arithmetic, the bag size in users is what matters, so a plain tree decomposition may be enough. The hypergraph formulation adds two things. It enforces that each AP's term sits inside a single bag, which fixes where hubs must be, and it exposes a balanced-separator search that controls depth. The min-fill ablation settles whether either addition changes rate, load, or depth. If it does not, we will adopt min-fill and keep the balanced-separator depth control only if it survives the second ablation.

Why not just run iterative consensus (ADMM or Gaussian belief propagation) on the loopy graph? Iteration avoids building a decomposition. However, it pays per-round traffic and latency for dozens of rounds. We compare total bits and rounds to decode, per coherence block, against our single upward and downward pass.

Proposed Experiments

Networks range from 100 to 2,000 APs with 4 antennas each, at user loads from 0.2 to 1 per AP, using the Bashar-style Monte Carlo channel model and, separately, the 19-cell hexagonal model of Zhou and Jain. Metrics are minimum user rate, 5th-percentile user rate, total and maximum-per-link backhaul bits, tree depth, and decomposition recomputation time. Decomposition code is sanity-checked on HyperBench against the reported result that hybrid log-k-decomp solves 98.7% of instances with width at most 5.

Three checks are decisive. First, with quantization disabled, the tree estimate must equal central MMSE to numerical precision. Second, at fixed minimum rate, the maximum per-link backhaul must fall below both the star and the ADMM baselines, and the measured growth of $s$ with density must match the predicted square-root trend, or else show that pruning holds it flat at small rate cost. Third, the depth ablation must show that balanced separators keep hop counts within a latency budget that sequential decompositions exceed.