A Faster Subquadratic Algorithm for Finding Outlier Correlations
A Faster Subquadratic Algorithm for Finding Outlier Correlations
复制标题
用于查找离群值相关性的更快的次二次算法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Kohonen
中科院分区：
文献类型：
--
作者：
Matti Karppa;P. Kaski;J. Kohonen
我们研究在 n 个变量集合中检测强相关变量的离群值对的问题，否则成对相关性较弱。归一化后，此任务相当于几何任务，其中我们给出一组具有单位欧几里德范数和维度 d 的 n 个向量作为输入，并且对于某些常数 0<τ < ρ < 1，我们被要求找到其内积绝对值至少为 ρ 的所有离群向量对，前提是除了最多 q 对向量外，所有向量的绝对值内积最多为 τ。改进 Valiant 的算法 [FOCS 2012； J. ACM 2015]，我们提出了一种随机算法，对于布尔输入（归一化为单位欧几里德长度的 { −1,1} 值数据），运行时间为 Õ((nmax,{ 1−γ +M(Δ γ ,γ),M(1−γ ,2 Δ γ)}+qdn2γ)，其中 0<γ < 1 是常数权衡参数，M(μ, ν) 是将 ⌊ nμ ⌋ × ⌊ nν ⌋ 矩阵与 ⌊ nν ⌋ × ⌊ nμ ⌋ 矩阵相乘，并且 Δ =1/(1−logτ ρ) 作为推论，我们获得在时间 Õ( (n2/ω 3−logτ ρ + qdn2/(1−logτ ρ)3=logττ ρ) 和 中运行的随机算法。 time õ( (n4 / 2+α (1−logτ ρ)+qdn2/α (1−logτ ρ)2+α (1−logτ ρ)>)，其中 2≤ ω <2.38 是方阵乘法的指数，0.3<α ≤ 1 是矩形矩阵乘法的指数。符号 Õ(ṡ) 隐藏了 n 和 d 中的多对数因子，其次数可能取决于 ρ 和 τ。我们提出了灯泡问题和学习稀疏布尔函数的进一步推论。
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 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 Õ((nmax,{ 1−γ +M(Δ γ ,γ),M(1−γ ,2 Δ γ)}+qdn2γ), where 0<γ < 1 is a constant tradeoff parameter and M(μ, ν) is the exponent to multiply an ⌊ nμ ⌋ × ⌊ nν ⌋ matrix with an ⌊ nν ⌋ × ⌊ nμ ⌋ matrix and Δ =1/(1−logτ ρ). As corollaries we obtain randomized algorithms that run in time Õ( (n2/ω 3−logτ ρ + qdn2/(1−logτ ρ)3=logττ ρ) and in time õ( (n4 / 2+α (1−logτ ρ)+qdn2/α (1−logτ ρ)2+α (1−logτ ρ)>), where 2≤ ω <2.38 is the exponent for square matrix multiplication and 0.3<α ≤ 1 is the exponent for rectangular matrix multiplication. The notation Õ(ṡ) 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.