Tensor denoising and completion based on ordinal observations

Abstract

Higher-order tensors arise frequently in applications such as neuroimaging, recommendation system, social network analysis, and psychological studies. We consider the problem of low-rank tensor estimation from possibly incomplete, ordinal-valued observations. Two related problems are studied, one on tensor denoising and the other on tensor completion. We propose a multi-linear cumulative link model, develop a rank-constrained M-estimator, and obtain theoretical accuracy guarantees. Our mean squared error bound enjoys a faster convergence rate than previous results, and we show that the proposed estimator is minimax optimal under the class of low-rank models. Furthermore, the procedure developed serves as an efficient completion method which guarantees consistent recovery of an order-$K$ $(d,\dots ,d)$-dimensional low-rank tensor using only $\tilde{\mathcal{O}}(Kd)$ noisy, quantized observations. We demonstrate the outperformance of our approach over previous methods on the tasks of clustering and collaborative filtering.

arXiv comment35 pages, 6 figures

References in corpus (9)

• Tensor Regression with Applications in Neuroimaging Data Analysis
• A modern maximum-likelihood theory for high-dimensional logistic regression
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Generalized Canonical Polyadic Tensor Decomposition
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Learning tensors from partial binary measurements
• Multiway clustering via tensor block models
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)

Cited by in corpus (2)

• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Beyond the Signs: Nonparametric Tensor Completion via Sign Series