Matrix Approximation and Projective Clustering via Volume Sampling

by Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang

Theory of Computing, Volume 2(12), pp. 225-247, 2006

Bibliography with links to cited articles

[1]   D. Achlioptas and F. McSherry: Fast computation of low rank matrix approximations. In Proc. 33rd STOC., pp. 611–618. ACM Press, 2001. [STOC:380752.380858].

[2]   P. Agarwal, S. Har-Peled, and K. Varadarajan: Geometric approximations via coresets. Combinatorial and Computational Geometry - MSRI Publications, 52:1–30, 2005.

[3]   P. Agarwal and N. Mustafa: k-means projective clustering. In Proc. Principles of Database Systems (PODS’04), pp. 155–165. ACM Press, 2004. [PODS:1055558.1055581].

[4]   P. Agarwal, C. Procopiuc, and K. Varadarajan: Approximation algorithms for a k-line center. Algorithmica, 42:221–230, 2005. [Algorithmica:p321725768012505].

[5]   R. Agarwal, J. Gehrke, D. Gunopulos, and P. Raghavan: Automatic subspace clustering of high dimensional data for data mining applications. Data Mining and Knowledge Discovery, 11:5–33, 2005. [Springer:m18077t9134v55n2].

[6]   C. Aggarwal, C. Procopiuc, J. Wolf, P. Yu, and J. Park: Fast algorithms for projected clustering. In Proc. Conf. on Management of Data (SIGMOD’99), pp. 61–72. ACM Press, 1999. [SIGMOD:304182.304188].

[7]   N. Alon, Y. Matias, and M. Szegedy: The space complexity of approximating the frequency moments. J. Computer and System Sciences, 58:137–147, 1999. [JCSS:10.1006/jcss.1997.1545].

[8]   M. Artin: Algebra. Prentice-Hall, 1991.

[9]   Z. Bar-Yossef: Sampling lower bounds via information theory. In Proc. 35th STOC., pp. 335–344. ACM Press, 2003. [STOC:780542.780593].

[10]   M. Bădoiu, S. Har-Peled, and P. Indyk: Approximate clustering via core-sets. In Proc. 34th STOC., pp. 250–257. ACM Press, 2002. [STOC:509907.509947].

[11]   W. Fernandez de la Vega, M. Karpinski, C. Kenyon, and Y. Rabani: Approximation schemes for clustering problems. In Proc. 35th STOC., pp. 50–58. ACM Press, 2003. [STOC:780542.780550].

[12]   A. Deshpande, L. Rademacher, S. Vempala, and G. Wang: Matrix approximation and projective clustering via volume sampling. In Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 1117–1126. SIAM, 2006. [SODA:1109557.1109681].

[13]   A. Deshpande and S. Vempala: Adaptive sampling and fast low-rank matrix approximation. In Proc. 10th Internat. Workshop on Randomization and Computation (RANDOM’06), pp. 292–303. Springer, 2006.

[14]   P. Drineas and R. Kannan: Pass efficient algorithms for approximating large matrices. In Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 223–232. SIAM, 2003. [SODA:644108.644147].

[15]   P. Drineas, R. Kannan, A. Frieze, S. Vempala, and V. Vinay: Clustering large graphs via the singular value decomposition. Machine Learning, 56:9–33, 2004. [ML:u424k6nn6k622788].

[16]   P. Drineas, R. Kannan, and M. Mahoney: Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. SIAM J. on Computing, 36:158–183, 2006. [SICOMP:10.1137/S0097539704442696].

[17]   M. Effros and L. J. Schulman: Rapid near-optimal VQ design with a deterministic data net. In Proc. Int. Symp. on Information Theory, p. 298. IEEE, 2004. [ISIT:10.1109/ISIT.2004.1365336].

[18]   J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang.: On graph problems in a semi-streaming model. Theoretical Computer Science, 348:207–216, 2005. [TCS:10.1016/j.tcs.2005.09.013].

[19]   A. Frieze, R. Kannan, and S. Vempala: Fast Monte Carlo algorithms for finding low-rank approximations. Journal of the ACM, 51:1025–1041, 2004. [JACM:1039488.1039494].

[20]   G. H. Golub and C. F. van Loan: Matrix Computations. Johns Hopkins, third edition, 1996.

[21]   S. A. Goreinov and E. E. Tyrtyshnikov: The maximal-volume concept in approximation by low-rank matrices. Contemporary Mathematics, 280:47–51, 2001.

[22]   S. Guha, N. Koudas, and K. Shim: Approximation and streaming algorithms for histogram construction problems. ACM Transactions on Database Systems, 31:396–438, 2006. [TODS:1132863.1132873].

[23]   S. Har-Peled and S. Mazumdar: On coresets for k-means and k-median clustering. In Proc. 36th STOC., pp. 291–300. ACM Press, 2004. [STOC:1007352.1007400].

[24]   S. Har-Peled and K. Varadarajan: Projective clustering in high dimensions using core-sets. In Proc. 18th Symp. on Comp. Geometry (SOCG), pp. 312–318. ACM Press, 2002. [SOCG:513400.513440].

[25]   M. Henzinger, P. Raghavan, and S. Rajagopalan: Computing on data streams. External Memory Algorithms – DIMACS Series in Discrete Mathematics and Computer Science, 50:107–118, 1999.

[26]   D. Kempe and F. McSherry: A decentralized algorithm for spectral analysis. In Proc. 36th STOC., pp. 561–568. ACM Press, 2004. [STOC:1007352.1007438].

[27]   J. Kuczyński and H. Woźniakowski: Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl., 13:1094–1122, 1992. [SIMAX:10.1137/0613066].

[28]   A. Kumar, Y. Sabharwal, and S. Sen.: A simple linear time (1 + ε)-approximation algorithm for k-means clustering in any dimensions. In Proc. 45th FOCS, pp. 454–462. IEEE Computer Society Press, 2004. [FOCS:10.1109/FOCS.2004.7].

[29]   J. Matoušek: On approximate geometric k-clustering. Discrete and Computational Geometry, 24:61–84, 2000. [Springer:xawxbau59gtjtvv6].

[30]   N. Megiddo and A. Tamir: On the complexity of locating linear facilities in the plane. Operations Research Letters, 13:194–197, 1982. [Elsevier:10.1016/0167-6377(82)90039-6].

[31]   R. Ostrovsky and Y. Rabani: Polynomial time approximation schemes for geometric min-sum median clustering. Journal of the ACM, 49:139–156, 2002. [JACM:506147.506149].

[32]   C. Procopiuc, P. Agarwal, T. Murali, and M. Jones: A Monte Carlo algorithm for fast projective clustering. In Proc. Conf. on Management of Data (SIGMOD’02), pp. 418–427. ACM Press, 2002. [SIGMOD:564691.564739].

[33]   L. Rademacher, S. Vempala, and G. Wang: Matrix approximation and projective clustering. Technical Report 2005–018, MIT CSAIL, 2005.

[34]   T. Sarlós: Improved approximation algorithms for large matrices via random projection. In Proc. 47th FOCS, pp. 143–152. IEEE Computer Society Press, 2006.