One-pass additive-error subset selection for _p subspace approximation and (k, p)-clustering

DOI10.1007/S00453-023-01124-0OpenAlexW4376149126MaRDI QIDQ6046948FDOQ6046948

Authors: Amit Deshpande, Rameshwar Pratap 

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01124-0

zbMATH Keywords

\(k\)-means clusteringsubset selectionsubspace approximation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Title not available (Why is that?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• CUR matrix decompositions for improved data analysis
• Low-Rank Approximation and Regression in Input Sparsity Time
• Relative-Error $CUR$ Matrix Decompositions
• Tensor-CUR Decompositions for Tensor-Based Data
• Fast monte-carlo algorithms for finding low-rank approximations
• Randomized Algorithms for Matrices and Data
• Competitive recommendation systems
• Random sampling with a reservoir
• Adaptive Sampling for k-Means Clustering
• The planar \(k\)-means problem is NP-hard
• Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Title not available (Why is that?)
• Sampling-based dimension reduction for subspace approximation
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Matrix approximation and projective clustering via volume sampling
• A general purpose unequal probability sampling plan
• A PTAS for ℓ_p-Low Rank Approximation
• Title not available (Why is that?)
• Relative Errors for Deterministic Low-Rank Matrix Approximations
• Frequent directions: simple and deterministic matrix sketching
• Exact bound for the convergence of metropolis chains
• Optimal Column-Based Low-Rank Matrix Reconstruction
• Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
• Title not available (Why is that?)
• Core-Sets: Updated Survey
• Non-adaptive adaptive sampling on turnstile streams

This page was built for publication: One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering

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