Sampling-based dimension reduction for subspace approximation with outliers

DOI10.1016/J.TCS.2021.01.021MaRDI QIDQ2222095zbMATH OpenOpenAlexFDO

Authors 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

outlierssamplingdimensionality reductionlow-rank approximationapproximation algorithms

Mathematics Subject Classification ID

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

Recommendations

• Coresets and sketches for high dimensional subspace approximation problems
• Low rank approximation in the presence of outliers
• Algorithms and hardness for subspace approximation
• Efficient subspace approximation algorithms
• Optimal outlier removal in high-dimensional

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• A novel M-estimator for robust PCA
• A unified framework for approximating and clustering data
• A well-tempered landscape for non-convex robust subspace recovery
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Constant approximation for \(k\)-median and \(k\)-means with outliers via iterative rounding
• Coresets and sketches for high dimensional subspace approximation problems
• Data reduction for weighted and outlier-resistant clustering
• Efficient subspace approximation algorithms
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast, robust and non-convex subspace recovery
• Graph expansion and the unique games conjecture
• Low rank approximation in the presence of outliers
• On the complexity of approximating extremal determinants in matrices
• Relative errors for deterministic low-rank matrix approximations
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Sampling-based dimension reduction for subspace approximation
• Sketching as a tool for numerical linear algebra

Cited in

(11)

• Coresets and sketches for high dimensional subspace approximation problems
• Low rank approximation in the presence of outliers
• A greedy algorithm for subspace approximation problem
• Optimal outlier removal in high-dimensional
• \(l_p\)-recovery of the most significant subspace among multiple subspaces with outliers
• The out-of-sample problem for classical multidimensional scaling
• Fast subspace approximation via greedy least-squares
• Optimal outlier removal in high-dimensional spaces
• Algorithms and hardness for subspace approximation
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Efficient subspace approximation algorithms

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Sampling-based dimension reduction for subspace approximation with outliers

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