Projective clustering in high dimensions using core-sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Projective clustering in high dimensions using core-sets

Full text

Pdf (204 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eighteenth annual symposium on Computational geometry table of contents

Barcelona, Spain

Pages: 312 - 318

Year of Publication: 2002

ISBN:1-58113-504-1

Authors

Sariel Har-Peled	University of Illinois, Urbana, IL
Kasturi Varadarajan	University of Iowa, Iowa City, IA

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 39, Citation Count: 16

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/513400.513440 What is a DOI?

ABSTRACT

(MATH) Let P be a set of n points in $\Re^d, and for any integer 0 &xie; k &xie; d--1, let $\RDk(P) denote the minimum over all k-flats $\FLAT$ of maxp&egr;P Dist(p,\FLAT). We present an algorithm that computes, for any 0 < &egr; < 1, a k-flat that is within a distance of (1 + $egr;) \RDk(P) from each point of P. The running time of the algorithm is dn^{O(k/&egr;⁵log(1/&egr;))}. The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P. The size of this "core-set" depends on k and &egr; but is independent of the dimension.This approach also extends to the case where we want to find a k-flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension k, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when k>1 or j>1.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
	2	N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
	3	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 09-11, 2000, San Francisco, California, United States
	4	I. Barany and Z. Furedi Computing the volume is difficult. In Discrete Comput. Geom. 2, 319--326, 1987.
	5	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	6	Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Journal of Algorithms, v.38 n.1, p.91-109, Jan. 2001 [doi>10.1006/jagm.2000.1127]
	7	Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
	8	A. Brieden and P. Gritzmann and V. Klee. Inapproximability of some geometric and quadratic optimization problems. In P. M. Pardalos, editor, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, pages 96--115, Kluwer, 2000.
	9	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	10	Peter Gritzmann , Victor Klee, Inner and outer j-radii of convex bodies in finite-dimensional normed spaces, Discrete & Computational Geometry, v.7 n.3, p.255-280, 1992 [doi>10.1007/BF02187841]
	11	Peter Gritzmann , Victor Klee, Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces, Mathematical Programming: Series A and B, v.59 n.2, p.163-213, April 14, 1993 [doi>10.1007/BF01581243]
	12	Peter Gritzmann , Victor Klee, On the complexity of some basic problems in computational convexity: I.: containment problems, Discrete Mathematics, v.136 n.1-3, p.129-174, Dec. 31, 1994 [doi>10.1016/0012-365X(94)00111-U]
	13	M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 2nd edition, 1988. 2nd edition 1994.
	14	S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
	15	S. Har-Peled, Approximate Shape Fitting via Linearization, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.66, October 14-17, 2001
	16	P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
	17	P. Indyk and M. Thorup. Approximate 1-median. manuscript, 2000.
	18	W.B. Johnson and J. Lindenstrauss. Extensions of lipshitz mapping into hilbert space. Contemporary Mathematics, 26:189--206, 1984.
	19	A. Magen. Dimensionality reductions that preserve volumes and distance to affine spaces, and its algorithmic applications. Manuscript, 2001.
	20	Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
	21	N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1:194--197, 1982.

CITED BY 17

	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Jie Gao , Michael Langberg , Leonard J. Schulman, Analysis of incomplete data and an intrinsic-dimension Helly theorem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.464-473, January 22-26, 2006, Miami, Florida
	Joachim Giesen , Uli Wagner, Shape dimension and intrinsic metric from samples of manifolds with high co-dimension, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Sariel Har-Peled , Kasturi Varadarajan, High-dimensional shape fitting in linear time, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Kenneth L. Clarkson, Subgradient and sampling algorithms for l1 regression, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida
	Mihai Bădoiu , Kenneth L. Clarkson, Optimal core-sets for balls, Computational Geometry: Theory and Applications, v.40 n.1, p.14-22, May, 2008
	Timothy M. Chan, Dynamic coresets, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Gereon Frahling , Christian Sohler, A fast k-means implementation using coresets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Dan Feldman , Amos Fiat , Micha Sharir , Danny Segev, Bi-criteria linear-time approximations for generalized k-mean/median/center, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Amit Deshpande , Kasturi Varadarajan, Sampling-based dimension reduction for subspace approximation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Nariankadu D. Shyamalkumar , Kasturi Varadarajan, Efficient subspace approximation algorithms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.532-540, January 07-09, 2007, New Orleans, Louisiana
	Mikhail Belkin , Jian Sun , Yusu Wang, Constructing Laplace operator from point clouds in R^d, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1031-1040, January 04-06, 2009, New York, New York
	Dan Feldman , Amos Fiat , Haim Kaplan , Kobbi Nissim, Private coresets, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Chuanjiang Luo , Jian Sun , Yusu Wang, Integral estimation from point cloud in d-dimensional space: a geometric view, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark