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. [ .pdf ] |
| [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. Badoiu, 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. [ .pdf ] |
| [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] |
S. A. Goreinov and E. E. Tyrtyshnikov: The maximal-volume concept in
approximation by low-rank matrices.
Contemporary Mathematics, 280:47-51, 2001. |
| [21] |
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]. |
| [22] |
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]. |
| [23] |
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]. |
| [24] |
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. |
| [25] |
D. Kempe and F. McSherry: A decentralized algorithm for spectral
analysis.
In Proc. 36th STOC., pp. 561-568. ACM Press, 2004.
[STOC:1007352.1007438]. |
| [26] |
J. Kuczynski and H. Wozniakowski: 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]. |
| [27] |
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]. |
| [28] |
J. Matoušek: On approximate geometric k-clustering.
Discrete and Computational Geometry, 24:61-84, 2000.
[Springer:xawxbau59gtjtvv6]. |
| [29] |
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]. |
| [30] |
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]. |
| [31] |
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]. |
| [32] |
L. Rademacher, S. Vempala, and G. Wang: Matrix approximation and
projective clustering.
Technical Report 2005-018, MIT CSAIL, 2005. |
| [33] |
T. Sarlós: Improved approximation algorithms for large matrices via
random projection.
In Proc. 47th FOCS, pp. 143-152. IEEE Computer Society Press,
2006. [ .pdf ] |
This file has been generated by bibtex2html 1.81.