A faster subquadratic algorithm for finding outlier correlations

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and for some constants 0<τ<ρ<1, we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value. Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs (-1,1-valued data normalized to unit Euclidean length) runs in time [ tilde Obigl(n^max,1-γ+M(Deltaγ,γ),,M(1-γ,2Deltaγ)+qdn2γbigr),, ] where 0<γ<1 is a constant tradeoff parameter and M(μ,nu) is the exponent to multiply an lfloor nμrfloor×lfloor n^nurfloor matrix with an lfloor n^nurfloor× lfloor nμrfloor matrix and Delta=1/(1-logτρ). As corollaries we obtain randomized algorithms that run in time [ tilde Obigl(n^frac2ω3-logτρ+qdn^frac2(1-logτρ)3-logτρbigr) ] and in time [ tilde Obigl(n^frac42+α(1-logτρ)+qdn^frac2α(1-logτρ)2+α(1-logτρ)bigr),, ] where 2≤ω<2.38 is the exponent for square matrix multiplication and 0.3<α≤ 1 is the exponent for rectangular matrix multiplication. The notation tilde O(·) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ. We present further corollaries for the light bulb problem and for learning sparse Boolean functions.