Efficient methods for grouping vectors into low-rank clusters

Research output: Contribution to journalArticlepeer-review


We present a few practical algorithms for sorting vectors into low-rank clusters. These algorithms rely on a subdivision scheme applied to the space of projections from d-dimensions to 1-dimension. This subdivision scheme can be thought of as a higher-dimensional generalization of quicksort. Given the ability to quickly sort vectors into low-rank clusters, one can efficiently search a matrix for low-rank sub-blocks of large diameter. The ability to detect large-diameter low-rank sub-blocks has many applications, ranging from data-analysis to matrix-compression.

Original languageEnglish (US)
Pages (from-to)5684-5703
Number of pages20
JournalJournal of Computational Physics
Issue number14
StatePublished - Jun 20 2011


  • Hierarchical factorization
  • Principal-component-analysis

ASJC Scopus subject areas

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


Dive into the research topics of 'Efficient methods for grouping vectors into low-rank clusters'. Together they form a unique fingerprint.

Cite this