Many signal-recovery problems ask for an integer vector $x$ from a few noisy linear measurements $y = \Phi x + e$, where the columns of $\Phi$ form a tight frame. A tight frame is an overcomplete set of $n$ vectors in $\mathbb{R}^k$ that preserves energy the way an orthonormal basis does. A cheap and often effective way to solve such problems is iterative decimation: estimate how confident you are about each unknown, permanently fix the most confident one, simplify, and repeat. Its known weakness is that one wrong early fix can make the rest of the problem unsolvable.
We propose that a single algebraic fact predicts when those wrong fixes happen and whether they can be repaired. The integer combinations of a tight frame form a discrete lattice exactly when the frame's inner products are rational multiples of one common constant. Otherwise they form a dense cloud with no minimum spacing. We argue that rational frames make decimation errors degenerate: harmless or exactly repairable, as in quantum error-correcting codes. Irrational frames make them near-degenerate: silent and fatal. We would then build a decimation algorithm that uses this structure explicitly.
Core Claim
Two papers establish the starting fact. Lattices from equiangular tight frames shows that the integer span $\mathbb{Z}\Phi$ of an equiangular frame is discrete if and only if the shared angle cosine is rational. Discrete cases include the $(5,10)$, $(13,26)$ and $(7,28)$ frames. The $(3,6)$, $(7,14)$ and $(9,18)$ frames give dense sets. Lattices From Tight Frames and Vertex Transitive Graphs generalizes this to Gram-matrix rationality and constructs frames from graph eigenspaces. Both papers treat discreteness as a yes-or-no geometric property. Neither asks what it does to an algorithm.
The quantity that connects lattice geometry to decimation is the smallest nonzero image of an integer difference vector inside the box of allowed values. Suppose each coordinate of $x$ lies in a range of width $B$. Define
$$ \delta_B(\Phi) = \min\{\|\Phi c\| : c \in \mathbb{Z}^n,\ |c_i| \le B,\ \Phi c \neq 0\} $$
and the box kernel $K_B = \{c \in \mathbb{Z}^n \setminus \{0\} : |c_i| \le B,\ \Phi c = 0\}$.
Two difference vectors can confuse a recovery algorithm. Vectors in $K_B$ make two candidate solutions produce identical measurements. Vectors with small $\|\Phi c\|$ make them produce nearly identical measurements.
For a rational frame, $\delta_B \ge \lambda_1(\Lambda)$ for every $B$, where $\lambda_1(\Lambda)$ is the lattice's minimum distance, because every nonzero $\Phi c$ is a lattice point. Confusion therefore has a gap: either exact (a kernel vector) or at least $\lambda_1$ away. For an irrational frame, density forces $\delta_B \to 0$ as $B$ grows. Confusion then becomes a continuum of near-collisions, none of which is visible as a measurement mismatch.
Our hypothesis is that decimation errors follow this split. In the rational regime a wrong fix moves the search along an exact kernel vector. That move is either benign, because an equivalent solution still exists, or exactly repairable by adding a precomputed kernel vector. This mirrors how code degeneracy helps guided decimation in Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation. In the irrational regime a wrong fix moves along a near-kernel vector. The residual stays within the noise level, so no check catches the error, and the cascade resembles the infeasibility failures that force the explicit repair step in GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming.
The stronger and more falsifiable form of the claim is that decimation's noise threshold scales with $\delta_B$, not with rationality as a binary label. This form also covers a rational frame with huge denominators, which has a tiny $\lambda_1$ and should behave like an irrational one.
Research Program
The algorithm, which we call kernel-aware decimation, has three parts.
The first part is offline. We compute a short generating set for $K_B$ and a list $D_\tau$ of near-kernel difference vectors with $\|\Phi c\| \le \tau$. For rational frames we scale the Gram matrix to integers, so $K_B$ comes from exact integer linear algebra plus basis reduction. For irrational frames we apply basis reduction to the standard embedding that stacks the identity matrix on top of a large multiple of $\Phi$. Short vectors of that stacked lattice are exactly the near-kernel vectors we want.
The second part is the decimation loop itself. It follows the guided-decimation pattern of BPGD. Belief propagation runs with discrete box priors on the dense bipartite graph linking measurements to frame coefficients, and the coordinate with the largest log-likelihood ratio is frozen. As a cheaper variant, we also test confidence taken from re-solved box-constrained least squares, in the probing style of One-Shot Learning for MIPs with SOS1 Constraints.
The third part changes what is decimated and how failures are handled. When a group of coordinates shares support with a short vector in $D_\tau$, the group is fixed jointly. We enumerate the few values consistent with that vector instead of committing one coordinate at a time. After every freeze, if the residual exceeds the noise level, the algorithm tries local moves along stored kernel and near-kernel vectors before declaring failure.
The analysis has two goals. The first is a threshold result for rational frames: with a gap $\lambda_1$, decimation that is correct up to kernel moves should succeed whenever the noise stays below roughly $\lambda_1/2$. The second is a counting argument for irrational frames: the number of near-collisions grows with $B$ and drives the failure rate up.
The frames come from the file's sources. They include simplices, the rational and irrational $(k,2k)$ equiangular frames, and the $(7,28)$ Gerzon frame. They also include graph-eigenspace frames from the Petersen, Schläfli, Gosset and Shrikhande graphs, as constructed in Lattices From Tight Frames and Vertex Transitive Graphs.
For scale and controlled comparison we use larger vertex-transitive graphs. Projecting onto the eigenspace of an integer eigenvalue of an integer adjacency matrix gives a rational frame, and an irrational eigenvalue generally gives an irrational one. One graph family can therefore supply matched rational and irrational frames of similar size. We target $k \approx 64$, $n \approx 256$, the scale at which Sparse recovery with integrality constraints reports BKZ-plus-MIP solving binary instances in seconds, and then go beyond it to where exact methods should strain.
Baselines
The naive reference point is box-constrained least squares, or $\ell_1$ minimization when $x$ is sparse, followed by rounding to the nearest integer. An algebraic perspective on integer sparse recovery argues that continuous methods of this kind are suboptimal for integer signals because they ignore lattice structure. We run it on the same instances with no tuning beyond the regularization weight. Any method that does not clearly beat it is not worth discussing.
The greedy reference is Projected Orthogonal Matching Pursuit (PrOMP), which rounds residual estimates one coordinate at a time. Lattices From Tight Frames and Vertex Transitive Graphs evaluated it on graph-generated frames and found low-coherence frames help. That paper gives no numerical recovery rates, and no reported result was found on Lacuna for PrOMP accuracy on these frames. We run it on identical frames and noise levels.
The strongest exact competitor is the rangespace formulation with BKZ basis reduction solved by Gurobi, as in Sparse recovery with integrality constraints. That paper reports solving $64 \times 256$ binary instances to optimality in "seconds" versus hours without BKZ, but gives no exact timings. It also covers only noiseless systems; no reported result was found on Lacuna for its noisy-regime accuracy. We give it the same per-instance wall-clock budget as our method. At sizes where it finishes, it serves as the ground-truth maximum-likelihood reference.
Beating this baseline means one of two things. The first is matching its exact-recovery rate within statistical error at a smaller wall-clock cost. The second is achieving a higher recovery rate under a fixed time budget at sizes where it times out.
The key ablation is plain guided decimation: identical belief propagation and identical freezing order, but no joint group fixing and no kernel moves. BPGD reports matching BP-OSD-0 on quantum codes, again without numbers in the file. This ablation isolates whether kernel awareness, rather than decimation itself, produces any gain.
Why not just…?
Why not just run BKZ plus a MIP solver and skip decimation? This is the real threat at medium scale, and we expect it to win or tie there. The proposal does not claim otherwise. The experiments sweep $n$ under matched time budgets to locate the crossover. If no crossover appears before memory limits, the algorithmic contribution fails. The diagnostic contribution would survive: explaining which frames are hard for any decimation-style method.
Why not just use only rational frames, since irrational ones are bad? Sometimes the frame is given by the physics of the measurement, not chosen. More importantly, rounding an irrational frame to a nearby rational one produces large denominators and a tiny $\lambda_1$. Our claim predicts such a frame fails like the irrational original. The denominator sweep in the experiments tests exactly this. If rationalized frames with large denominators decode as well as small-denominator ones, our $\delta_B$ account is wrong.
Why not just add a generic repair step, as large-scale integer programming heuristics do? The repair in GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming unfixes variables only after a constraint is violated. In the irrational regime the near-kernel error never violates anything: the residual stays within the noise level, so a generic repair is never triggered. We include a generic unfix-on-residual variant. Our prediction is that it matches kernel-aware decimation on rational frames and falls behind it on irrational ones. If it matches on both, the kernel machinery is unnecessary and we would report that.
Proposed Experiments
The first check tests the mechanism directly. For every failed run of plain decimation, we take the difference between the decoded vector and the true $x$. We test whether that difference lies in $K_B$, in $D_\tau$, or neither. The claim predicts kernel-dominated failures for rational frames and near-kernel-dominated failures for irrational frames. A mixed picture on both would refute it.
The second check is a threshold plot. For each frame we measure exact-recovery rate against noise level and box width $B$. We then test whether the noise level at 50% failure collapses onto a single curve when divided by $\delta_B$ across all frames, rational and irrational. As a separate test, we follow the denominator sweep: rational approximations of the $(3,6)$ and $(7,14)$ frames with increasing denominators should slide continuously from lattice-like to dense-like behavior.
The third check is the head-to-head scaling study. It runs on the matched rational and irrational graph-eigenspace families against all baselines under equal time budgets. We report exact-recovery rate, wall-clock time, and the number of kernel repairs used.
The proposal succeeds if three things hold. The failure decomposition separates cleanly by rationality. The $\delta_B$ collapse holds. Kernel-aware decimation beats plain decimation on irrational frames and overtakes BKZ-plus-MIP at some size within the tested range.
References
- Lattices from equiangular tight frames
- Lattices From Tight Frames and Vertex Transitive Graphs
- Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation
- GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming
- One-Shot Learning for MIPs with SOS1 Constraints
- Sparse recovery with integrality constraints
- An algebraic perspective on integer sparse recovery