FANOK swMATH ID: 42241 Software Authors: Armin Askari, Quentin Rebjock, Alexandre d'Aspremont, Laurent El Ghaoui Description: FANOK: Knockoffs in Linear Time. 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 Homepage: https://arxiv.org/abs/2006.08790 Source Code: https://github.com/qrebjock/fanok Related Software: DeepPINK; KnockoffGAN; Knockpy; Python; glasso; SCS; CVXPY; Scikit Cited in: 2 Publications Cited by 5 Authors 1 Askari, Armin 1 d’Aspremont, Alexandre 1 Janson, Lucas 1 Rebjock, Quentin 1 Spector, Asher Cited in 2 Serials 1 The Annals of Statistics 1 SIAM Journal on Mathematics of Data Science Cited in 2 Fields 2 Statistics (62-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year