Motivated by combinatorial regression problems, which we interpret as low rank tensor completion, we study the case of noisy tensor completion for positive tensors. Existing approaches to low rank tensor completion leverage matrix structure within tensors, because this converts the problem into the well-understood low rank matrix completion problem; however, there is currently a significant gap between the best rates achievable using convex reformulations as matrix completion with the best rates achievable using an NP-hard formulation.
Given this mismatch, we propose an alternative approach in which we identify low rank tensor structures that are amenable to both efficient computation and result in estimators with good statistical properties. Focusing on positive tensors, we choose a risk function that enables polynomial time computation and leads to risk consistency. In contrast to soft-thresholding, such as that achieved by nuclear-norm minimization, we use a hard-thresholding approach to identify the low rank structure in the tensor. Numerical examples show that our estimator is competitive with existing approaches to tensor completion.
Anil Aswani is currently an Assistant Professor in IEOR at UC Berkeley. He received a B.S. in Electrical Engineering from the University of Michigan-Ann Arbor in 2005, an M.S. in Electrical Engineering and Computer Sciences (EECS) from UC Berkeley in 2007, and a Ph.D. in EECS with a Designated Emphasis in Computational and Genomic Biology from UC Berkeley in 2010. He won the Leon O. Chua award in 2012 from Berkeley for outstanding achievement in an area of nonlinear science.