Math @ Duke

Publications [#243801] of Mauro Maggioni
Papers Published
 Mahoney, MW; Maggioni, M; Drineas, P, TensorCUR decompositions for tensorbased data,
Siam Journal on Matrix Analysis and Applications, vol. 30 no. 3
(December, 2008),
pp. 957987, Society for Industrial & Applied Mathematics (SIAM), ISSN 08954798 [doi]
(last updated on 2019/02/16)
Abstract: Motivated by numerous applications in which the data may be modeled by a variable subscripted by three or more indices, we develop a tensorbased extension of the matrix CUR decomposition. The tensorCUR 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 tensorCUR 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 + l)tensor, i.e., an m × n × 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 × n matrices as "slabs" and each of the mn different pvectors as "fibers." In this case, the tensorCUR algorithm computes an approximation to the data tensor A that is of the form CWR., where C is an m × n × c tensor consisting of a small number c of the slabs, R is an r × p matrix consisting of a small number r of the fibers, and U is an appropriately defined and easily computed c × r encoding matrix. Both C and R may be chosen by randomly sampling either slabs or fibers according to a judiciously chosen and datadependent probability distribution, and both c and r depend on a rank parameter k, an error parameter ε, and a failure probability δ. 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 tensorCUR 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 tensorCUR decomposition is used to reconstruct missing entries in a userproductproduct 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 productproduct comparisons from a new user. © 2008 Society for Industrial and Applied Mathematics.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

