Detecting low-rank clusters via random sampling

Aaditya V. Rangan

doi:10.1016/j.jcp.2011.09.008

Detecting low-rank clusters via random sampling

Aaditya V. Rangan

Mathematics

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	215-222
Number of pages	8
Journal	Journal of Computational Physics
Volume	231
Issue number	1
DOIs	https://doi.org/10.1016/j.jcp.2011.09.008
State	Published - Jan 1 2012

Keywords

Random rotation projection

ASJC Scopus subject areas

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

Access to Document

10.1016/j.jcp.2011.09.008

Cite this

@article{6217b369ba5a46979ffc16ebd7aecc9e,

title = "Detecting low-rank clusters via random sampling",

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.",

keywords = "Random rotation projection",

author = "Rangan, {Aaditya V.}",

year = "2012",

month = jan,

day = "1",

doi = "10.1016/j.jcp.2011.09.008",

language = "English (US)",

volume = "231",

pages = "215--222",

journal = "Journal of Computational Physics",

issn = "0021-9991",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Detecting low-rank clusters via random sampling

AU - Rangan, Aaditya V.

PY - 2012/1/1

Y1 - 2012/1/1

N2 - 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.

AB - 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.

KW - Random rotation projection

UR - http://www.scopus.com/inward/record.url?scp=80054861590&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054861590&partnerID=8YFLogxK

U2 - 10.1016/j.jcp.2011.09.008

DO - 10.1016/j.jcp.2011.09.008

M3 - Article

AN - SCOPUS:80054861590

SN - 0021-9991

VL - 231

SP - 215

EP - 222

JO - Journal of Computational Physics

JF - Journal of Computational Physics

IS - 1

ER -

Detecting low-rank clusters via random sampling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this