Tensor-CUR decompositions for tensor-based data

ABSTRACT

Motivated by numerous applications in which the data may be modeled by a variable subscripted by three or more indices, we develop a tensor-based extension of the matrix CUR decomposition. The tensor-CUR decomposition is most relevant as a data analysis tool when the data consist of one mode that is qualitatively different than the others. In this case, the tensor-CUR decomposition approximately expresses the original data tensor in terms of a basis consisting of underlying subtensors that are actual data elements and thus that have natural interpretation in terms ofthe processes generating the data. In order to demonstrate the general applicability of this tensor decomposition, we apply it to problems in two diverse domains of data analysis: hyperspectral medical image analysis and consumer recommendation system analysis. In the hyperspectral data application, the tensor-CUR decomposition is used to compress the data, and we show that classification quality is not substantially reduced even after substantial data compression. In the recommendation system application, the tensor-CUR decomposition is used to reconstruct missing entries in a user-product-product preference tensor, and we show that high quality recommendations can be made on the basis of a small number of basis users and a small number of product-product comparisons from a new user.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: M. W. Berry, S. A. Pulatova, and G. W. Stewart. Computing sparse reduced-rank approximations to sparse matrices. Technical Report UMIACS TR-2004-32 CMSC TR-4589, University of Maryland, College Park, MD, 2004.
• 4: Daniel Billsus , Michael J. Pazzani, Learning Collaborative Information Filters, Proceedings of the Fifteenth International Conference on Machine Learning, p.46-54, July 24-27, 1998
• 5: J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Annual Conference on Uncertainty in Artificial Intelligence, pages 43--52, 1998.
• 6: J. D. Carroll and J. J. Chang. Analysis of individual differences in multidimensional scaling via an N-way generalization of "Eckart- Young" decomposition. Psychometrika, 35(3):283--319, 1970.
• 7: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 8: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication, SIAM Journal on Computing, v.36 n.1, p.132-157, 2006 [doi>10.1137/S0097539704442684]
• 9: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix, SIAM Journal on Computing, v.36 n.1, p.158-183, 2006 [doi>10.1137/S0097539704442696]
• 10: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition, SIAM Journal on Computing, v.36 n.1, p.184-206, 2006 [doi>10.1137/S0097539704442702]
• 11: Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509922]
• 12: P. Drineas and M. W. Mahoney. A randomized algorithm for a tensor-based generalization of the Singular Value Decomposition. To appear in: Linear Algebra and its Applications.
• 13: P. Drineas and M. W. Mahoney. On the Nyström method for approximating a Gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6:2153--2175, 2005.
• 14: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 15: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 16: G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
• 17: S. A. Goreinov and E. E. Tyrtyshnikov. The maximum-volume concept in approximation by low-rank matrices. Contemporary Mathematics, 280:47--51, 2001.
• 18: S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. A theory of pseudoskeleton approximations. Linear Algebra and Its Applications, 261:1--21, 1997.
• 19: R. A. Harshman and M. E. Lundy. The PARAFAC model for three-way factor analysis and multidimensional scaling. In H. G. Law, C. W. Snyder Jr., J. Hattie, and R. P. McDonald, editors, Research Methods for Multimode Data Analysis, pages 122--215. Praeger, 1984.
• 20: Johan Håstad, Tensor rank is NP-complete, Journal of Algorithms, v.11 n.4, p.644-654, Dec. 1990 [doi>10.1016/0196-6774(90)90014-6]
• 21: R. Jin, L. Si, and C. X. Zhai. Preference-based graphic models for collaborative filtering. In Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, pages 329--336, 2003.
• 22: Rong Jin , Luo Si , ChengXiang Zhai , Jamie Callan, Collaborative filtering with decoupled models for preferences and ratings, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956922]
• 23: Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007439]
• 24: P. M. Kroonenberg and J. De Leeuw. Principal component analysis of three-mode data by means of alternating least squares algorithms. Psychometrika, 45(1):69--97, 1980.
• 25: J. B. Kruskal. Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and Its Applications, 18:95--138, 1977.
• 26: J. B. Kruskal, Rank, decomposition, and uniqueness for 3-way and n-way arrays, Multiway data analysis, North-Holland Publishing Co., Amsterdam, The Netherlands, 1989
• 27: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
• 28: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, A Multilinear Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1253-1278, March – May 2000 [doi>10.1137/S0895479896305696]
• 29: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, On the Best Rank-1 and Rank-(R₁,R₂,. . .,R_N) Approximation of Higher-Order Tensors, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1324-1342, March – May 2000 [doi>10.1137/S0895479898346995]
• 30: D. Leibovici and R. Sabatier. A singular value decomposition of a k-way array for a principal component analysis of multiway data, PTA-k. Linear Algebra and Its Applications, 269:307--329, 1998.
• 31: L.-H. Lim and G. H. Golub. Tensors for numerical multilinear algebra: ranks and basic decompositions. Technical Report 05-02, Stanford University SCCM, Stanford, CA, April 2005.
• 32: Greg Linden , Brent Smith , Jeremy York, Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, v.7 n.1, p.76-80, January 2003 [doi>10.1109/MIC.2003.1167344]
• 33: M. Maggioni, G. L. Davis, F. J. Warner, F. B. Geshwind, A. C. Coppi, R. A. DeVerse,and R. R. Coifman. Algorithms from signal and data processing applied to hyperspectral analysis: Discriminating normal and malignant microarray colon tissue sections using a novel digital mirror device system. Manuscript, 2006.
• 34: M. Maggioni, G. L. Davis, F. J. Warner, F. B. Geshwind, A. C. Coppi, R. A. DeVerse,and R. R. Coifman. Hyperspectral microscopic analysis of normal, benign and carcinoma microarray tissue sections. Manuscript, 2006.
• 35: Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]
• 36: B. Sarwar, G. Karypis, J. Konstan, and J. Riedl. Application of dimensionality reduction in recommender system - a case study. In Proceedings of the WebKDD 2000 Workshop, pages 000--000, 2000.
• 37: G. W. Stewart. Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix. Numerische Mathematik, 83:313--323, 1999.
• 38: G. W. Stewart. Error analysis of the quasi-Gram-Schmidt algorithm. Technical Report UMIACS TR-2004-17 CMSC TR-4572, University of Maryland, College Park, MD, 2004.
• 39: L. R. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279--311, 1966.
• 40: C. K. I. Williams and M. Seeger. Using the Nyström method to speed up kernel machines. In Annual Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, pages 682--688, 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.m MISCELLANEOUS

Additional Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation

Keywords:
CUR decomposition, hyperspectral image analysis, recommendation system analysis, tensor CUR