Tensor Completion via Integer Optimization
The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation error. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate. Our approach formulates tensor completion as a convex optimization problem constrained using a gauge-based tensor norm, which is defined in a way that allows the use of integer linear optimization to solve linear separation problems over the unit-ball in this new norm. Adaptations based on this insight are incorporated into a Frank-Wolfe variant to build our algorithm. We show our algorithm scales-well using numerical experiments on tensors with up to ten million entries.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonnegative Tensor Completion via Integer Optimization
Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for…
Matrix CompletionAccelerated Nonnegative Tensor Completion via Integer Programming
The problem of tensor completion has applications in healthcare, computer vision, and other domains. However, past approaches to tensor completion have faced a tension in that they either have polynomial-time computation…
High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format
Tensor train (TT) decomposition has drawn people's attention due to its powerful representation ability and performance stability in high-order tensors. In this paper, we propose a novel approach to recover the missing e…
Vocal Bursts Intensity PredictionHigh-order Tensor Completion for Data Recovery via Sparse Tensor-train Optimization
In this paper, we aim at the problem of tensor data completion. Tensor-train decomposition is adopted because of its powerful representation ability and linear scalability to tensor order. We propose an algorithm named S…
Vocal Bursts Intensity PredictionSimultaneous Tensor Completion and Denoising by Noise Inequality Constrained Convex Optimization
Tensor completion is a technique of filling missing elements of the incomplete data tensors. It being actively studied based on the convex optimization scheme such as nuclear-norm minimization. When given data tensors in…
DenoisingMissing ElementsRetrieval