How few bits per symbol does it take to store a binary sequence with memory, such as a Markov chain, if we tolerate a fixed fraction of flipped bits? For memoryless sources the answer is a one-line formula. For sources with memory it is a limit over ever-longer blocks. Each block length $n$ requires optimizing a coupling between $2^n$ source strings and $2^n$ reconstructions, so exact solvers stop at about a dozen symbols. Even the binary symmetric Markov chain under bit-flip (Hamming) distortion has a closed form only at small distortion levels. The block limit is where this regime gets its name, a "multi-letter" characterization: a limit over blocks rather than a formula for one symbol.
This note proposes to make long blocks tractable without enumerating them. Recent work showed that the rate–distortion function is an entropy-regularized optimal transport problem in which the reconstruction distribution is free. For block length $n$ with per-symbol distortion, the transport cost factorizes across positions. We therefore represent the free reconstruction distribution as the square of a tensor train, a chain of small matrices whose product gives the probability of each string. This parameterization is a sequential analogue of the low-rank factorization $X = UU^T$ studied under the restricted isometry property. It yields statistically certified upper bounds on the block rate at block lengths of 64 or more. It lets us test whether the "no bad local minima" geometry known from low-rank matrix sensing carries over to this entropic objective. A residual-balanced penalty update lets each solve target an exact distortion level.
Core Claim
For a stationary source $X_1, X_2, \dots$ and per-letter distortion $d$, define the block rate
$$R_n(D) = \frac{1}{n}\min_{P_{Y^n|X^n}:\ \mathbb{E}\,\frac1n\sum_i d(X_i,Y_i)\le D} I(X^n;Y^n).$$
$R(D)=\lim_n R_n(D)=\inf_n R_n(D)$ by subadditivity, so every finite-$n$ solution is an upper bound on the true rate.
Fix a reconstruction distribution $q$ on strings $y^n$ and a slope $\lambda>0$. The test channel is $P(y^n|x^n)\propto q(y^n)e^{-\lambda \sum_i d(x_i,y_i)}$. Let $D_q$ be its expected distortion. Its mutual information then satisfies
$$I(X^n;Y^n)\ \le\ -\lambda n D_q-\mathbb{E}_{X^n}\log\,(K_\lambda q)(X^n),$$
where $K_\lambda=\bigotimes_{i=1}^n [e^{-\lambda d(x,y)}]$ is a Kronecker product of small per-letter kernels. Minimizing the right-hand side over $q$ recovers the Blahut–Arimoto/Sinkhorn fixed point. This is the extremal entropic transport formulation of On a Relation Between the Rate-Distortion Function and Optimal Transport. We do not need to store $q$ or the plan.
Our claim is that a squared tensor train, $q(y^n)=\psi(y^n)^2/Z$ with $\psi$ of bond dimension $r$, has three useful properties. It makes $(K_\lambda q)(x^n)$, the normalizer $Z$, and exact sampling from the test channel all cost polynomial time in $n$ and $r$. Monte Carlo over source strings, which are easy to sample from a Markov or hidden-Markov model, then gives unbiased estimates of both sides of the bound with confidence intervals. Finally, it reaches rates up to $n\log|\mathcal{Y}|$ bits. That avoids the $\log(\text{particles})$ ceiling that limits particle methods (Estimating the Rate-Distortion Function by Wasserstein Gradient Descent).
Bond dimension $r=1$ is the product (memoryless-style) reconstruction. Growing $r$ interpolates toward the exact block optimum. The new deliverables are three. First, certified upper bounds on $R_n(D)$ at block lengths well beyond dense enumeration, for binary Markov and hidden-Markov sources. Second, an empirical map of how large $r$ must be. Third, a test of whether the factorized landscape is benign.
Research Program
Solver. We minimize the bound over the tensor-train cores by stochastic gradient. Gradients of $\mathbb{E}\log(K_\lambda q)$ are computed by contracting $\psi$ against the per-letter kernel and against itself. Each contraction costs $O(n r^3|\mathcal{Y}|^2)$ per source sample. Squaring $\psi$ enforces nonnegativity in the same way $UU^T$ enforces positive semidefiniteness. We will also try nonnegative cores as an alternative.
Hitting an exact distortion. Comparing $R_n(D)$ across $n$ requires the same $D$ at every $n$. The method behind A Communication Optimal Transport Approach to the Computation of Rate Distortion Functions does this with a Newton root-find on $\lambda$. It reports that this avoids the failures of Blahut–Arimoto at non-smooth "bifurcation" points. Newton steps assume an accurate inner solve, which stochastic, non-convex training does not provide. We instead update $\lambda$ as a dual variable, with a step size adjusted by comparing the distortion violation to the change in the primal iterate. This follows the residual-balancing rule of Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. We borrow from Faster and Non-ergodic O(1/K) Stochastic Alternating Direction Method of Multipliers the practice of increasing the penalty slowly, so the optimizer is not forced to a boundary early. Both papers prove convergence only for convex problems. Here the rule is a heuristic, and we ablate it rather than claim guarantees.
Landscape analysis. Global Optimality of Local Search for Low Rank Matrix Recovery and Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate prove that factorized least squares has no spurious local minima under the restricted isometry property. That property means the measurement operator nearly preserves lengths of low-rank matrices, with constant below 1/5 or 1/3. Their arguments rest on the loss curving nearly uniformly along low-rank directions.
Our objective $-\mathbb{E}\log(K_\lambda q)$ is convex in $q$ but not quadratic, so their theorems do not apply. Their mechanism, however, suggests a measurable quantity. We will estimate the ratio of largest to smallest curvature of this objective restricted to the tangent space of bond-dimension-$r$ tensor trains, which we call the restricted condition ratio. We will then test whether this ratio predicts how often random restarts end at different objective values. A clean relationship would be a first step toward a landscape theorem for entropic block objectives. A failure would show that RIP-style reasoning does not transfer, and would argue for warm starts, for example growing $r$ or $n$ progressively.
Scope. The main target is rate–distortion. The same Kronecker-structured bound applies to block mutual information of finite-state channels without feedback. We treat that only as a later extension. The Intractability of Multi-Letter Channel Capacities shows that the feedback case is uncomputable in general, and we make no claim there.
Baselines
The naive reference point treats the source as memoryless. It reports the single-letter rate–distortion function of the marginal, which for a symmetric binary source is $1-h(D)$. This equals our method at block length 1, or equivalently at bond dimension 1 with identical cores. Any useful method must beat it.
The strongest existing competitor is dense alternating Sinkhorn on the full block alphabet. This is the method of A Communication Optimal Transport Approach to the Computation of Rate Distortion Functions, which reports relative error "frequently as low as $10^{-15}$" against analytic solutions and runs 11 to 18 times faster than Blahut–Arimoto on memoryless binary, Gaussian, and Laplacian sources. For sources with memory we found no reported result on Lacuna. We will run dense alternating Sinkhorn and dense Blahut–Arimoto at every $n$ that fits on the same GPU, which we expect to be about 12 to 13 for binary alphabets. Both will target the same distortion grid and get the same wall-clock budget. We also give the dense baseline its best large-$n$ estimate by extrapolating $R_n(D)$ in $n$ with fits of the form $a+b/n+c\log n/n$.
Beating this baseline means two things at large $n$. In the regime where a closed form exists, our certified upper bounds must lie closer to the truth than the extrapolated dense estimate. Elsewhere, our certified upper bounds must lie below the best dense finite-$n$ bound, which is a valid upper bound, whereas the extrapolation is not.
Two ablations isolate the key ingredients. The first sweeps bond dimension $r$ at fixed $n$ and tests whether low-rank reconstructions are the source of any gain. The second replaces adaptive $\lambda$ with a fixed-$\lambda$ sweep plus interpolation of the curve, and also with a Newton root-find on noisy estimates, at equal gradient steps. For continuous sources, Wasserstein gradient descent particles in block space (Estimating the Rate-Distortion Function by Wasserstein Gradient Descent) are a further baseline. They expose the particle-count rate ceiling.
Why not just…?
Why not just run dense Blahut–Arimoto or alternating Sinkhorn up to $n\approx 12$ and extrapolate? This is the real threat. If $R_n(D)$ converges at a clean $O(1/n)$ rate, extrapolation from small blocks could be as accurate as anything we compute. The experiment settles this directly. On the binary symmetric Markov source below the critical distortion, the truth is the Shannon lower bound $h(p)-h(D)$. We compare extrapolation error against the error of our certified bounds at $n=32$ and $n=64$.
If extrapolation matches us, the contribution narrows to certification, since extrapolated numbers are not bounds. It also narrows to sources where convergence in $n$ is irregular, such as hidden-Markov sources with long correlation. We will report that narrowing honestly rather than rely on the small-distortion regime alone.
Why not just use a neural estimator or particles over blocks? Neural rate–distortion estimators report hyperparameter instability and are 10 to 100 times slower than particle flows. Particle flows are capped at $\log_2(\text{particles})$ bits (Estimating the Rate-Distortion Function by Wasserstein Gradient Descent). At $n=64$ and low distortion, the block rate is tens of bits, which would need astronomically many particles. A neural reconstruction model with tractable likelihood could replace the tensor train. We view it as a sibling of our parameterization rather than an alternative. The tensor train is chosen because $(K_\lambda q)$ and $Z$ are computed exactly rather than estimated.
Why not just sweep $\lambda$ instead of adapting it? For the curve alone, a sweep with interpolation might be enough, and the ablation may show that the dynamic weighting is only a convenience. We expect it to matter in two places. One is at the kinks of the curve, where the CommOT paper reports that fixed-slope methods misbehave. The other is under noisy gradients, where Newton steps on $\lambda$ overshoot. We will report the number of distortion targets missed by more than $10^{-3}$ under each scheme. If the sweep ties, we will keep it and drop the claim.
Proposed Experiments
Sources. The sanity check is the memoryless binary Hamming source from the CommOT benchmarks. There $R_n(D)=1-h(D)$ for every $n$, so any drift with $n$ or $r$ exposes estimator bias. The main testbed is the binary symmetric Markov source with flip probabilities $p\in\{0.05, 0.1, 0.2\}$. It has a known answer at small distortion and open territory above the critical distortion, where we report the gap between our upper bound and the Shannon lower bound. The stress test is a binary hidden-Markov source with a slowly mixing hidden state. We will add a Gauss–Markov source under squared error, discretized per letter, against the reverse water-filling answer as an optional continuous check.
Decisive checks. The first is agreement. At $n\le 12$, the tensor-train solver at moderate $r$ must match dense alternating Sinkhorn to within $10^{-4}$ bits per symbol. If it does not, the low-rank assumption is wrong for these sources.
The second is gain at length. At $n\in\{24,32,64\}$, our 95%-confidence upper bounds must fall strictly below the best dense finite-$n$ bound. In the closed-form regime they must also approach the truth faster than extrapolation does.
The third is rank requirements. We plot the bond dimension needed for $10^{-3}$-bit accuracy against the source's correlation length. If it grows exponentially with $n$, the method fails.
The fourth is landscape. Across 50 random restarts per configuration, we report the spread of final objectives against the estimated restricted condition ratio.
A positive result consists of certified block-length-64 bounds above the critical distortion of the binary Markov source, together with evidence that local search over small bond dimension finds them reliably. That would be a new computational handle on a classical open curve.
References
- On a Relation Between the Rate-Distortion Function and Optimal Transport
- Estimating the Rate-Distortion Function by Wasserstein Gradient Descent
- A Communication Optimal Transport Approach to the Computation of Rate Distortion Functions
- Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
- Faster and Non-ergodic O(1/K) Stochastic Alternating Direction Method of Multipliers
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate
- Capacity of Finite State Channels with Feedback: Algorithmic and Optimization Theoretic Properties