When a radar tracks a target whose angle falls between two pre-drawn grid points, compressed-sensing theory has a precise name for what happens next: basis mismatch. The target's energy "leaks" into neighboring grid cells, sparsity breaks down, and — most damaging — the estimation error hits an irreducible floor that no amount of extra transmit power can remove (Sensitivity to Basis Mismatch in Compressed Sensing). Metagenomics has the same problem and no name for it. Microbial evolution is a continuum — strains diverge by point mutation and gene exchange across the whole range of Average Nucleotide Identity (ANI) — yet every profiling pipeline forces sequencing reads onto a fixed catalog of discrete reference genomes or, worse, onto coarse genus-level bins. A strain that sits, say, 1% diverged from its nearest reference is an off-grid target: its reads leak into the reference bin and its neighbors, corrupting abundance estimates in exactly the way signal-processing theory predicts.
This matters because the downstream science — how hosts genetically filter and assemble their microbial communities — appears to stall at exactly the resolution where leakage is worst. The largest host-genetics study of the gut microbiome, the MiBioGen meta-analysis, pooled 18,340 individuals across 24 cohorts and still found only 31 genome-wide significant loci, with just 9 of 410 genera detected in more than 95% of participants (Large-scale association analyses identify host factors influencing human gut microbiome composition). Meanwhile, closely related strains are known to exert opposite biological effects — culprit and protector strains within one taxonomic family in peptic ulcer disease (Yu et al.), tolerance-inducing versus inflammation-inducing strains of the same species (Bhutta et al.) — so coarse binning cancels real signals rather than merely blurring them. The open question is whether this ceiling is biological or mathematical.
Core Claim
I claim that the weak replicability of host–microbiome genetic associations and the failure of strain-level metagenomic profiling share a single mathematical cause: projecting a continuous evolutionary continuum onto a discrete reference grid. I propose to (i) prove this formally by porting the perturbation analysis of Sensitivity to Basis Mismatch in Compressed Sensing to metagenomic read-matching dictionaries, deriving an abundance error floor that scales with genomic divergence and cannot be removed by read depth; (ii) remove the floor with an off-grid alternating estimator that reuses the biconvex scheme of Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search; and (iii) test, on the strain-stressed benchmark of Critical Assessment of Metagenome Interpretation: the second round of challenges and on simulated host-association data, whether off-grid recovery restores strain-resolved host–microbe signals that genus-level aggregation destroys.
The Dictionary and Its Perturbation
Formally, let $y$ be a sample's $k$-mer count spectrum, $x$ the vector of strain abundances, and $A = [a(\theta_1), \dots, a(\theta_N)]$ a dictionary whose columns are the expected $k$-mer spectra of the $N$ reference genomes, so that
$$y = A x + e,$$
with $e$ absorbing sequencing error and technical noise. A strain at per-site divergence $\Delta$ from its nearest reference $\theta_g$ has a true column $a(\theta_g + \Delta)$ that appears in no reference catalog. The signal-processing fix (Combined UAMP and MF Message Passing Algorithm for Multi-Target Wideband DOA Estimation with Dirichlet Process Prior) expands it locally as
$$a(\theta_g + \Delta) \approx a(\theta_g) + a'(\theta_g)\,\Delta,$$
and here genomics is unusually cooperative: under a simple point-mutation model the expected fraction of a genome's $k$-mers that survive divergence $\Delta$ is $(1-\Delta)^k$, so the derivative $a'(\theta_g)$ — the rate at which the read-matching profile drifts with divergence — is available in closed form rather than needing an antenna-calibration analogue. This turns "off-grid strain" into a scalar displacement parameter per strain, exactly the structure the alternating search of Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search exploits: with displacements fixed, recover sparse abundances by $\ell_1$ minimization; with abundances fixed, update each displacement by maximum likelihood on the read pileup; iterate. The method of that paper converges in seconds where a semidefinite program takes minutes, which is the runtime class metagenomics needs. For organisms absent from any catalog — the 600 new plasmids and viruses planted in CAMI II — I add an open-ended component via a Dirichlet process prior, following the factor-graph construction of Combined UAMP and MF Message Passing Algorithm for Multi-Target Wideband DOA Estimation with Dirichlet Process Prior, so the model can admit novel strains rather than misassigning them.
Two prior results constrain the design rather than supplying it. The tensor decompositions of Tensor-Based Channel Estimation for Dual-Polarized Massive MIMO Systems elegantly bypass discrete dictionaries, but they require Vandermonde (shift-invariance) structure that multi-omics contingency tables — host genotype × microbial spectrum × body site — do not possess, so a direct port is not well-defined. The atomic-norm route of MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding eliminates error floors provably, but its semidefinite program costs $O(N^6)$ and its duality rests on Toeplitz covariance from uniform arrays, which $k$-mer dictionaries lack. The alternating scheme is the deliberate compromise: continuous enough to remove the floor, cheap enough to run on CAMI II's $>1{,}000$ GB of data.
Research Program
The program has three parts. First, theory: I will adapt the perturbation model $\Psi_0^{-1}\Psi_1 = I + E$ of Sensitivity to Basis Mismatch in Compressed Sensing to the $k$-mer dictionary, bounding the best $k$-term approximation error and $\ell_1$ recovery error as functions of divergence $\Delta$, $k$-mer length, and read depth. The key predicted result is an abundance error floor that is linear in $\Delta$ and invariant to read depth — the metagenomic twin of the error floors documented in Target parameter estimation for spatial and temporal formulations in MIMO radars using compressive sensing, and a formal explanation of why 18,340 individuals in Large-scale association analyses identify host factors influencing human gut microbiome composition yielded only 31 loci: sample size is the analogue of signal power, and mismatch error floors are immune to it.
Second, algorithm: build the alternating strain-recovery profiler described above, with the closed-form mutation derivative, Dirichlet-process admission of novel components, and a Stein-type data-driven denoising of the count spectrum borrowed in spirit from the BEACHES thresholding of Beamspace Channel Estimation for Massive MIMO mmWave Systems: Algorithm and VLSI Design to strip the technical noise that accounted for roughly 29% of inter-cohort variance in the MiBioGen cohorts.
Third, the biology: use the recovered strain-resolution abundances to ask whether host genetic filtering acts below the species boundary. The canonical real anchor is the LCT–Bifidobacterium association ($P = 1.28 \times 10^{-20}$ in Large-scale association analyses identify host factors influencing human gut microbiome composition); the proposal's testbed, however, is simulated, because no public shotgun cohort in the supplied material couples dense host genotypes to strain-resolved profiles — I state this plainly rather than pretending otherwise. The host-filter spectrum documented across systems — genetics dominating in wild birds (Comparative Gut Microbiota of 59 Neotropical Bird Species) and in controlled sheep and pig cohorts (The Impact of Host Genotype, Intestinal Sites and Probiotics Supplementation on the Gut Microbiota Composition and Diversity in Sheep; Comparative multiomics analyses reveal the breed effect on the colonic host–microbe interactions in pig), environment dominating in brood-parasitic cowbirds (Sampling locality is more detectable than taxonomy or ecology in the gut microbiota of the brood-parasitic Brown-headed Cowbird ( Molothrus ater )) — has only ever been measured at coarse ranks; whether those filters select strains or species is an open, now-measurable question.
Baselines
The naive "do nothing" reference is best-hit read assignment: map every read to its nearest reference genome and report catalog abundances, with no off-grid handling. This is the metagenomic equivalent of fixed-grid sparse recovery, and my theory predicts it exhibits a divergence-linear error floor; it defines the floor the proposal must beat. The strongest existing competitors are the reference-based profilers that dominated CAMI II at higher taxonomic ranks — mOTUs and MetaPhlAn (Critical Assessment of Metagenome Interpretation: the second round of challenges); no reported result found on Lacuna for their strain-level abundance accuracy on the Strain-Madness dataset, so I will run them myself under the identical CAMI II gold standard, evaluation code, and hardware. The CAMI II consortium's qualitative finding — success at higher ranks, failure above the 95% ANI strain barrier — is the bar to clear. A third baseline densifies the reference catalog by roughly $4\times$ with mutated near-duplicates, mirroring the grid-refinement baseline of MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding, where a $4\times$ denser grid cut OMP's spectral-efficiency loss from 63% to 11% but left a persistent floor that continuous recovery (3.4%) eliminated; I expect the same saturation shape here. All methods receive the same reads, the same tuning budget (a fixed number of hyperparameter evaluations each), and are compared on strain-level relative-abundance error and wall-clock time. Finally, the decisive ablation is the full pipeline with the displacement-refinement stage frozen at $\Delta = 0$: identical $\ell_1$ recovery, identical denoising, no off-grid correction. If the frozen version matches the full method on Strain-Madness, the core claim is wrong and I will say so.
Why not just…?
Why not just sequence more reference genomes and densify the catalog? This is the most natural objection, and the signal-processing evidence against it is unusually crisp: in MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding, refining the grid fourfold left an 11% irreducible loss, because near-duplicate dictionary columns become mutually coherent and break sparse-optimization identifiability. The metagenomic version is the strain barrier itself: CAMI II shows profiling fails above 95% ANI regardless of catalog size, with chimeric assemblies and fragmented bins (Critical Assessment of Metagenome Interpretation: the second round of challenges). Densification also cannot help for organisms never sequenced — the 600 new plasmids and viruses in CAMI II were invisible to every reference-based tool. I will run the densified catalog as a baseline precisely because if it does close the gap, the simpler method should win.
Why not just aggregate at genus level and avoid strain resolution entirely? Honest answer: for many assembly questions this is fine — the bird and cowbird studies show host-filtering conclusions are robust at coarse ranks. But for host genetic association it is the wrong resolution by construction: within-taxon functional opposition is documented (culprit versus protector strains in Yu et al.; opposing immune responses in Bhutta et al.; strain-dependent safety profiles in Hu et al.), so genus aggregation averages real opposing effects toward zero. The simulated-association experiment settles this directly: I will plant a host allele whose effect acts through two same-species strains with opposite signs, and measure detection power under genus aggregation versus off-grid recovery. If aggregation detects it anyway, the strain-resolution program loses its main biological justification.
Why not just formulate the whole problem as atomic-norm semidefinite programming? Three reasons, all from the file: the $O(N^6)$ complexity reported in MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding; the latency gap quantified in Beamspace Channel Estimation for Massive MIMO mmWave Systems: Algorithm and VLSI Design — about 83,000 ms for ANM versus 2,200 ms for iterative off-grid estimation and 1.5 ms for thresholding at 256 antennas — which is fatal at CAMI II's terabyte scale; and, most fundamentally, the SDP reformulation of the atomic norm exploits Toeplitz/Hankel structure that $k$-mer dictionaries do not have, so a faithful port does not currently exist. I concede the counterfactual: if a suitable positive-semidefinite embedding of the genomic kernel were found, ANM could dominate at extreme divergence, and I will compare against it on small synthetic cases where SDP is tractable.
Why not just denoise harder (BEACHES-style) instead of going off-grid? Adaptive thresholding with Stein's Unbiased Risk Estimator (Beamspace Channel Estimation for Massive MIMO mmWave Systems: Algorithm and VLSI Design) addresses the 29% technical-variance problem in Large-scale association analyses identify host factors influencing human gut microbiome composition, and I adopt it as a module — but denoising suppresses noise, not bias, and off-grid leakage is a deterministic bias of the dictionary. The error-floor experiment below separates them: denoising should flatten the floor's noise term in both pipelines; only off-grid correction moves the floor itself.
Proposed Experiments
Experiment one, the floor: evolve synthetic strains from CAMI II references at controlled ANI (95% to 99.9%), generate reads at increasing depth, and plot strain-abundance error against depth for best-hit assignment, the $4\times$ densified catalog, and the off-grid method. The decisive signature, predicted by the perturbation theory and mirroring the 63%/11%/3.4% saturation pattern of MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding, is that fixed-grid errors stop improving with depth while the off-grid error keeps shrinking. Experiment two, the benchmark: full evaluation on the CAMI II Strain-Madness dataset (100 samples, roughly 1,700 genomes and plasmids plus 600 novel plasmids and viruses, strains placed above the 95% ANI barrier; Critical Assessment of Metagenome Interpretation: the second round of challenges), reporting strain-level abundance error against the baselines above, plus runtime — with the design target set by the seconds-versus-minutes contrast of Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search. Experiment three, the biology: the planted host-association simulation described above, extended to a MiBioGen-style 24-cohort layout with 29% injected technical variance, measuring cross-cohort replicability of strain-resolved versus genus-binned associations, with the real $LCT$ locus as the calibration anchor. If experiments one and two succeed but three shows no replicability gain, the honest conclusion is that the strain barrier is a measurement problem solved, while the mbQTL ceiling is genuinely biological — itself a publishable answer, and one this proposal is designed to distinguish rather than assume.
References
- Sensitivity to Basis Mismatch in Compressed Sensing
- Large-scale association analyses identify host factors influencing human gut microbiome composition
- Association between gut microbiota and peptic ulcer disease, particularly gastric ulcer and duodenal ulcer: a two-sample Mendelian randomization study
- Gut microbiota mediated T cells regulation and autoimmune diseases
- Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search
- Critical Assessment of Metagenome Interpretation: the second round of challenges
- Combined UAMP and MF Message Passing Algorithm for Multi-Target Wideband DOA Estimation with Dirichlet Process Prior
- Tensor-Based Channel Estimation for Dual-Polarized Massive MIMO Systems
- MmWave channel estimation via atomic norm minimization for multi-user hybrid precoding
- Target parameter estimation for spatial and temporal formulations in MIMO radars using compressive sensing
- Beamspace Channel Estimation for Massive MIMO mmWave Systems: Algorithm and VLSI Design
- Comparative Gut Microbiota of 59 Neotropical Bird Species
- The Impact of Host Genotype, Intestinal Sites and Probiotics Supplementation on the Gut Microbiota Composition and Diversity in Sheep
- Comparative multiomics analyses reveal the breed effect on the colonic host–microbe interactions in pig
- Sampling locality is more detectable than taxonomy or ecology in the gut microbiota of the brood-parasitic Brown-headed Cowbird ( Molothrus ater )
- Lactic acid bacteria with a strong antioxidant function isolated from “Jiangshui,” pickles, and feces