Separating Populations with Wide Data: A Spectral Analysis

DOI10.1007/978-3-540-77120-3_39MaRDI QIDQ5387777zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Shuheng Zhou, Avrim Blum, Alan Frieze

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0706.3434

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Statistical distribution theory (62E99) Applications of statistics (62P99)

Abstract: In this paper, we consider the problem of partitioning a small data sample drawn from a mixture of $k$ product distributions. We are interested in the case that individual features are of low average quality $gamma$, and we want to use as few of them as possible to correctly partition the sample. We analyze a spectral technique that is able to approximately optimize the total data size--the product of number of data points $n$ and the number of features $K$--needed to correctly perform this partitioning as a function of $1/gamma$ for $K>n$. Our goal is motivated by an application in clustering individuals according to their population of origin using markers, when the divergence between any two of the populations is small.

Recommendations

• Separating populations with wide data: a spectral analysis
• Learning Theory
• A spectral algorithm for learning mixture models
• The Spectral Method for General Mixture Models
• Learning Theory

Cites work

• A rigorous analysis of population stratification with limited data
• Concentration of norms and eigenvalues of random matrices
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Learning mixtures of arbitrary Gaussians
• Learning Mixtures of Product Distributions over Discrete Domains
• Learning Theory
• On the learnability of discrete distributions
• PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption
• Some estimates of norms of random matrices
• Spectral norm of random matrices

Cited in

(5)

• Separating populations with wide data: a spectral analysis
• A rigorous analysis of population stratification with limited data
• Separation of the largest eigenvalues in eigenanalysis of genotype data from discrete subpopulations
• An attempt to separate \(A \rightarrow B\) process spectra. Separation by minimum overlapping method SEMILAM
• Leave-one-out singular subspace perturbation analysis for spectral clustering

This page was built for publication: Separating Populations with Wide Data: A Spectral Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387777)