# A faster subquadratic algorithm for finding outlier correlations

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

### Researchers

### Research units

### 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 we are asked to find all the outlier pairs of vectors whose inner product is at least p in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most r in absolute value for some constants 0 <t <p <1. Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({-1, l}-valued data normalized to unit Euclidean length) runs in time Q(nmax{l-γ, +M(δγ γ), M(l-γ, 2δ γ)} +qdnγ) where 0 <γ <1 is a constant tradeoff parameter and M(μ, v ) is the exponent to multiply an [nμ] × [nv] matrix with an [nv]×[nμ] matrix and A = 1/(1-logTp). As corollaries we obtain randomized algorithms that run in time O(2Omega;/n3-logTp+qdn 2(1-logTp)/3-logTp and in time O(4/n2+α(1-logTp+qdn 2α(1-logTp)/2+α(1-logTp) where 2 <ω <2.38 is the exponent for square matrix multiplication and 0.3 <α<1 is the exponent for rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation O(-) hides polylogarithmic factors in n and d whose degree may depend on p and t.)

### Details

Original language | English |
---|---|

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Subtitle of host publication | SODA 2016, Arlington, VA, USA, January 10-12, 2016 |

Editors | Robert Krauthgamer |

Publication status | Published - 2016 |

MoE publication type | A4 Article in a conference publication |

Event | ACM-SIAM Symposium on Discrete Algorithms - Arlington, United States Duration: 10 Jan 2016 → 12 Jan 2016 Conference number: 27 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country | United States |

City | Arlington |

Period | 10/01/2016 → 12/01/2016 |

ID: 2549191