Matrix approximation and projective clustering via volume sampling

ABSTRACT

Frieze et al. [17] proved that a small sample of rows of a given matrix A contains a low-rank approximation D that minimizes ||A - D||F to within small additive error, and the sampling can be done efficiently using just two passes over the matrix [12]. In this paper, we generalize this result in two ways. First, we prove that the additive error drops exponentially by iterating the sampling in an adaptive manner. Using this result, we give a pass-efficient algorithm for computing low-rank approximation with reduced additive error. Our second result is that using a natural distribution on subsets of rows (called volume sampling), there exists a subset of k rows whose span contains a factor (k + 1) relative approximation and a subset of k + k(k + 1)/ε rows whose span contains a 1+ε relative approximation. The existence of such a small certificate for multiplicative low-rank approximation leads to a PTAS for the following projective clustering problem: Given a set of points P in R^d, and integers k, j, find a set of j subspaces F1, . . ., Fj, each of dimension at most k, that minimize Σp∈Pmini d(p, Fi)².

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Pankaj K. Agarwal , Cecilia Magdalena Procopiuc , Kasturi R. Varadarajan, Approximation Algorithms for k-Line Center, Proceedings of the 10th Annual European Symposium on Algorithms, p.54-63, September 17-21, 2002
• 3: P. Agarwal, S. Har-Peled, K. Varadajan, Geometric approximations via coresets. Manuscript, 2004. http://valis.cs.uiuc.edu/~sariel/papers/04/survey/.
• 4: Pankaj K. Agarwal , Nabil H. Mustafa, k-means projective clustering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055581]
• 5: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 6: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 7: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 8: M. Artin. Algebra, Prentice-Hall, 1991.
• 9: 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]
• 10: Ziv Bar-Yossef, Sampling lower bounds via information theory, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780593]
• 11: W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780550]
• 12: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 13: Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: P. Drineas, R. Kannan, M. Maloney, Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix. Yale University Technical Report, YALEU/DCS/TR-1270, 2004.
• 15: M. Effros, L. J. Schulman, Deterministic clustering with data nets, ECCC TR04--050, 2004.
• 16: J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang, On graph problems in a semi-streaming model. Proceedings of the 31st ICALP, 2004.
• 17: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast monte-carlo algorithms for finding low-rank approximations, Journal of the ACM (JACM), v.51 n.6, p.1025-1041, November 2004 [doi>10.1145/1039488.1039494]
• 18: G. Golub, C. Van Loan, Matrix Computations. John Hopkins University Press, third edition, 1996.
• 19: S. A. Goreinov, E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices Contemporary Mathematics, Vol. 280 (2001), 47--51.
• 20: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 21: 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 [doi>10.1145/1007352.1007400]
• 22: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 23: M. Henzinger, P. Raghavan, S. Rajagopalan, Computing on data streams. Technical Note 1998--011, Digital Systems Research Center, Palo Alto, CA, May 1998.
• 24: David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007438]
• 25: Amit Kumar , Yogish Sabharwal , Sandeep Sen, A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 26: J. Matoušek, On approximate geometric k-clustering. Discrete and Computational Geometry, 61--84, 2000.
• 27: N. Megiddo, A. Tamir, On the complexity of locating linear facilities in the plane. Operations Research Letters, 1 (1982), 194--197.
• 28: Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002 [doi>10.1145/506147.506149]
• 29: Cecilia M. Procopiuc , Michael Jones , Pankaj K. Agarwal , T. M. Murali, A Monte Carlo algorithm for fast projective clustering, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564739]
• 30: L. Rademacher, S. Vempala, G. Wang, Matrix approximation and projective clustering via iterative sampling. MIT-LCS-TR-983, 2005.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Theory