Kenneth L. Clarkson
ABSTRACT
We design a new distribution over poly(r ε-1) x n matrices S so that for any fixed n x d matrix A of rank r, with probability at least 9/10, SAx2 = (1 pm ε)Ax2 simultaneously for all x ∈ Rd. Such a matrix S is called a subspace embedding. Furthermore, SA can be computed in O(nnz(A)) + ~O(r2ε-2) time, where nnz(A) is the number of non-zero entries of A. This improves over all previous subspace embeddings, which required at least Ω(nd log d) time to achieve this property. We call our matrices S sparse embedding matrices.
Using our sparse embedding matrices, we obtain the fastest known algorithms for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and lp-regression: to output an x' for which Ax'-b2 ≤ (1+ε)minx Ax-b2 for an n x d matrix A and an n x 1 column vector b, we obtain an algorithm running in O(nnz(A)) + ~O(d3ε-2) time, and another in O(nnz(A)log(1/ε)) + ~O(d3log(1/ε)) time. (Here ~O(f) = f ⋅ logO(1)(f).) to obtain a decomposition of an n x n matrix A into a product of an n x k matrix L, a k x k diagonal matrix D, and a n x k matrix W, for which F{A - L D W} ≤ (1+ε)F{A-Ak}, where Ak is the best rank-k approximation, our algorithm runs in O(nnz(A)) + ~O(nk2 ε-4log n + k3ε-5log2n) time. to output an approximation to all leverage scores of an n x d input matrix A simultaneously, with constant relative error, our algorithms run in O(nnz(A) log n) + ~O(r3) time. to output an x' for which Ax'-bp ≤ (1+ε)minx Ax-bp for an n x d matrix A and an n x 1 column vector b, we obtain an algorithm running in O(nnz(A) log n) + poly(r ε-1) time, for any constant 1 ≤ p < ∞. We optimize the polynomial factors in the above stated running times, and show various tradeoffs. Finally, we provide preliminary experimental results which suggest that our algorithms are of interest in practice.
- Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, and Frank McSherry. Web search via hub synthesis. In FOCS, pages 500--509, 2001. Google Scholar
Digital Library
- Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distributions. In COLT, pages 458--469, 2005. Google ScholarDigital Library
- Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approximations. J. ACM, 54(2), 2007. Google ScholarDigital Library
- Sanjeev Arora, Elad Hazan, and Satyen Kale. A fast random sampling algorithm for sparsifying matrices. In APPROX-RANDOM, pages 272--279, 2006. Google ScholarDigital Library
- Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, and Jared Saia. Spectral analysis of data. In STOC, pages 619--626, 2001. Google ScholarDigital Library
- Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theor. Comput. Sci., 312(1):3--15, 2004. Google ScholarDigital Library
- Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. In STOC, pages 549--562, 2012. Google ScholarDigital Library
- K. Clarkson, P. Drineas, Malik Magdon-Ismail, M. Mahoney, Xiangrui Meng, and David P. Woodruff. The fast cauchy transform and faster robust linear regression. In SODA, 2013.Google ScholarCross Ref
- Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In STOC, pages 205--214, 2009. Google ScholarDigital Library
- Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney. Sampling algorithms and coresets for lp regression. SIAM J. Comput., 38(5):2060--2078, 2009. Google ScholarDigital Library
- Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse Johnson-Lindenstrauss transform. In STOC, pages 341--350, 2010. Google ScholarDigital Library
- Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. In SODA, pages 1117--1126, 2006. Google ScholarDigital Library
- Amit Deshpande and Santosh Vempala. Adaptive sampling and fast low-rank matrix approximation. In APPROX-RANDOM, pages 292--303, 2006. Google ScholarDigital Library
- Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay. Clustering large graphs via the singular value decomposition. Machine Learning, 56(1--3):9--33, 2004. Google ScholarDigital Library
- Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM J. Comput., 36(1):132--157, 2006. Google ScholarDigital Library
- Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. SIAM J. Comput., 36(1):158--183, 2006. Google ScholarDigital Library
- Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition. SIAM J. Comput., 36(1):184--206, 2006. Google ScholarDigital Library
- Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. Competitive recommendation systems. In STOC, pages 82--90, 2002. Google ScholarDigital Library
- Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. CoRR, abs/1109.3843, 2011.Google Scholar
- Petros Drineas, Michael Mahoney, Malik Magdon-Ismail, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. In ICML, 2012.Google Scholar
- Petros Drineas and Michael W. Mahoney. Approximating a Gram matrix for improved kernel-based learning. In COLT, pages 323--337, 2005. Google ScholarDigital Library
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for $\ell_2$ regression and applications. In SODA, pages 1127--1136, 2006. Google ScholarDigital Library
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-based methods. In APPROX-RANDOM, pages 316--326, 2006. Google ScholarDigital Library
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-row-based methods. In ESA, pages 304--314, 2006. Google ScholarDigital Library
- Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. CoRR, abs/0710.1435, 2007. Google ScholarDigital Library
- Alan M. Frieze, Ravi Kannan, and Santosh Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. J. ACM, 51(6):1025--1041, 2004. Google ScholarDigital Library
- N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. ArXiv e-prints, September 2009.Google Scholar
- D.L. Hanson and F.T. Wright. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42(3):1079--1083, 1971.Google ScholarCross Ref
- Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss transforms. In SODA, pages 1195--1206, 2012. Google ScholarDigital Library
- Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. Fast moment estimation in data streams in optimal space. In STOC, pages 745--754, 2011.ıfSTOC Google ScholarDigital Library
- Ravindran Kannan, Hadi Salmasian, and Santosh Vempala. The spectral method for general mixture models. SIAM J. Comput., 38(3):1141--1156, 2008. Google ScholarDigital Library
- Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632, 1999. Google ScholarDigital Library
- Avner Magen and Anastasios Zouzias. Low rank matrix-valued Chernoff bounds and approximate matrix multiplication. In SODA, pages 1422--1436, 2011. Google ScholarDigital Library
- Frank McSherry. Spectral partitioning of random graphs. In FOCS, pages 529--537, 2001. Google ScholarDigital Library
- X. Meng and M. W. Mahoney. Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression. ArXiv e-prints, October 2012.Google Scholar
- Gary L. Miller and Richard Peng. Iterative approaches to row sampling. CoRR, abs/1211.2713, 2012.Google Scholar
- Jelani Nelson and Huy L. Nguyen. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. CoRR, abs/1211.1002, 2012.Google Scholar
- Jelani Nelson and David P. Woodruff. Fast Manhattan sketches in data streams. In PODS, pages 99--110, 2010. Google ScholarDigital Library
- Nam H. Nguyen, Thong T. Do, and Trac D. Tran. A fast and efficient algorithm for low-rank approximation of a matrix. In STOC, pages 215--224, 2009. Google ScholarDigital Library
- Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala. Latent semantic indexing: A probabilistic analysis. J. Comput. Syst. Sci., 61(2):217--235, 2000. Google ScholarDigital Library
- Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail, and Petros Drineas. Random projections for support vector machines. CoRR, abs/1211.6085, 2012.Google Scholar
- Benjamin Recht. A simpler approach to matrix completion. CoRR, abs/0910.0651, 2009.Google Scholar
- M. Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 164(1):60--72, 1999.Google ScholarCross Ref
- Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric functional analysis. J. ACM, 54(4), 2007. Google ScholarDigital Library
- Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In FOCS, pages 143--152, 2006. Google ScholarDigital Library
- Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In SODA, pages 615--624, 2004. Google ScholarDigital Library
- Lloyd N. Trefethen and David Bau. Numerical linear algebra. SIAM, 1997.Google Scholar
- Anastasios Zouzias. A matrix hyperbolic cosine algorithm and applications. CoRR, abs/1103.2793, 2011.Google Scholar
- Anastasios Zouzias and Nikolaos M. Freris. Randomized extended Kaczmarz for solving least-squares. CoRR, abs/1205.5770, 2012.Google Scholar
Index Terms
- Low rank approximation and regression in input sparsity time
Recommendations
Low-Rank Approximation and Regression in Input Sparsity Time
We design a new distribution over m × n matrices S so that, for any fixed n × d matrix A of rank r, with probability at least 9/10, ∥SAx∥2 = (1 ± ε)∥Ax∥2 simultaneously for all x ∈ Rd. Here, m is bounded by a polynomial in rε− 1, and the parameter ε ∈ (...
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingLow-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for common linear algebra problems. We show that, given a matrix A ∈ Rn x d with n >> d and a p ∈ [1, 2), with a constant probability, ...
Low-rank PSD approximation in input-sparsity time
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsWe give algorithms for approximation by low-rank positive semidefinite (PSD) matrices. For symmetric input matrix A ∈ ℝn × n, target rank k, and error parameter ε > 0, one algorithm finds with constant probability a PSD matrix Ỹ of rank k such that ||A −...
Comments