# FANOK: Knockoffs in Linear Time

arXiv: https://arxiv.org/abs/2006.08790 · HTML: https://mlsanity.com/paper/2006.08790/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [Virtual Dummies: Enabling Scalable FDR-Controlled Variable Selection via Sequential Sampling of Null Features](https://mlsanity.com/paper/2604.07464/) (2026)

## Abstract (arXiv)

We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. Identifying the knockoff distribution requires solving a large scale semidefinite program for which we derive several efficient methods. One handles generic covariance matrices, has a complexity scaling as O(p3) where p is the ambient dimension, while another assumes a rank k factor model on the covariance matrix to reduce this complexity bound to O(pk2). We also derive efficient procedures to both estimate factor models and sample knockoff covariates with complexity linear in the dimension. We test our methods on problems with p as large as 500,000.