A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World

Agniva Chowdhury; Aritra Bose; Samson Zhou; David P. Woodruff; Petros Drineas

doi:10.1007/978-3-031-04749-7_6

A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World

Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas

Systems and Decision Sciences

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

4 Scopus citations

Abstract

Principal component analysis (PCA) is a widely used dimensionality reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present ThreSPCA, a provably accurate algorithm based on thresholding the Singular Value Decomposition for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our thresholding algorithm is conceptually simple; much faster than current state-of-the-art; and performs well in practice. When applied to genotype data from the 1000 Genomes Project, ThreSPCA is faster than previous benchmarks, at least as accurate, and leads to a set of interpretable biomarkers, revealing genetic diversity across the world.

Original language	English
Title of host publication	Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings
Editors	Itsik Pe’er
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	86-106
Number of pages	21
ISBN (Print)	9783031047480
DOIs	https://doi.org/10.1007/978-3-031-04749-7_6
State	Published - 2022
Event	26th International Conference on Research in Computational Molecular Biology, RECOMB 2022 - San Diego, United States Duration: May 22 2022 → May 25 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13278 LNBI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Conference on Research in Computational Molecular Biology, RECOMB 2022
Country/Territory	United States
City	San Diego
Period	05/22/22 → 05/25/22

Funding

Acknowledgements. PD and AC were partially supported by National Science Foundation (NSF) 10001390, NSF III-10001674, NSF III-10001225, and an IBM Faculty Award to PD. AB was supported by IBM. DPW and SZ would like to thank partial support from NSF grant No. CCF-181584, Office of Naval Research (ONR) grant N00014-18-1-2562, National Institute of Health (NIH) grant 5401 HG 10798-2, and a Simons Investigator Award.

Keywords

Population stratification
Population structure
Principal Component Analysis
Sparse PCA

Access to Document

10.1007/978-3-031-04749-7_6

Cite this

Chowdhury, A., Bose, A., Zhou, S., Woodruff, D. P., & Drineas, P. (2022). A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. In I. Pe’er (Ed.), Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings (pp. 86-106). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13278 LNBI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-04749-7_6

Chowdhury, Agniva ; Bose, Aritra ; Zhou, Samson et al. / A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings. editor / Itsik Pe’er. Springer Science and Business Media Deutschland GmbH, 2022. pp. 86-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6962255298dc434785c421d8a7cdbf2e,

title = "A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World",

abstract = "Principal component analysis (PCA) is a widely used dimensionality reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present ThreSPCA, a provably accurate algorithm based on thresholding the Singular Value Decomposition for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our thresholding algorithm is conceptually simple; much faster than current state-of-the-art; and performs well in practice. When applied to genotype data from the 1000 Genomes Project, ThreSPCA is faster than previous benchmarks, at least as accurate, and leads to a set of interpretable biomarkers, revealing genetic diversity across the world.",

keywords = "Population stratification, Population structure, Principal Component Analysis, Sparse PCA",

author = "Agniva Chowdhury and Aritra Bose and Samson Zhou and Woodruff, {David P.} and Petros Drineas",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 26th International Conference on Research in Computational Molecular Biology, RECOMB 2022 ; Conference date: 22-05-2022 Through 25-05-2022",

year = "2022",

doi = "10.1007/978-3-031-04749-7_6",

language = "English",

isbn = "9783031047480",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "86--106",

editor = "Itsik Pe{\textquoteright}er",

booktitle = "Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings",

}

Chowdhury, A, Bose, A, Zhou, S, Woodruff, DP & Drineas, P 2022, A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. in I Pe’er (ed.), Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13278 LNBI, Springer Science and Business Media Deutschland GmbH, pp. 86-106, 26th International Conference on Research in Computational Molecular Biology, RECOMB 2022, San Diego, United States, 05/22/22. https://doi.org/10.1007/978-3-031-04749-7_6

A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. / Chowdhury, Agniva; Bose, Aritra; Zhou, Samson et al.
Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings. ed. / Itsik Pe’er. Springer Science and Business Media Deutschland GmbH, 2022. p. 86-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13278 LNBI).

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

TY - GEN

T1 - A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World

AU - Chowdhury, Agniva

AU - Bose, Aritra

AU - Zhou, Samson

AU - Woodruff, David P.

AU - Drineas, Petros

PY - 2022

Y1 - 2022

N2 - Principal component analysis (PCA) is a widely used dimensionality reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present ThreSPCA, a provably accurate algorithm based on thresholding the Singular Value Decomposition for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our thresholding algorithm is conceptually simple; much faster than current state-of-the-art; and performs well in practice. When applied to genotype data from the 1000 Genomes Project, ThreSPCA is faster than previous benchmarks, at least as accurate, and leads to a set of interpretable biomarkers, revealing genetic diversity across the world.

AB - Principal component analysis (PCA) is a widely used dimensionality reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present ThreSPCA, a provably accurate algorithm based on thresholding the Singular Value Decomposition for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our thresholding algorithm is conceptually simple; much faster than current state-of-the-art; and performs well in practice. When applied to genotype data from the 1000 Genomes Project, ThreSPCA is faster than previous benchmarks, at least as accurate, and leads to a set of interpretable biomarkers, revealing genetic diversity across the world.

KW - Population stratification

KW - Population structure

KW - Principal Component Analysis

KW - Sparse PCA

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

U2 - 10.1007/978-3-031-04749-7_6

DO - 10.1007/978-3-031-04749-7_6

M3 - Conference contribution

AN - SCOPUS:85131150782

SN - 9783031047480

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 106

BT - Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings

A2 - Pe’er, Itsik

PB - Springer Science and Business Media Deutschland GmbH

T2 - 26th International Conference on Research in Computational Molecular Biology, RECOMB 2022

Y2 - 22 May 2022 through 25 May 2022

ER -

Chowdhury A, Bose A, Zhou S, Woodruff DP, Drineas P. A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. In Pe’er I, editor, Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 86-106. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-04749-7_6