Sampling-based dimension reduction for subspace approximation with outliers

DOI10.1016/j.tcs.2021.01.021zbMath1478.62078OpenAlexW3121111608MaRDI QIDQ2222095

Amit Deshpande, Rameshwar Pratap

Publication date: 3 February 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.021

zbMATH Keywords

samplingoutliersapproximation algorithmsdimensionality reductionlow-rank approximation

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Nonparametric estimation (62G05) Approximation algorithms (68W25)

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Efficient subspace approximation algorithms
• On the complexity of approximating extremal determinants in matrices
• Graph expansion and the unique games conjecture
• A Novel M-Estimator for Robust PCA
• Computational Advertising: Techniques for Targeting Relevant Ads
• Sampling-based dimension reduction for subspace approximation
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Fast, robust and non-convex subspace recovery
• Relative Errors for Deterministic Low-Rank Matrix Approximations
• A unified framework for approximating and clustering data
• Fast monte-carlo algorithms for finding low-rank approximations