Can linear algebra create perfect knockoffs?

Christopher Hemmens, Stephan Robert-Nicoud · 2025

Read Can linear algebra create perfect knockoffs? by Christopher Hemmens, Stephan Robert-Nicoud (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02148.txt.

Introduction

Christopher Hemmens and Stephan Robert-Nicoud ask whether pure linear algebra can build perfect knockoffs, the fake data columns used to test which variables truly matter. Their 2025 paper works in the Model-X knockoff framework, where each real variable gets a synthetic twin that mimics its ties to the others without copying its link to the outcome. Most work aims at sampling the twins from the right distribution.

Judged by the average absolute correlation between twins and originals, their construction reaches near-perfect quality. The catch is cost: the optimizing routine is very slow. The pair then lay out a series of shortcuts that cut the run time sharply. The note maps a trade between knockoff quality and computing budget that method builders can exploit.

Catalog record

CREATORChristopher Hemmens, Stephan Robert-Nicoud
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02148

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Can linear algebra create perfect knockoffs? Christopher Hemmens, Stephan Robert-Nicoud Abstract As new Model-X knockoff construction techniques are developed, primarily concerned with determining the correct conditional distribution from which to sample, we focus less on deriving the correct multivariate distribution and instead ask if “perfect" knockoffs can be constructed using linear algebra. Using mean absolute correlation between knockoffs and features as a measure of quality, we do produce knockoffs that are pseudo-perfect, however, the optimization algorithm is computationally very expensive. We outline a series of methods to significantly reduce the computation time of the algorithm. 1 Introduction Candes et al. [ 3 ] asked how to control the false discovery rate in high-dimensional non-linear models, for example, what if you have more features than observations but you know only a handful of the features has any predictive power on the response variable? The authors’ solution was the introduction of Model-X Knockoffs – a set of random variables that statistically mimic the original feature set but, by design, do not have any predictive power on the response variable. The definition of a Model-X Knockoff, \tilde{X} , for a feature set X is as follows: 1. for any subset S\subset\{1,\dots,p\} , (X,\tilde{X})_{\text{swap}(S)}\stackrel{{\scriptstyle d}}{{=}}(X,\tilde{X}) ; 2. \tilde{X}\Perp Y | X if there is a response Y . Note that as long as \tilde{X} is constructed without knowledge of Y , condition 2 is automatically satisfied. [ 3 ] test this methodology by replicating [ 10 ] , who identify gene clusters that predict the development of Crohn’s disease in patients. Whereas the original study was able to identify 9 gene clusters, by implementing the Model-X Knockoff methodology, [ 3 ] was able to identify 18 gene clusters. Since then, several steps have been taken to improve the methodology. For example, [ 1 ] add implementation of the Metropolis-Hastings (MH) algorithm ( [ 6 ] , [ 4 ] ) which, although more computationally expensive, improves the “quality" of the knockoffs as measured by the mean absolute correlation between the knockoffs and their features. The key insight with regard to adding the MH algorithm to the construction process is that it’s a Markov chain method that is time-reversible, and therefore mimics the condition that features and knockoffs are able to be swapped without affecting the distribution. The one element that connects every approach to generating knockoffs since the 2018 paper is the focus on deriving the correct conditional distribution from which to sample the knockoffs. But is this a necessary step? In every case we start with a p\times n matrix and our goal is to generate another p\times n matrix that fulfils a number of linear constraints. Hence, it is possible to reframe this problem not as deriving the correct conditional distribution from which to sample, but a linear algebra optimization problem subject to a series of linear constraints. If we can ensure that the univariate distributions of the knockoffs match those of the features, which is trivial, and that the main co-moments between all the features and knockoffs match up, then for a relevant subset of multivariate distributions, we will have constructed the best possible knockoffs for that distribution. This process, however, is computationally very expensive, so one of the main aspects of this paper is a discussion on methods to reduce the computation time as much as possible while still ensuring pseudo-perfect knockoffs. In this paper, section 2 summarizes the literature on knockoff construction to date; section 3 outlines how to frame the problem using linear algebra; section 4 tests the methodology on a set of artificially generated random variables with enforced non-zero values of coskewness and cokurtosis; section 5 tests the methodology on a real dataset that in particular presents a serious challenge to the knockoff generation procedure in general; section 6 concludes the paper. 2 Literature Review In addition to the initial knockoff construction algorithms put forth by [ 3 ] and [ 1 ] , a wide range of other knockoff-generating methods have been developed. For example, [ 8 ] use deep generative models to sample knockoffs using a criterion measuring the validity of the knockoffs produced by the model. [ 2 ] use copulas to generate knockoffs. Essentially, if the distribution of the p features is F(x_{1},\dots,x_{p}) , then, by Sklar’s Theorem ( [ 9 ] ) there exists a p -copula C and univariate distributions F_{1},\dots,F_{p} such that F(x_{1},\dots,x_{p})=C\left[F_{1}(x_{1}),\dots,F_{p}(x_{p})\right],\,\forall x_{1},\dots,x_{p} By carefully selecting a set of 2-copulas D_{1},\dots,D_{p} , a new distribution can be created H(x_{1},\dots,x_{p},x_{p+1},\dots,x_{2p})=C\left[D_{1}\left(F_{1}(x_{1}),F_{1}(x_{p+1})\right),\dots,D_{p}\left(F_{p}(x_{p}),F_{p}(x_{2p})\right)\right] from which knockoffs can be constructed. [ 5 ] also look at copulas but vine copulas. They use this method because it’s especially strong for high-dimensionally modelling. However, unlike the method in [ 2 ] that samples all the knockoffs at once, they generate the knockoffs recursively, like in [ 3 ] and [ 1 ] . Since the knockoff construction algorithm is typically random, [ 7 ] introduce a method for derandomizing the procedure and making it more stable by constructing multiple sets of knockoffs and aggregating the results. 3 Methodology Suppose we have a multivariate distribution F(x_{1},\dots,x_{p})=Pr(X_{1}\leq x_{1},\dots,X_{p}\leq x_{p}) where the cumulative distribution function (CDF) of X_{i} is F_{i}:\mathbb{R}\rightarrow[0,1] . Suppose also that we have a sample of this distribution with n observations. Our goal is to use a linear algebra optimization approach to construct perfect Model-X knockoffs. That is, if the original sample is \mathcal{X}\equiv(X_{1},\dots,X_{p})\in\mathbb{R}^{p\times n} , then we want to find a matrix \tilde{\mathcal{X}}\equiv(\tilde{X}_{1},\dots,\tilde{X}_{p})\in\mathbb{R}^{p\times n} such that the statistical moments of each feature and the other features are equal to the statistical moments of that feature’s knockoff and the other features, as well as between that feature’s knockoff and the other features’ knockoffs, while minimizing the absolute value of the correlation between each feature and its knockoff. We focus on equating up to the fourth statistical moment: correlation, coskewness, and cokurtosis. To understand our approach, you have to know that generating knockoffs using linear algebra is disproportionately computationally expensive compared to sampling from a distribution and, as a result, our methodology concentrates on minimizing the amount of work a computer needs to do. 3.1 Setting Constraints We define our (standardized) (m,k) -moment between variables X and Y to be \mu_{m,k}(X,Y)=\frac{\frac{1}{n}\sum_{i=1}^{n}\left((x_{i}-\mu_{1}(X))^{k}(y_{i}-\mu_{1}(Y))^{m-k}\right)}{(\mu_{2}(X))^{k/2}(\mu_{2}(Y))^{(m-k)/2}} where \mu_{1}(X)=\frac{1}{n}\sum_{i=1}^{n}x_{i} and \mu_{2}(X)=\frac{1}{n}\sum_{i=1}^{n}(x_{i}-\mu_{1}(X))^{2} This means our first constraints on each knockoff are that they have the same distributions as their features. We ensure this by determining the distribution of the feature in advance, and then performing a Kolmogorov-Smirnov test on the knockoff. We set the constraint that the p-value of the test’s result is as close to 1 as possible. The next set of constraints are simply that for every value of i,j=1,\dots,p where i\neq j , and 2\leq m\leq 4 with 1\leq k\leq(m-1) , we have 1. \mu_{m,k}(\tilde{X}_{i},X_{j})=\mu_{m,k}(X_{i},X_{j}) 2. \mu_{m,k}(X_{i},\tilde{X}_{j})=\mu_{m,k}(X_{i},X_{j}) 3. \mu_{m,k}(\tilde{X}_{i},\tilde{X}_{j})=\mu_{m,k}(X_{i},X_{j}) We are careful not to duplicate any of these constraints, for example, \mu_{4,1}\left(X_{i},\tilde{X}_{j}\right) and \mu_{4,3}\left(\tilde{X}_{j},X_{i}\right) are the same condition, so we only include it once in the optimization process. 3.2 Optimizing Now the constraints are set, we want to optimize the knockoffs such that the correlations between the features and their knockoffs are as close to zero as possible. In many circumstances, it may not be possible to generate knockoffs with zero

Read the complete text