Cover Image

Deterministic Coreset for Lp Subspace

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chhaya, Rachit, Dasgupta, Anirban, Feldman, Dan, Shit, Supratim
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Simple PTAS for Weighted $k$-means and Sensor Coverage
by: Pareek, Akash, et al.
Published: (2025)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

Coreset Spectral Clustering
by: Jourdan, Ben, et al.
Published: (2025)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
by: Roy, Shubhajit, et al.
Published: (2023)

Coresets for Clustering Under Stochastic Noise
by: Huang, Lingxiao, et al.
Published: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Scalable Learning of Multivariate Distributions via Coresets
by: Ding, Zeyu, et al.
Published: (2026)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
by: Dasgupta, Sanjoy, et al.
Published: (2024)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
by: Fang, Ziyi, et al.
Published: (2025)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

A Note On Deterministic Submodular Maximization With Bounded Curvature
by: Li, Wenxin
Published: (2024)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

TimeCluster with PCA is Equivalent to Subspace Identification of Linear Dynamical Systems
by: Hines, Christian L., et al.
Published: (2025)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
by: Diakonikolas, Ilias, et al.
Published: (2024)

Constructing Long Paths in Graph Streams
by: Konrad, Christian, et al.
Published: (2025)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

Local Search-based Individually Fair Clustering with Outliers
by: Maity, Binita, et al.
Published: (2025)

Coresets for Kernel Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2021)

Optimal Embedding Dimension for Sparse Subspace Embeddings
by: Chenakkod, Shabarish, et al.
Published: (2023)

Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
by: Gao, Chao, et al.
Published: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

On Differentially Private Subspace Estimation in a Distribution-Free Setting
by: Tsfadia, Eliad
Published: (2024)

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
by: Tukan, Murad, et al.
Published: (2024)

Robust Learning of Multi-index Models via Iterative Subspace Approximation
by: Diakonikolas, Ilias, et al.
Published: (2025)

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
by: Chenakkod, Shabarish, et al.
Published: (2024)

Local Pan-Privacy for Federated Analytics
by: Feldman, Vitaly, et al.
Published: (2025)

PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
by: Asi, Hilal, et al.
Published: (2025)

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
by: Chenakkod, Shabarish, et al.
Published: (2025)

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
by: Swartworth, William, et al.
Published: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Nearly Optimal Attention Coresets
by: Liberty, Edo, et al.
Published: (2026)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2025)

$L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
by: Lin, Honghao, et al.
Published: (2025)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

Efficient Adaptive Data Analysis over Dense Distributions
by: Huh, Joon Suk
Published: (2026)