A PTAS for ℓp-Low Rank Approximation.
Frank BanVijay BhattiproluKarl BringmannPavel KolevEuiwoong LeeDavid P. WoodruffPublished in: SODA (2019)
Keyphrases
- low rank approximation
- singular value decomposition
- low rank matrix approximation
- approximation algorithms
- subspace learning
- low rank
- kernel matrix
- spectral clustering
- adjacency matrix
- iterative algorithms
- latent semantic indexing
- data dependent
- reconstruction error
- nonnegative matrix factorization
- dimensionality reduction
- special case
- eigendecomposition
- matrix factorization
- matrix completion
- np hard
- data representation
- image segmentation
- kernel methods
- high order
- linear combination
- feature extraction