Searches for physics beyond the Standard Model increasingly fail for a mundane reason. The data are plentiful, but the simulation used to predict background events is wrong in ways nobody has parameterized. A common fix is to learn the background from the data itself. Events from control regions are modeled as non-negative mixtures of a few unknown background shapes, a non-negative matrix factorization or NMF. A new-physics signal would then show up as an event histogram that no such mixture can explain. The danger is flexibility. NMF solutions are generally not unique, so a learned background can rotate to swallow a real signal, or bend to "explain" a calibration drift that is not physics at all. We propose to test candidate excesses only against the background constraints that every admissible factorization of the control data shares. These are the facets of the background cone that are mathematically certified as unique. Because a background set defined by certified facets alone contains every admissible background, the test is conservative by construction. It is also a convex problem, even though finding the factorization itself is NP-hard.
In two sentences: learn the background from control data as a non-negative mixture, but keep only those boundary constraints of the mixture that provably cannot move. Then flag signal-region data that violate one of those fixed constraints. The contribution is a way to make data-driven background modeling safe against both signal absorption and systematic mismodeling. It pairs a statistic that is conservative by construction with a way of recovering power when the experiment supplies pure control samples.
Core Claim
Picture each control slice j (a mass window, a run period, an off-resonance sample) as a histogram $n_j$ with $d$ bins. Background-only histograms are assumed to have expectation $W h_j$ with $W \in \mathbb{R}^{d\times r}_+$ and $h_j \in \mathbb{R}^r_+$. Their expectations then live in a cone $\mathcal{C}(W)$ spanned by the $r$ columns of $W$. Geometrically this is the nested polytope picture of On the geometric interpretation of the nonnegative rank. Any valid background cone must sit between the hull of the data and the positive orthant, and choosing it is NP-hard even at rank 3 or 4. Computing a nonnegative matrix factorization - provably adds that exact solutions need time exponential in $r$ under the Exponential Time Hypothesis. Nonnegative Matrix Factorization Requires Irrationality shows that exact factors may not even be rational. Any search built on "the" fitted NMF therefore rests on an arbitrary local optimum.
We avoid choosing a factorization. Describe each candidate cone by its facets, the linear inequalities $a_k^\top \mu \ge 0$. Then build its slack matrix, the table of how far each control histogram sits from each facet. A zero slack means the histogram lies on that facet. Partial Identifiability for Nonnegative Matrix Factorization shows that such zero patterns can pin down individual components uniquely even when the whole factorization is not unique. Its data-based uniqueness theorem requires a selective window plus a full-rank complementary block. We use the dual form of this idea and call a facet certified if every rank-$r$ cone consistent with the control data shares it. Let $K$ be the set of certified facets. The certified background set and the test statistic are
$$\mathcal{B}_K=\{\mu \ge 0 : a_k^\top \mu \ge -\epsilon_k\, \mathbf{1}^\top\mu,\ k\in K\},\qquad T(y)=\min_{\mu\in\mathcal{B}_K} 2\sum_{b=1}^{d}\Big[\mu_b-y_b+y_b\log\frac{y_b}{\mu_b}\Big],$$
where $y$ is the signal-region histogram and $T$ is the Poisson deviance to the nearest certified-background expectation. The tolerance $\epsilon_k$ absorbs residual systematic spread. It is set from the run-to-run scatter of the control slack along facet $k$, in the spirit of the intrinsic-variance term of Maximum-likelihood Regression with Systematic Errors for Astronomy and the Physical Sciences. II. Every admissible cone lies inside $\mathcal{B}_K$, so $T$ never exceeds the statistic computed against any single admissible fit. The false-positive rate is therefore controlled whichever factorization is "true", and the optimization is convex. The price is power. Few certified facets means a loose $\mathcal{B}_K$.
The power question has a physics answer. In When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?, Donoho and Stodden show that a component present in every observation has no zeros and cannot be identified: their "torso" example. A continuum or multi-jet background is exactly such a torso. Experiments, however, routinely record samples that are pure in one component. Examples are off-resonance running below the $B\overline{B}$ threshold, deep sidebands, and dedicated calibration channels. Inserted as columns, these act as the pure "anchor" columns that the separability assumption behind linear-programming NMF requires (Factoring nonnegative matrices with linear programs). They create exactly the slack zeros that certification needs. The research program asks how much experimental design, meaning the choice of control samples, buys in certified power.
Research Program
The first part is theory, and it has three goals. First, prove that $\mathcal{B}_K$ contains all admissible cones when certification is exact. Second, extend the certificate from the exact, noise-free setting of Gillis and Rajkó to Poisson counts with bounded systematic drift. That paper leaves this extension open. Our route is a perturbation bound: a facet stays certified if its zero-slack columns keep a well-conditioned complementary block under the combined Poisson and systematic perturbation. Third, show that the statistic is solved in the lifted space of mixing weights rather than over explicit facets. Linear vs. Semidefinite Extended Formulations and Lifting for Simplicity supply the reason, via Yannakakis' theorem: an explicit facet list can be enormous, while a lift of size equal to the slack matrix's non-negative rank describes the same set. Slack-matrix geometry is thus the organizing lens, and it does double duty. It supplies the certificate through zero patterns and a compact representation through the lift. It is not a claim of new extension-complexity bounds.
The second part is algorithmic. In a Poisson-loss variant of anchor-based NMF, control-sample anchors are fixed and the remaining components are fit. Certification is then tested facet by facet on the resulting slack matrix. Stability of the zero pattern is measured under Poisson resampling and under explicit shifts in calibration and smearing. The optimal dual variables of the deviance problem give an interpretable output. They form a single linear combination of bins, a derived observable, that background plus systematics cannot push past its bound but the data do. This generalizes the double-ratio observables physicists already build so that shared systematics cancel.
The third part is calibration. The null distribution of $T$ comes from toys drawn at the boundary points of $\mathcal{B}_K$. The left tail gets explicit checking, because the paper cited above found that analytic approximations fail there once Poisson and systematic fluctuations are correlated.
Baselines
The naive reference is the fitted NMF test: fit one Poisson-loss NMF of rank $r$ to the control slices, then test the signal region against that single cone. It shows what happens without certification. It is expected to be both overconfident, because a rotated cone can leave real background outside, and signal-absorbing, because a rotated cone can cover the signal.
The strongest conventional competitor is a profiled template fit. Background shapes come from simulation, and systematic variations enter as constrained nuisance parameters with linear shape interpolation. This is the standard of the BABAR analyses of B → X_s γ via the recoil method (Measurement of the B → X s γ branching fraction and photon energy spectrum using the recoil method) and B → K* l+ l− angular distributions. It gets the same histograms, and its nuisance envelope is tuned on the same control slices we use. It wins whenever simulation is right. We beat it only if we keep nominal false-positive rates when the simulation is deliberately mismodeled beyond its envelope, while losing less than a stated fraction of its sensitivity when simulation is correct.
The strongest machine-learning competitor is the anomaly search of Anomaly-preserving contrastive neural embeddings. It feeds a contrastive embedding into the New Physics Learning Machine hypothesis test and reports $12.1\sigma$ global discovery significance for a supervised SimCLR Transformer on its blind benchmark, against $0\sigma$ on raw 57-dimensional inputs and $1.4\sigma$ for a 6-dimensional variational autoencoder. We rerun it on our histograms and injected signals with its published architecture and a tuning budget matched to ours. On the LHC Olympics black boxes, The LHC Olympics 2020 reports which methods detected Black Box 1 and missed Black Box 3. No reported result was found on Lacuna for a single global significance metric on those black boxes, so we compute all methods' numbers ourselves.
Two ablations isolate the key ingredient. The first tests against the facets of one fitted cone rather than only certified facets. The second drops the control-sample anchors while keeping certification, which measures how much power experimental design supplies.
Why not just…?
Why not just profile nuisance parameters in a simulation template fit? This is a real threat. When simulation is adequate, profiling is more powerful than any conservative data-driven test, and we expect to lose to it there. Its weakness is structural: profiling cannot recover a shape outside the parameterized envelope. The quasar example in the ACsys paper shows how much this matters. A feature at $p \le 0.01$ degrades to $p = 3.6\%$ under a $5\%$ systematic and to $18.1\%$ under $10\%$ once systematics are modeled, so unmodeled systematics directly produce false claims. Our mismodeling-injection experiment settles the comparison. It locates the degree of simulation error at which the certified test starts to dominate. If that crossover lies beyond realistic mismodeling, the method is not worth adopting, and we will say so.
Why not just subtract off-resonance data or interpolate sidebands? For one background component and one smooth variable, this is essentially what our method reduces to, and it may match us. The advantage appears only when several backgrounds mix in proportions that change across slices. There, simple subtraction of one control sample leaves the other components uncorrected. We therefore include one- and multi-component toy scenarios and report where plain subtraction suffices.
Why not just use a deep anomaly detector or ordinary NMF? The contrastive-embedding paper itself documents that representations tuned for background fidelity suppress anomalies. Ordinary NMF comes with no uniqueness guarantee and produces "ghosts" on invariant components, as Donoho and Stodden showed. Neither offers a false-positive guarantee under a background model it learned itself. The signal-absorption metric below measures this directly, including for the NMF-without-certification ablation.
Proposed Experiments
Four testbeds are used, from simplest to most realistic. The first two validate the certification step. The Swimmer images come from Donoho and Stodden, with the torso as an adversarial invariant component. The five-component chemical-reaction spectra come from Gillis and Rajkó. On these we check that facets certified under added Poisson noise match the known ground truth.
The third testbed is B-factory-style toys. Histograms of photon energy or missing energy are generated as mixtures of continuum, generic $B\overline{B}$, and peaking backgrounds, and an off-resonance-like pure-continuum column is optionally included. Calibration drift is injected as a slice-dependent energy-scale shift. Signals are small rare-decay-like components at controlled strengths.
The fourth testbed is the LHC Olympics R&D and black-box samples. Rows are bins of jet-substructure observables, and columns are dijet mass windows. The background varies across mass windows as a changing mixture of a few jet populations. Black Box 2 serves as the background-only null.
The metrics are defined as follows. Validity is the observed false-positive rate at nominal $\alpha$ on background-only data. Power is the discovery significance as a function of injected signal fraction. Signal absorption is the fraction of injected signal yield explained by the background fit. Certification quality is the number and accuracy of certified facets.
The decisive check has two parts. On background-only data with simulation mismodeled beyond its nuisance envelope, the certified test must stay near nominal false-positive rate while the template fit and the fitted-NMF test inflate. On injected signals, the certified test must absorb far less signal than the fitted-NMF ablation. The second check is whether adding the anchor column restores enough power to be competitive with the template fit when simulation is correct. If validity holds but power stays low even with anchors, the result is a negative one. It would show that data-driven non-negative background models cannot be both safe and sensitive without pure control samples, which is itself worth knowing before experiments adopt them.
References
- On the geometric interpretation of the nonnegative rank
- Computing a Nonnegative Matrix Factorization - Provably
- Nonnegative Matrix Factorization Requires Irrationality
- Partial Identifiability for Nonnegative Matrix Factorization
- Maximum-likelihood Regression with Systematic Errors for Astronomy and the Physical Sciences. II. Hypothesis Testing of Nested Model Components for Poisson Data
- When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?
- Factoring nonnegative matrices with linear programs
- Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
- Lifting for Simplicity: Concise Descriptions of Convex Sets
- Measurement of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>B</mml:mi><mml:mo>→</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mi>s</mml:mi></mml:msub><mml:mi>γ</mml:mi></mml:math>branching fraction and photon energy spectrum using the recoil method
- Angular distributions in the decay<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>B</mml:mi><mml:mo>→</mml:mo><mml:msup><mml:mi>K</mml:mi><mml:mo>*</mml:mo></mml:msup><mml:msup><mml:mi>l</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:msup><mml:mi>l</mml:mi><mml:mo>−</mml:mo></mml:msup></mml:math>
- Anomaly preserving contrastive neural embeddings for end-to-end model-independent searches at the LHC
- The LHC Olympics 2020 a community challenge for anomaly detection in high energy physics