jmlr jmlr2012 jmlr2012-43 jmlr2012-43-reference knowledge-graph by maker-knowledge-mining

43 jmlr-2012-Fast Approximation of Matrix Coherence and Statistical Leverage


Source: pdf

Author: Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff

Abstract: The statistical leverage scores of a matrix A are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nystr¨ m-based low-rank o matrix approximation as well as in large-scale statistical data analysis applications more generally; moreover, they are of interest since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n × d matrix A, with n ≫ d, and that returns as output relative-error approximations to all n of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of n and d) in O(nd log n) time, as opposed to the O(nd 2 ) time required by the na¨ve algorithm that involves computing an orthogonal basis for the ı range of A. Our analysis may be viewed in terms of computing a relative-error approximation to an underconstrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with n ≈ d, and the extension to streaming environments. Keywords: matrix coherence, statistical leverage, randomized algorithm


reference text

D. Achlioptas. Database-friendly random projections: Johnson-lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687, 2003. N. Ailon and B. Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 557– 563, 2006. N. Ailon and B. Chazelle. The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on Computing, 39(1):302–322, 2009. N. Ailon and E. Liberty. Fast dimension reduction using Rademacher series on dual BCH codes. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1–9, 2008. A. Andoni, R. Krauthgamer, and K. Onak. Streaming algorithms from precision sampling. Technical report, 2010. Preprint: arXiv:1011.1263. H. Avron, P. Maymounkov, and S. Toledo. Blendenpik: Supercharging LAPACK’s least-squares solver. SIAM Journal on Scientific Computing, 32:1217–1236, 2010. C. Bekas, E. Kokiopoulou, and Y. Saad. An estimator for the diagonal of a matrix. Applied Numerical Mathematics, 57:1214–1229, 2007. C. Bekas, A. Curioni, and I. Fedulova. Low cost high performance uncertainty quantification. In Proceedings of the 2nd Workshop on High Performance Computational Finance, page Article No.: 8, 2009. P. Bonacich. Power and centrality: A family of measures. The American Journal of Sociology, 92 (5):1170–1182, 1987. C. Boutsidis, M.W. Mahoney, and P. Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 968–977, 2009. C. Boutsidis, P. Drineas, and M. Magdon-Ismail. Near-optimal column-based matrix reconstruction. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 305–314, 2011a. C. Boutsidis, P. Drineas, and M. Magdon-Ismail. Near-optimal column-based matrix reconstruction. Technical report, 2011b. Preprint: arXiv:1103.0995. E.J. Candes and B. Recht. Exact matrix completion via convex optimization. Technical report, 2008. Preprint: arXiv:0805.4471. 3503 D RINEAS , M AGDON -I SMAIL , M AHONEY AND W OODRUFF S. Chatterjee and A.S. Hadi. Influential observations, high leverage points, and outliers in linear regression. Statistical Science, 1(3):379–393, 1986. S. Chatterjee and A.S. Hadi. Sensitivity Analysis in Linear Regression. John Wiley & Sons, New York, 1988. S. Chatterjee, A.S. Hadi, and B. Price. Regression Analysis by Example. John Wiley & Sons, New York, 2000. A. Dasgupta, R. Kumar, and T. Sarl´ s. A sparse Johnson-Lindenstrauss transform. In Proceedings o of the 42nd Annual ACM Symposium on Theory of Computing, pages 341–350, 2010. P. Drineas, R. Kannan, and M.W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing, 36:132–157, 2006a. P. Drineas, M.W. Mahoney, and S. Muthukrishnan. Sampling algorithms for ℓ2 regression and applications. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1127–1136, 2006b. P. Drineas, M.W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30:844–881, 2008. P. Drineas, J. Lewis, and P. Paschou. Inferring geographic coordinates of origin for Europeans using small panels of ancestry informative markers. PLoS ONE, 5(8):e11892, 2010a. P. Drineas, M.W. Mahoney, S. Muthukrishnan, and T. Sarl´ s. Faster least squares approximation. o Numerische Mathematik, 117(2):219–249, 2010b. S. Ganguly, M. Bansal, and S. Dube. Estimating hybrid frequency moments of data streams. In Proceedings of the 2nd Annual International Workshop on Frontiers in Algorithmics, pages 55– 66, 2008. S. Georgiev and S. Mukherjee, 2011. Unpublished results. (2011). A. Gittens and M. W. Mahoney, 2012. In preparation. (2012). G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1996. N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011. N.J.A. Harvey, J. Nelson, and K. Onak. Sketching and streaming entropy via approximation theory. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 489–498, 2008. D.C. Hoaglin and R.E. Welsch. The hat matrix in regression and ANOVA. The American Statistician, 32(1):17–22, 1978. 3504 FAST A PPROXIMATION OF M ATRIX C OHERENCE AND S TATISTICAL L EVERAGE E. A. Jonckheere, M. Lou, J. Hespanha, and P. Barooah. Effective resistance of Gromov-hyperbolic graphs: Application to asymptotic sensor network problems. In Proceedings of the 46th IEEE Conference on Decision and Control, pages 1453–1458, 2007. M. Magdon-Ismail. Row sampling for matrix algorithms via a non-commutative Bernstein bound. Technical report, 2010. Preprint: arXiv:1008.0587. M. W. Mahoney. Randomized Algorithms for Matrices and Data. Foundations and trends in machine learning. NOW Publishers, Boston, 2011. Also available at: arXiv:1104.5557. M.W. Mahoney and P. Drineas. CUR matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. USA, 106:697–702, 2009. X. Meng, M. A. Saunders, and M. W. Mahoney. LSRN: A parallel iterative solver for strongly overor under-determined systems. Technical report, 2011. Preprint: arXiv:1109.5981. M. Monemizadeh and D. P. Woodruff. 1-pass relative-error l p -sampling with applications. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1143–1160, 2010. S. Muthukrishnan. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science. Now Publishers Inc, Boston, 2005. M.Z. Nashed, editor. Generalized Inverses and Applications. Academic Press, New York, 1976. M.E.J. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27:39–54, 2005. C.H. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent semantic indexing: a probabilistic analysis. Journal of Computer and System Sciences, 61(2):217–235, 2000. P. Paschou, E. Ziv, E.G. Burchard, S. Choudhry, W. Rodriguez-Cintron, M.W. Mahoney, and P. Drineas. PCA-correlated SNPs for structure identification in worldwide human populations. PLoS Genetics, 3:1672–1686, 2007. P. Paschou, J. Lewis, A. Javed, and P. Drineas. Ancestry informative markers for finescale individual assignment to worldwide populations. Journal of Medical Genetics, page doi:10.1136/jmg.2010.078212, 2010. M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th Annual ACM SIGKDD Conference, pages 61–70, 2002. V. Rokhlin and M. Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proc. Natl. Acad. Sci. USA, 105(36):13212–13217, 2008. V. Rokhlin, A. Szlam, and M. Tygert. A randomized algorithm for principal component analysis. SIAM Journal on Matrix Analysis and Applications, 31(3):1100–1124, 2009. T. Sarl´ s. Improved approximation algorithms for large matrices via random projections. In Proo ceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 143– 152, 2006. 3505 D RINEAS , M AGDON -I SMAIL , M AHONEY AND W OODRUFF A. Talwalkar and A. Rostamizadeh. Matrix coherence and the Nystr¨ m method. In Proceedings of o the 26th Conference in Uncertainty in Artificial Intelligence, 2010. P.F. Velleman and R.E. Welsch. Efficient computing of regression diagnostics. The American Statistician, 35(4):234–242, 1981. 3506