Detecting low-rank clusters via random sampling

Research output: Contribution to journalArticle

Abstract

We present an algorithm for detecting a low-rank cluster of vectors from within a much larger group of vectors. This algorithm relies on a basic geometric property of high-dimensional space: Most of the volume of a typical eccentric ellipsoid is confined to relatively few orthants within the ambient space. This simple fact can be used to quickly detect a collection of vectors with low numerical rank from amongst a larger group of vectors with higher numerical rank.

Original languageEnglish (US)
Pages (from-to)215-222
Number of pages8
JournalJournal of Computational Physics
Volume231
Issue number1
DOIs
StatePublished - Jan 1 2012

Keywords

  • Random rotation projection

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy(all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Detecting low-rank clusters via random sampling'. Together they form a unique fingerprint.

  • Cite this