Combining Structured and Unstructured Randomness in Large Scale PCA

2013/10/23 by Nikos Karampatziakis, Karampatziakis, Nikos, Paul Mineiro +1
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1310.6304

openalex publication_date 2013/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Principal Component Analysis (PCA) is a ubiquitous tool with many applications in machine learning including feature construction, subspace embedding, and outlier detection. In this paper, we present an algorithm for computing the top principal components of a dataset with a large number of rows (examples) and columns (features). Our algorithm leverages both structured and unstructured random projections to retain good accuracy while being computationally efficient. We demonstrate the technique on the winning submission the KDD 2010 Cup.

Citations

• The Approximation of One Matrix by Another of Lower Rank
• Perturbation bounds in connection with singular value decomposition
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Related

• Single-Pass PCA of Large High-Dimensional Data
• Selecting the number of components in PCA via random signflips
• Self-Paced Probabilistic Principal Component Analysis for Data with Outliers
• Ensemble Principal Component Analysis
• Fast Randomized PCA for Sparse Data