A faster subquadratic algorithm for finding outlier correlations

DOI10.1145/3174804MaRDI QIDQ4554359zbMATH OpenOpenAlexWikidataFDO

Authors Matti Karppa, Petteri Kaski, Jukka Kohonen

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.03895

zbMATH Keywords

correlationfast matrix multiplicationlight bulb problemrectangular matrix multiplicationsimilarity search

Mathematics Subject Classification ID

Measures of association (correlation, canonical correlation, etc.) (62H20) Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: 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<au<ho<1$, we are asked to find all the outlier pairs of vectors whose inner product is at least $ho$ in absolute value, subject to the promise that all but at most $q$ pairs of vectors have inner product at most $au$ 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 [ ilde O�igl(n^{max,{1-gamma+M(Deltagamma,gamma),,M(1-gamma,2Deltagamma)}}+qdn^{2gamma}�igr),, ] where $0<gamma<1$ is a constant tradeoff parameter and $M(mu,u)$ is the exponent to multiply an $lfloor{n}^{m}ufloorimeslfloor{n}^{u}floor$ matrix with an $lfloor{n}^{u}floorimeslfloor{n}^{m}ufloor$ matrix and $Delta=1/(1-lo{g}_{a}uho)$. As corollaries we obtain randomized algorithms that run in time [ ilde O�igl(n^{frac{2omega}{3-log_ au ho}}+qdn^{frac{2(1-log_ au ho)}{3-log_ au ho}}�igr) ] and in time [ ilde O�igl(n^{frac{4}{2+alpha(1-log_ au ho)}}+qdn^{frac{2alpha(1-log_ au ho)}{2+alpha(1-log_ au ho)}}�igr),, ] where $2leqomega<2.38$ is the exponent for square matrix multiplication and $0.3<alphaleq1$ is the exponent for rectangular matrix multiplication. The notation $ildeO(cdot)$ hides polylogarithmic factors in $n$ and $d$ whose degree may depend on $ho$ and $au$. We present further corollaries for the light bulb problem and for learning sparse Boolean functions.

Recommendations

• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• scientific article; zbMATH DE number 6846423
• Fast sketch-based recovery of correlation outliers

Cited in

(12)

• A new algorithm for finding closest pair of vectors (extended abstract)
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• Fast sketch-based recovery of correlation outliers
• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• scientific article; zbMATH DE number 6846423 (Why is no real title available?)
• Tensor network complexity of multilinear maps
• Convex transform order of Beta distributions with some consequences
• An illuminating algorithm for the light bulb problem
• A non-trivial algorithm enumerating relevant features over finite fields
• Counting short vector pairs by inner product and relations to the permanent
• The planted orthogonal vectors problem

This page was built for publication: A faster subquadratic algorithm for finding outlier correlations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554359)