TENSOR-CUR DECOMPOSITIONS FOR TENSOR-BASED DATA

摘要

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 from 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 a natural interpretation in terms of the processes generating the data. Assume the data may be modeled as a (2+1)-tensor, i.e., an m x n x p tensor A in which the first two modes are similar and the third is qualitatively different. We refer to each of the p different m x n matrices as "slabs" and each of the mn different p-vectors as "fibers." In this case, the tensor-CUR algorithm computes an approximation to the data tensor A that is of the form CUR, where C is an m x n x c tensor consisting of a small number c of the slabs, 12 is an r x p matrix consisting of a small number r of the fibers, and U is an appropriately defined and easily computed c x r encoding matrix. Both C and R may be chosen by randomly sampling either slabs or fibers according to a judiciously chosen and data-dependent probability distribution, and both c and r depend on a rank parameter k, an error parameter e, and a failure probability 6. Under appropriate assumptions, provable bounds on the Frobenius norm of the error tensor A _ CUR are obtained. 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.