Tensor nuclear norm minimization with linear constraints
Abstract
We study the tensor nuclear norm minimization with general linear constraints, a fundamental model for low-rank tensor optimization that includes many practical applications in computer vision, recommendation systems, revenue management, transportation research. Although the tensor nuclear norm is a convex surrogate for the tensor rank, optimizing it remains computationally challenging because evaluating the nuclear norm itself is NP-hard. We propose a semidefinite programming framework that exposes a finite structure hidden in this problem, even though it appears to possess infinitely many constraints. In particular, we show that the tensor nuclear norm admits an exact SDP representation supported by a finite number of points on the unit sphere. Based on this representation, we develop two complementary solution approaches. The first replaces the unknown support set by a finite sphere discretization which yields a solution with a provable worst-case approximation guarantee. The second selects spherical points adaptively, returns an exact optimum upon finite termination, and otherwise converges asymptotically to an optimal solution. Numerical experiments on synthetic tensor completion instances and real highway traffic data demonstrate that the adaptive method achieves competitive, and often substantially improved, recovery accuracy relative to existing methods.
Related
- Robust low-rank tensor completion via factorized weighted tensor schatten-p norm minimization
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
- An Ω(T3/4) lower bound for projection-free online learning with linear minimization oracles
- Quaternion Gaussian Probes for Tensor Frobenius-Norm Estimation
BibTeX
@misc{chen2026tensor,
title = {{Tensor nuclear norm minimization with linear constraints}},
author = {Renjie Chen and Nanxi Zhang and Bo Jiang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33219},
eprint = {2609.33219},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33219},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tensor nuclear norm minimization with linear constraints
AU - Renjie Chen
AU - Nanxi Zhang
AU - Bo Jiang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33219
UR - https://arxiv.org/abs/2609.33219
AB - We study the tensor nuclear norm minimization with general linear constraints, a fundamental model for low-rank tensor optimization that includes many practical applications in computer vision, recommendation systems, revenue management, transportation research. Although the tensor nuclear norm is a convex surrogate for the tensor rank, optimizing it remains computationally challenging because evaluating the nuclear norm itself is NP-hard. We propose a semidefinite programming framework that exposes a finite structure hidden in this problem, even though it appears to possess infinitely many constraints. In particular, we show that the tensor nuclear norm admits an exact SDP representation supported by a finite number of points on the unit sphere. Based on this representation, we develop two complementary solution approaches. The first replaces the unknown support set by a finite sphere discretization which yields a solution with a provable worst-case approximation guarantee. The second selects spherical points adaptively, returns an exact optimum upon finite termination, and otherwise converges asymptotically to an optimal solution. Numerical experiments on synthetic tensor completion instances and real highway traffic data demonstrate that the adaptive method achieves competitive, and often substantially improved, recovery accuracy relative to existing methods.
ER -