Certified 1-Bit Precoding: Only a Handful of Antennas Need Rounding

A base station with hundreds of antennas can serve many users at once by precoding: it chooses the signal each antenna sends so that the waves add up correctly at each user and cancel elsewhere. Cheap 1-bit digital-to-analog converters (DACs) make large arrays affordable, but they force every antenna to send one of only four values, $\pm 1 \pm j$. Choosing those values is a combinatorial problem. Exact solvers such as branch-and-bound stop at about a dozen antennas. The fast solvers used in practice are relaxations that push continuous values toward $\pm 1$. They work well in simulation, but nobody can say how far a given output is from the best discrete signal.

This note proposes a simple structural fact and builds on it. Relax the 1-bit set to the box $[-1,1]$, solve that convex problem, and then move within the set of box points that produce the same received signal until you reach a corner of that set. At such a corner, at most $2U$ of the $2B$ real antenna coordinates are not already $\pm 1$, where $U$ is the number of users and $B$ the number of antennas. So all of the discrete distortion comes from rounding roughly $2U$ antennas. The number of antennas $B$ never enters, and as $B/U$ grows the relative loss must shrink. The same convex solve also gives a per-channel lower bound on the true discrete optimum. Any fast 1-bit precoder (C2PO, GEMM, ADMM) can therefore report a certified optimality gap for every channel realization, at a cost linear in $B$.

Core Claim

Take the sum-mean-squared-error (MSE) form of 1-bit precoding studied exactly by Mse-Optimal 1-Bit Precoding for Multiuser Mimo Via Branch and Bound. Written in real coordinates, with $s\in\mathbb{R}^{2U}$ the intended user symbols, $H\in\mathbb{R}^{2U\times 2B}$ the channel, $\beta>0$ a receive gain and $N_0$ the noise power, the problem is

$$ \min_{\beta>0,\; x\in\{\pm1\}^{2B}} \; \|s-\beta Hx\|_2^2 + \beta^2 U N_0 . $$

For fixed $\beta$, replacing $\{\pm1\}^{2B}$ by $[-1,1]^{2B}$ gives a convex problem. Its value $L(\beta)$ lower-bounds the discrete optimum. Let $x^\star$ be a box solution and $y=Hx^\star$. The set $\{x\in[-1,1]^{2B}: Hx=y\}$ is a polytope, and any corner of it has at most $2U$ coordinates strictly inside $(-1,1)$. This is the standard counting argument for basic solutions: $2U$ equality constraints can hold at most $2U$ coordinates away from their bounds.

We claim three things. First, after rounding only those coordinates, the final objective exceeds $L(\beta)$ by at most a quantity controlled by the norms of at most $2U$ columns of $H$. Second, under i.i.d. Rayleigh fading this additive gap has an explicit non-asymptotic constant, and relative to the signal it decays as $B/U$ grows. Third, the gap between any heuristic's objective and $L(\beta)$ is a certificate that can be computed for every channel realization.

The goal is not a multiplicative approximation ratio. Such ratios are ill-posed for minimization problems whose optimum can approach zero. The goal is an additive, dimension-explicit bound whose constants are tight enough to be checked against branch-and-bound.

Relation to Prior Work

The motivating evidence has two sides. Relaxation-based 1-bit precoders are strong empirically. SQUID (Quantized Precoding for Massive MU-MIMO, Nonlinear 1-Bit Precoding for Massive MU-MIMO with Higher-Order Modulation) reformulates 1-bit design as a convex squared-$\ell_\infty$ problem and takes signs. C1PO/C2PO (1-bit Massive MU-MIMO Precoding in VLSI) and GEMM (A Framework for One-Bit and Constant-Envelope Precoding Over Multiuser Massive MISO Channels) add a negative-norm penalty that drives variables to $\pm1$. The ADMM method of Efficient Nonlinear Precoding for Massive MIMO Downlink Systems With 1-Bit DACs converges globally only to stationary points of its non-convex reformulation. None of these methods bounds its distance to the discrete optimum. We reuse them unchanged and attach certificates to their outputs.

The approximation literature constrains the design. Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs proves dimension-independent SDR rounding ratios of $54M^2/\pi$ (real) and $24M/\sqrt{\pi}$ (complex) for beamforming with binary scheduling variables. Its measured ratios stay below 3 and 2. That result shows lifted SDR analysis is both expensive and loose in the number of users. It also leaves discrete antenna outputs untreated. Semidefinite Relaxation and Approximation Analysis of a Beamformed Alamouti Scheme gets $\mathcal{O}(1/(\sqrt{M}\log J))$ SDR bounds, but its relay weights are continuous.

Efficiently and Globally Solving Joint Beamforming and Compression Problem proves SDR is exactly tight for fronthaul quantization. Its quantization is Gaussian compression noise, not a finite alphabet, so its exactness does not carry over to our setting. We do not lift to matrices. We work with the $2B$-dimensional box relaxation and exploit its low-rank structure, since $H$ has only $2U$ rows.

On the constant-factor side, Learning with Square Loss: Localization through Offset Rademacher Complexity supplies the lesson that sharp constants come from analyzing the problem near the optimum rather than uniformly over the whole search space. Beyond singular value gaps in randomized subspace approximation supplies the style of Gaussian-matrix bounds we need for the leftover columns. Both play a methodological role only.

Research Program

The first component is the algorithm, which we call corner-then-round. It solves the box relaxation with a forward-backward splitting method that needs no matrix inversion, so it has the same arithmetic profile as C2PO. It then runs a pivoting walk to a corner. Each step takes $2U+1$ fractional coordinates, finds a direction in the null space of the corresponding $2U\times(2U+1)$ submatrix of $H$, and moves along it until one coordinate hits $\pm1$. There are at most $2B$ steps, each costing $\mathcal{O}(U^3)$.

The remaining $\le 2U$ coordinates are rounded in one of three ways: by plain signs, by greedy sequential choice that minimizes the residual, or by a small exhaustive search when $2U$ is small. The gain $\beta$ is handled by a one-dimensional search over $L(\beta)$.

The second component is analysis at three levels. At the worst-case level, we bound the added error by the leftover columns weighted by their distance to $\pm1$. At the average-case level, we bound it under i.i.d. $\mathcal{CN}(0,1)$ entries, where the maximum column norm concentrates near $\sqrt{U}$ up to a $\sqrt{\log B}$ correction. We will track every constant explicitly rather than discard it, which is the failure mode that the constant-factor literature documents. We expect the discrete loss divided by received signal power to fall roughly as a power of $U/B$, because array gain grows with $B$ while the rounding error does not. Pinning down that exponent and its constant is part of the work. At the certificate level, for any output $\hat{x}$ of any algorithm, we report $\|s-\beta H\hat{x}\|^2+\beta^2UN_0 - L(\beta)$, and in decibels relative to $L$.

The third component extends the method along two axes. The first is to 16-QAM and 64-QAM. Here the discrete loss is exactly what causes the error floor, so the bound predicts which array ratio $B/U$ is needed for a given constellation. The second is to 2–3-bit DACs, where the box becomes a set of intervals and the corner argument still bounds how many coordinates end up between levels. Constant-envelope precoding changes the relaxation into a product of disks, and we leave it as a stated open case.

Baselines

The naive reference point is zero-forcing or Wiener-filter precoding followed by taking signs. In the file's 128-antenna, 16-user setup this reference incurs an 8 dB penalty at a bit-error rate (BER) of $10^{-3}$ (Quantized Precoding for Massive MU-MIMO). It shows how much the problem needs joint optimization.

The exact reference is BB-1 from Mse-Optimal 1-Bit Precoding for Multiuser Mimo Via Branch and Bound. That paper reports a gap of only 4 dB to infinite resolution at BER $10^{-3}$ with 12 antennas. We will run it at $B\le 12$ to measure how loose our bound and certificate actually are.

The strongest fast competitor is GEMM (A Framework for One-Bit and Constant-Envelope Precoding Over Multiuser Massive MISO Channels). It reports a 4.3–5 dB SNR gain over SQUID for 1-bit 16-QAM and 0.85 s runtime at 512 antennas.

SQUID is the convex-relaxation-then-sign baseline, reported to be 3 dB from ideal at BER $10^{-3}$ for 128 antennas and 16 users. C2PO is the hardware-relevant baseline. The ADMM method of Wen et al. is reported to run over 300 times faster than SDR. SDR with Gaussian randomization is run only at small sizes.

All methods see the same channel draws and the same symbol vectors. Each gets the same iteration-count grid for tuning its penalty or step size, chosen on held-out channel draws, and each is timed on the same CPU.

We count as beating GEMM either of two outcomes: corner-then-round matches its 16-QAM symbol-error probability within 0.3 dB at equal or lower runtime, or it beats it at 64-QAM. The core contribution, however, is the certificate, and it does not require beating GEMM on error rate.

The key ablation isolates the corner walk. It compares signs of $x^\star$ against rounding only the $\le 2U$ leftover coordinates after the walk, with the same box solution used in both arms.

Why not just…?

Why not just take the sign of the box-relaxed solution, as SQUID effectively does? This is the real threat. Box solutions to low-rank quadratics are often already mostly saturated, so plain signs may be nearly as good as the corner walk. The ablation settles this directly. If signs are equally good empirically, the practical algorithm is unchanged, but the analysis still has value: the corner argument is what explains why signs work and supplies the bound. We would then reframe the contribution as analysis plus certificates rather than a new precoder.

Why not just run branch-and-bound and report exact gaps? Its cost grows exponentially, which confines exactness to about 12 antennas (Mse-Optimal 1-Bit Precoding for Multiuser Mimo Via Branch and Bound). That is exactly the regime where $B/U$ is too small for our bound to be informative. We use BB-1 for validation, not deployment.

Why not use semidefinite relaxation with randomized rounding, which already has proven constants? The proven ratios grow like $M$ or $M^2$ and are far looser than what is observed (Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs). Interior-point SDR is also reported to run over 300 times slower than ADMM at comparable BER (Efficient Nonlinear Precoding for Massive MIMO Downlink Systems With 1-Bit DACs). Our lower bound $L(\beta)$ may be weaker than the SDR bound on small instances. We will measure the difference where SDR is affordable.

Why not just use 3–4-bit DACs with linear precoding? At those resolutions linear precoding largely closes the gap (Quantized Precoding for Massive MU-MIMO), but DAC power and interconnect cost grow with bits on very large arrays. The multi-bit extension of the corner argument also lets us quantify the number of bits needed for each array ratio, instead of assuming it.

Proposed Experiments

All experiments use i.i.d. Rayleigh channels with 1,000 draws per point.

The first test validates the bound against the exact solver. We run $B\in\{8,10,12\}$ with $U\in\{1,2,3\}$ and compare three quantities: the exact BB-1 optimum, $L(\beta)$, and our predicted additive bound. Success means the certificate is within 1 dB of the true gap on median channels.

The second test checks scaling. We sweep $B\in\{32,64,128,256,512\}$ at $U=16$ and plot the certified gaps of GEMM, C2PO, ADMM, SQUID and corner-then-round against $B/U$. The decisive check is whether the analytical bound predicts the slope of the certified gap. If the bound stays at least an order of magnitude above the certificates at $B=128$, the constants are not yet sharp, and we will report that failure.

The third test measures error rates. We report uncoded BER and symbol-error probability at 16-QAM and 64-QAM, and ask whether the bound predicts the smallest $B/U$ at which the 64-QAM error floor disappears. Reaching that point at 64-QAM is an open problem noted in Nonlinear 1-Bit Precoding for Massive MU-MIMO with Higher-Order Modulation.

The fourth test measures runtime against GEMM's reported 0.85 s at 512 antennas, on our own hardware and rerun for fairness.