Heritability is the share of variation in a trait, such as height or disease risk, that is explained by additive genetic differences. Genome-wide studies systematically come up short of family-based estimates, a gap known as "missing heritability." One promising family of methods recovers some of that gap by treating the genome as a sparse regression problem: a few thousand variants matter and the rest are zero. The best example, HERRA, uses the Lasso, a regression that pushes most coefficients to exactly zero. HERRA reports colorectal cancer heritability of 0.110, against 0.068 from standard mixed models. Nobody can say whether such a number is trustworthy for a given genotype matrix. Sparse regression is only guaranteed to work when the design matrix satisfies conditions like the restricted isometry property (RIP), meaning every small set of columns behaves almost like an orthogonal set. Neighboring genetic variants are often nearly identical copies of each other, a phenomenon called linkage disequilibrium (LD), so these conditions plainly fail at the level of individual variants.
The idea of this note is that heritability does not need the conditions that fail. Heritability depends on how much phenotypic variance the fitted genetic signal explains. It does not depend on which of two nearly identical variants receives the credit. If variants are grouped into LD clusters, and the regression penalizes the size of each cluster's fitted contribution rather than its individual coefficients, then near-collinearity inside a cluster stops mattering. What remains is interference between clusters. That interference can be bounded with cheap, computable coherence quantities from the sparse-recovery literature, and because LD is mostly local, the computation scales to whole chromosomes. We propose to build this cluster-level certificate, to derive how it bounds the error of a residual-variance heritability estimate, and to test whether it tells practitioners, region by region, when a sparse estimate should be believed over a mixed-model one.
Core Claim
A cluster-level cumulative coherence certificate can be computed in near-linear time on real genotype data. It is non-vacuous on a substantial fraction of the genome at sparsity levels relevant to complex traits. Its value tracks the actual heritability estimation error of sparse estimators in semi-synthetic simulations, well enough to decide when to prefer a sparse estimator over a mixed model. The naive version of this idea fails: certifying the raw variant-level genotype matrix gives vacuous answers, because adjacent variants with $r^2 > 0.95$ already push the pairwise and cumulative coherence above the thresholds needed for any sparsity of two or more. Moving the certificate to the level at which the estimand is defined is the substantive step.
Background and Positioning
Exact RIP verification is NP-hard (Ben-Haim et al.; Pope et al.). It is also hard on average for random matrices (Kunisky et al.; Ding et al.). These results constrain the design: we aim only at sufficient, computable conditions and accept that they will be conservative.
The method comes from three lines of tractable certificates. Li and Chen show that cumulative coherence implies the restricted eigenvalue condition, the condition needed for Lasso consistency. Cumulative coherence is the largest total correlation between any one column and its $s$ most-correlated others. Their Lasso condition is $\mu_1(s-1)+\mu_1(4s-1)<1/\sqrt{3}$. They test only stylized matrices and do not treat variance estimation. Iouditski et al. certify block-sparse recovery through a convex "contrast matrix" program that generalizes block incoherence. It is tractable only at small scale and is evaluated without genetic data. Barg et al. use average rather than worst-case coherence to explain why structured matrices beat worst-case bounds. We reuse the first as the main certificate, the second as a tighter per-region check, and the third as a robustness variant.
On the genetics side, HERRA (Gorfine et al.) motivates the work. It shows that sparse estimation beats infinitesimal mixed models when causal variants are untyped, but it offers no guarantee about the design matrix. It also handles LD only by averaging over sample splits. Moment-matching heritability (Ge et al.) supplies the fast mixed-model reference point. i-LDSC uses a fixed ±50-variant window for local interactions. That window choice is a heuristic of the kind a coherence profile could inform, but we leave interactions to future work and keep this proposal additive.
Research Program
The first component is the grouped design. We partition each chromosome into LD clusters by greedy agglomeration until the within-cluster correlation exceeds a threshold. For each cluster we orthonormalize its columns, so that the cluster is represented by the subspace it spans. Between-cluster interference is then measured by the largest canonical correlation between two cluster subspaces, which is the largest singular value of their cross-Gram matrix. Block cumulative coherence $\mu^{B}_1(s)$ is the largest sum of the top $s$ such canonical correlations seen from any single cluster. Because LD decays with physical distance, the cross-Gram is effectively banded. This makes the computation roughly linear in the number of variants times the band width. Known long-range LD regions, such as the major histocompatibility complex, are flagged and certified separately.
The second component is the estimator. We fit a group Lasso whose penalty is $\sum_g \|X_g \beta_g\|_2$, where $X_g$ is the genotype submatrix for cluster $g$ and $\beta_g$ its coefficients. This penalty is invariant to how weight is spread within a cluster. We then estimate residual variance from the full sample with a degrees-of-freedom correction, avoiding HERRA's halving of the sample. As an alternative full-sample route we run the early-stopped multiplicative reparameterization of Vaskevicius et al.. That method reaches the oracle rate without the downward pull on coefficient sizes that the Lasso penalty introduces, but it assumes an unverified restricted eigenvalue condition; our certificate is exactly what would justify it.
The third component is error propagation, which addresses the gap Li and Chen leave open for variance estimation. With heritability estimated as $\hat h^2 = 1-\hat\sigma_e^2/\hat\sigma_y^2$, where $\hat\sigma_y^2$ is the phenotypic variance, the error in $\hat\sigma_e^2$ is controlled by the in-sample prediction error. Under a restricted eigenvalue constant $\kappa$ at cluster sparsity $s$, that prediction error scales as
$$\frac{1}{n}\|X(\hat\beta-\beta)\|_2^2 \lesssim \frac{s\,\sigma_e^2\,(\log G + \bar p)}{n\,\kappa^2},$$
where $n$ is sample size, $G$ the number of clusters, and $\bar p$ the typical cluster rank. This form is the standard group-sparse rate. We will prove a lower bound on $\kappa$ in terms of $\mu^B_1$, by adapting Li and Chen's argument from columns to subspaces. The result is a computable bound on $|\hat h^2-h^2|$ as a function of $n$, $s$, and the certificate alone, uniform over all $s$-cluster-sparse architectures.
Baselines
The naive reference point is moment-matching heritability on the genetic similarity matrix as in Ge et al., together with GCTA-style REML. These estimators need no sparsity, so they define what the certificate must beat when it says "trust the sparse method." All estimators run on identical genotype matrices and simulated phenotypes, with default settings and no per-scenario tuning.
The strongest existing sparse competitor is HERRA, run as published, with ridge screening, split, Lasso selection, OLS refit, and swap-and-average. On GECCO it reports $h^2 = 0.110$ (SE 0.005) against GCTA's 0.068 (SE 0.017) and LDAK's 0.072 (SE 0.021) (Gorfine et al.). In its Chromosome 22 simulations it reports lower mean squared error than GCTA and LDAK, with no single summary number given in the file. Our estimator beats HERRA if it achieves lower root mean squared error in $\hat h^2$ on the same simulated replicates. The more important test is whether certificate-guided selection between HERRA and the mixed model achieves lower error than always using either one.
The key ablation removes the grouping. It computes Li and Chen's variant-level cumulative coherence on the same matrices, to confirm that the variant-level certificate is vacuous and the cluster level is the active ingredient. A second ablation replaces clustering with LD pruning to $r^2<0.2$ followed by ordinary mutual coherence, a common practitioner shortcut. A third replaces the coherence certificate with the per-region contrast-matrix program of Iouditski et al., solved within each banded region where its size is manageable. This measures how much tightness the cheap certificate gives up.
Why not just…?
Why not just use a mixed model, which needs no sparsity condition at all? Mixed models are not certificate-free in practice. HERRA's Chromosome 22 simulations show GCTA and LDAK attenuating sharply when causal variants are untyped, and the GECCO gap of 0.068 versus 0.110 is large. The mixed model stays in the study as the default estimator. The certificate's job is to say where departing from it is safe, and if certificate-guided selection never beats always-mixed-model, that is a clear negative result we will report.
Why not just prune LD and compute ordinary mutual coherence? Pruning makes coherence small by discarding variants, and the discarded variants carry tagged variance, which is part of the missing heritability being sought. The pruning ablation measures this directly. It reports both the certificate value and the heritability bias induced by dropping variants. If pruning gives comparable certificates with negligible bias, the grouped construction is unnecessary.
Why not just calibrate each estimator by simulation on the actual genotypes? This is the most serious alternative. It is cheap, and HERRA itself validates this way. Its weakness is that it certifies only the architectures one thought to simulate, whereas the coherence bound holds for every $s$-cluster-sparse architecture. We will test this head-on. Gating rules are built from simulation calibration under one architecture, such as uniformly placed causal variants, and from the certificate. Both are then evaluated under held-out architectures: clustered causal variants, effects concentrated in high-LD regions, and mixed sparse-plus-infinitesimal. If simulation calibration transfers as well as the certificate, the honest conclusion is that the certificate's value is mainly theoretical.
Proposed Experiments
The primary testbed copies HERRA's semi-synthetic design. We use real Chromosome 22 genotypes, with the 1000 Genomes European panel as the public source and the UK Biobank chromosome 22 for larger $n$. Phenotypes are simulated with $h^2$ between 0.05 and 0.7, with cluster sparsity from 5 to 500, and with causal variants either kept or masked to mimic untyped variants. Every estimator is run on identical replicates. The 1000 Genomes sample is small, at a few thousand individuals, which is precisely the regime where the bound should bite; the UK Biobank subsample lets us vary $n$ and check that error shrinks at the predicted rate in $n$.
We measure three things. The first is the fraction of chromosome 22 clusters with a non-vacuous certificate at each sparsity, which we expect to be large at the cluster level and near zero at the variant level. The second is the rank correlation, across regions and scenarios, between the certified bound and the realized $|\hat h^2 - h^2|$, together with empirical coverage of the bound. The third is the root mean squared error of certificate-gated estimation versus HERRA, moment-matching, and simulation-calibrated gating under held-out architectures. As a real-data check we compute certificates on the UK Biobank arrays used by Ge et al.. We then ask whether traits where sparse and mixed estimates disagree most sit in poorly certified regions.
The decisive check is pre-specified. The idea fails if fewer than a quarter of LD clusters are certifiable at sparsity 5 on UK Biobank chromosome 22, or if the certified bound shows no positive rank correlation with realized error. In either case the conclusion is that coherence-type certificates cannot meet real LD, even at the level where heritability lives, and that semidefinite relaxations like d'Aspremont and El Karoui are the next thing to try per region.
References
- Heritability Estimation using a Regularized Regression Approach (HERRA): Applicable to continuous, dichotomous or age-at-onset outcome
- Coherence-based performance guarantees for estimating a sparse vector under random noise
- Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- Signal recovery under cumulative coherence
- On the accuracy of l1-filtering of signals with block-sparse structure
- Restricted isometry property of random subdictionaries
- Phenome-wide heritability analysis of the UK Biobank
- Discovering non-additive heritability using additive GWAS summary statistics
- Implicit Regularization for Optimal Sparse Recovery
- Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics