Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#243801] of Mauro Maggioni

Papers Published

  1. Mahoney, MW; Maggioni, M; Drineas, P, Tensor-CUR decompositions for tensor-based data, Siam Journal on Matrix Analysis and Applications, vol. 30 no. 3 (December, 2008), pp. 957-987, Society for Industrial & Applied Mathematics (SIAM), ISSN 0895-4798 [doi]
    (last updated on 2019/02/16)

    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 + 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 p-vectors as "fibers." In this case, the tensor-CUR 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 data-dependent 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 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. © 2008 Society for Industrial and Applied Mathematics.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320