CUR matrix decompositions for improved data analysis Export

@article{citeulike:3917252, abstract = {10.1073/pnas.0803205106 Principal components analysis and, more generally, the Singular Value Decomposition are fundamental data analysis tools that express a data matrix in terms of a sequence of orthogonal or uncorrelated vectors of decreasing importance. Unfortunately, being linear combinations of up to all the data points, these vectors are notoriously difficult to interpret in terms of the data and processes generating the data. In this article, we develop CUR matrix decompositions for improved data analysis. CUR decompositions are low-rank matrix decompositions that are explicitly expressed in terms of a small number of actual columns and/or actual rows of the data matrix. Because they are constructed from actual data elements, CUR decompositions are interpretable by practitioners of the field from which the data are drawn (to the extent that the original data are). We present an algorithm that preferentially chooses columns and rows that exhibit high ” statistical leverage” and, thus, in a very precise statistical sense, exert a disproportionately large ” influence” on the best low-rank fit of the data matrix. By selecting columns and rows in this manner, we obtain improved relative-error and constant-factor approximation guarantees in worst-case analysis, as opposed to the much coarser additive-error guarantees of prior work. In addition, since the construction involves computing quantities with a natural and widely studied statistical interpretation, we can leverage ideas from diagnostic regression analysis to employ these matrix decompositions for exploratory data analysis.}, author = {Mahoney, Michael W. and Drineas, Petros}, citeulike-article-id = {3917252}, citeulike-linkout-0 = {http://dx.doi.org/10.1073/pnas.0803205106}, citeulike-linkout-1 = {http://www.pnas.org/content/106/3/697.abstract}, citeulike-linkout-2 = {http://www.pnas.org/content/106/3/697.full.pdf}, citeulike-linkout-3 = {http://view.ncbi.nlm.nih.gov/pubmed/19139392}, citeulike-linkout-4 = {http://www.hubmed.org/display.cgi?uids=19139392}, day = {20}, doi = {10.1073/pnas.0803205106}, journal = {Proceedings of the National Academy of Sciences}, keywords = {approximation, decomposition, matrix, onur2009, svd}, month = {January}, number = {3}, pages = {697--702}, posted-at = {2009-06-04 18:48:23}, priority = {2}, title = {CUR matrix decompositions for improved data analysis}, url = {http://dx.doi.org/10.1073/pnas.0803205106}, volume = {106}, year = {2009} }

TY - JOUR ID - citeulike:3917252 L3 - citeulike-article-id:3917252 N2 - 10.1073/pnas.0803205106 Principal components analysis and, more generally, the Singular Value Decomposition are fundamental data analysis tools that express a data matrix in terms of a sequence of orthogonal or uncorrelated vectors of decreasing importance. Unfortunately, being linear combinations of up to all the data points, these vectors are notoriously difficult to interpret in terms of the data and processes generating the data. In this article, we develop CUR matrix decompositions for improved data analysis. CUR decompositions are low-rank matrix decompositions that are explicitly expressed in terms of a small number of actual columns and/or actual rows of the data matrix. Because they are constructed from actual data elements, CUR decompositions are interpretable by practitioners of the field from which the data are drawn (to the extent that the original data are). We present an algorithm that preferentially chooses columns and rows that exhibit high “statistical leverage” and, thus, in a very precise statistical sense, exert a disproportionately large “influence” on the best low-rank fit of the data matrix. By selecting columns and rows in this manner, we obtain improved relative-error and constant-factor approximation guarantees in worst-case analysis, as opposed to the much coarser additive-error guarantees of prior work. In addition, since the construction involves computing quantities with a natural and widely studied statistical interpretation, we can leverage ideas from diagnostic regression analysis to employ these matrix decompositions for exploratory data analysis. IS - 3 JF - Proceedings of the National Academy of Sciences EP - 702 TI - CUR matrix decompositions for improved data analysis VL - 106 SP - 697 KW - approximation KW - decomposition KW - matrix KW - onur2009 KW - svd AU - Mahoney, Michael AU - Drineas, Petros PY - 2009/01/20/ UR - http://dx.doi.org/10.1073/pnas.0803205106 ER -