Abstract
The recovery of low-rank tensors from a limited number of measurements is a fundamental challenge in signal processing and data science. While matrix nuclear norm minimization is a well-established technique for order-2 tensors, the tensor nuclear norm for higher-order tensors is NP-hard to compute. This paper introduces "theta norms" ($\theta_k$-norms), a hierarchy of convex relaxations based on theta bodies from real algebraic geometry. These norms provide a computationally tractable path for low-rank tensor recovery via semidefinite programming (SDP). We demonstrate that $\theta_1$-norm minimization effectively captures multi-dimensional structure and offers a theoretically grounded alternative to standard matricization techniques.
Introduction
In many modern applications, data is naturally represented as multi-dimensional arrays, or tensors. Recovering the underlying low-rank structure of these tensors from incomplete or noisy observations is critical for tasks such as video completion, hyperspectral imaging, and recommendation systems. For matrices, the nuclear norm serves as the tightest convex relaxation of the rank function, leading to guaranteed recovery under certain conditions. However, extending this to tensors of order $d \ge 3$ is non-trivial. The tensor nuclear norm is defined as the dual of the spectral norm, but its computation is NP-hard.
Current practitioners often rely on "flattening" the tensor into a matrix and applying matrix nuclear norm minimization, or using the "sum of nuclear norms" (SNN) across different orientations. These methods frequently fail to exploit the full multi-dimensional correlations, requiring a higher number of measurements for successful recovery. This work by Rauhut and Stojanac proposes a new family of norms, the $\theta_k$-norms, which bridge the gap between theoretical optimality and computational feasibility.
Methodology: Theta Bodies and SDP Relaxations
The authors' approach is rooted in computational algebraic geometry, specifically the concept of theta bodies and Lasserre relaxations.
Ideal Construction and Gröbner Bases
The core idea is to define a polynomial ideal $J$ whose variety corresponds to the set of rank-one tensors with unit Frobenius norm. A significant theoretical contribution of this work is the identification of a reduced Gröbner basis for this ideal. The authors prove that the set of second-order minors of all possible matricizations of a tensor, combined with a Frobenius norm constraint, forms a reduced Gröbner basis under the graded reverse lexicographic (grevlex) ordering. This result is pivotal, as finding Gröbner bases for such ideals is typically computationally prohibitive.
The Hierarchy of Theta Norms
Using this basis, the authors construct a hierarchy of convex bodies known as theta bodies. The $k$-th theta body in this hierarchy induces the $\theta_k$-norm. These norms are defined via sum-of-squares (SOS) polynomials modulo the ideal $J$. Crucially, the $\theta_k$-norm can be explicitly formulated as a Semidefinite Program (SDP), allowing for the use of standard convex optimization solvers.
Experimental Results
The recovery performance of the $\theta_1$-norm was evaluated using synthetic datasets. Low-rank tensors were generated as sums of $r$ random rank-one tensors, and measurements were taken using independent Gaussian random tensors.
Recovery Performance
Numerical experiments demonstrate that $\theta_1$-norm minimization successfully reconstructs low-rank tensors from significantly fewer measurements than the total number of entries. For a tensor of size $n \times n \times n$ and rank $r$, empirical results suggest a recovery threshold of approximately $m \ge 6rn \log(n)$.
Computational Tractability
While the tensor nuclear norm is NP-hard, the $\theta_1$-norm is solvable in polynomial time. For instance, $9 \times 9 \times 9$ tensors were recovered in approximately 5 minutes, and $11 \times 11 \times 11$ tensors in about 50 minutes using the SDPNAL+ solver. The authors also proved that for order-2 tensors (matrices), the $\theta_k$-norms collapse to the standard matrix nuclear norm, confirming that these norms are a natural and mathematically consistent generalization.
Discussion and Future Work
The $\theta_k$-norms offer a tighter relaxation of the tensor structure than the maximum or weighted sum of nuclear norms of unfoldings. However, scalability remains a challenge. The size of the moment matrices in the SDP formulation grows rapidly with tensor dimensions, currently limiting the approach to tensors of relatively small size (e.g., up to $15 \times 15 \times 15$).
Future research directions include the development of specialized first-order methods, such as ADMM, tailored to the specific structure of the theta-basis moment matrices. Additionally, providing formal theoretical bounds, such as a Restricted Isometry Property (RIP) for theta norms, would further solidify the mathematical foundation of this promising recovery framework.
Summary updated