A unified framework for approximating and clustering data

2011/06/06 by Dan Feldman, Michael Langberg · 2 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Face and Expression Recognition #Topological and Geometric Data Analysis

paper · pdf · doi:10.1145/1993636.1993712

openalex publication_date 2011/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

Given a set F of n positive functions over a ground set X, we consider the problem of computing x* that minimizes the expression ∑f ∈ Ff(x), over x ∈ X. A typical application is shape fitting, where we wish to approximate a set P of n elements (say, points) by a shape x from a (possibly infinite) family X of shapes. Here, each point p ∈ P corresponds to a function f such that f(x) is the distance from p to x, and we seek a shape x that minimizes the sum of distances from each point in P. In the k-clustering variant, each x∈ X is a tuple of k shapes, and f(x) is the distance from p to its closest shape in x.

Citations

• Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)
• A PTAS for k-means clustering based on weak coresets
• Near-Optimal Column-Based Matrix Reconstruction
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

Cited by

• A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification
• Parameterized approximation algorithm [wikipedia]