Coherence

Mutual coherence with the pixel basis, mu(U) = N max_ij |U_ij|^2 in [1, N], together with a certificate that tells you before training whether training can raise it above 1.

Mutual coherence of a learned basis with the pixel basis.

For compression, the only thing that matters about a basis is how few coefficients it needs. For any task that recovers an image from a subset of its pixels — inpainting, completion, compressed sensing — a second quantity governs the outcome, and it is not sparsity:

mu(U) = N * max_ij |U_ij|^2   in [1, N]

with N the operator dimension. mu = 1 is maximal incoherence with the pixel basis, the most favourable case for recovery from pointwise samples; mu = N is the worst, an atom supported on a single pixel, invisible to any sample set that misses it. Sample-complexity bounds for recovery from random pixel observations scale linearly in mu (Candes & Plan 2011, Krahmer & Ward 2014).

A trained basis can drift in mu while its compression loss improves, so the quantity is worth being able to measure. This module measures it — and, more usefully, certifies when it cannot drift at all.

The guarantee

Let the circuit act on n wires, and suppose every gate is diagonal in the computational basis except for exactly one Hadamard per wire. Then:

|U_ij| = N^{-1/2}   for every i, j and every parameter value,

so mu(U) = 1 identically over the whole parameter space, and sqrt(N) U is a complex Hadamard matrix (Tadej & Zyczkowski 2006).

Proof. Track the amplitude vector produced by an input basis vector. Diagonal gates multiply amplitudes by unit moduli and never move amplitude between the two values of any wire; a permutation permutes. Consider the moment the Hadamard on wire q is applied. Every earlier gate is diagonal or a Hadamard on a different wire, so none has moved amplitude across wire q, and the vector is supported on one value of it: one branch carries a, the other 0. Since H (a, 0)^T = (a, a)^T / sqrt(2), the gate replaces each modulus by two equal moduli |a|/sqrt(2) and never combines unequal ones. Each wire receives exactly one Hadamard, so every amplitude ends at 2^{-n/2}, and the remaining diagonal gates and permutations preserve moduli. QED

The practical consequence is a classification of this package’s bases by which gates are left free during training:

• free only the controlled-phase gates — the compact-CP tensors — and mu is pinned at 1 no matter how hard the basis is trained, on any objective, with no penalty, constraint or monitoring;

• free the Hadamard / U(4) gates as well and the guarantee is void. It is void in practice, not only in principle: randomising them on an (m, n) = (3, 3) QFTBasis reaches mu = 24.8 of a possible 64, and on RichBasis — which has no diagonal gates at all — mu = 32.5.

certify_flat_modulus performs that check for a given training configuration, taking the same frozen_indices that train_basis_batched accepts, so the question “does this training run preserve incoherence?” can be answered before the run rather than measured after it.

Discovered while applying this package’s basis family to image completion, where the reversal matters: the transform that compresses an image best is not the one that completes it best.

Contents

coherence	mu(U) = N max_ij |U_ij|^2, in [1, N].
certify_flat_modulus	Certify that training cannot raise mu above 1.
FlatModulusCertificate	Whether mu == 1 holds over the whole reachable parameter set.
is_flat_modulus	True if |U_ij| = N^{-1/2} everywhere, i.e. sqrt(N) U is complex Hadamard.
diagonal_tensor_indices	Indices of the tensors that are diagonal in the computational basis.
dense_operator	The basis as an explicit matrix acting on vec(image).