Abstract
We study the extension of compressive sensing and low-rank matrix recovery to higher-order tensors. While matrix recovery via nuclear norm minimization is well-understood, extending these techniques to tensors is complicated by the fact that the tensor nuclear norm is generally NP-hard to compute. In this article, we introduce a family of convex relaxations called theta norms ($\theta_k$-norms), which are computable in polynomial time via semidefinite programming (SDP). These norms are derived from theta bodies, a concept from computational algebraic geometry. We demonstrate that for matrices, these norms reduce to the standard nuclear norm, while for higher-order tensors, they provide a hierarchy of increasingly tight relaxations that converge to the tensor nuclear norm. Numerical experiments suggest that $\theta_1$-norm minimization successfully reconstructs low-rank tensors from incomplete linear measurements.
Introduction
In modern data science, multi-dimensional arrays or tensors are used to represent complex datasets in fields ranging from computer vision to signal processing. A fundamental challenge is recovering a low-rank tensor from a limited set of linear measurements. For 2D matrices, this is efficiently handled by minimizing the nuclear norm—the convex hull of the set of rank-one matrices. However, for tensors of order $d \geq 3$, the nuclear norm is NP-hard to compute, and the very definition of "rank" becomes computationally elusive.
Existing heuristics often rely on "flattening" or matricizing the tensor, which involves rearranging its entries into a matrix and applying standard matrix recovery tools. While computationally feasible, this approach often fails to exploit the inherent multi-way structure of the data, requiring significantly more measurements for successful recovery than theoretically necessary.
Methodology: The Theta Norm Framework
This research bridges the gap between tensor analysis and computational algebraic geometry by introducing theta norms. The approach is based on the following steps:
- Polynomial Ideals and Varieties: The authors define a polynomial ideal $J$ such that its algebraic variety—the set of points where the polynomials vanish—corresponds to the set of rank-one tensors with unit Frobenius norm.
- Theta Bodies: The convex hull of this variety is the unit ball of the tensor nuclear norm. Because computing this hull is intractable, the authors utilize "theta bodies" ($TH_k$), which are a sequence of nested convex sets that provide outer relaxations of the hull.
- The $\theta_k$-Norm: Each theta body defines a corresponding norm. A key theoretical result of the paper is that for order-2 tensors (matrices), the $\theta_k$-norm is identical to the nuclear norm. For higher-order tensors, the sequence of $\theta_k$-norm balls converges asymptotically to the unit tensor nuclear norm ball as $k$ increases.
- SDP Formulation: By computing the Gröbner basis of the ideal, the authors provide a concrete method to formulate the $\theta_k$-norm minimization problem as a semidefinite program (SDP), ensuring it can be solved in polynomial time.
Experimental Validation
The effectiveness of the $\theta_1$-norm was tested using synthetic datasets consisting of third-order tensors.
- Data Generation: Low-rank tensors (rank-1 and rank-2) were created using the outer products of random Gaussian vectors. These tensors were then sampled using random Gaussian measurement maps $\Phi$.
- Recovery Performance: Experiments on tensors of various dimensions (e.g., $5 \times 5 \times 5$ and $4 \times 5 \dots 6$) showed that the $\theta_1$-norm could recover the original data from a small fraction of entries. For instance, a $5 \times 5 \times 5$ rank-1 tensor, which contains 125 entries, was successfully recovered from approximately 43 measurements.
- Scaling: The results suggest that the number of measurements $m$ required for recovery scales linearly with the tensor's degrees of freedom ($O(rn)$), a significant improvement over the $O(rn^2)$ scaling typically required by simple flattening methods.
Discussion and Insights
The introduction of theta norms provides a mathematically rigorous generalization of the matrix nuclear norm to the tensor setting. Unlike heuristic unfolding methods, the $\theta_1$-norm is a distinct mathematical object that preserves the multi-way structure of the tensor.
However, the approach faces practical challenges regarding computational overhead. While the SDPs are polynomial-time solvable, the size of the moment matrices grows rapidly. A $5 \times 5 \times 5$ tensor recovery takes roughly 139 seconds, but increasing the dimensions to $11 \times 11 \times 11$ extends the computation time to nearly an hour using standard solvers.
Conclusion
Tensor theta norms offer a promising new path for low-rank tensor recovery, providing a hierarchy of convex relaxations that are more sophisticated than standard flattening techniques. Future work will focus on developing specialized first-order algorithms to handle the specific structure of these SDPs, which is essential for scaling the method to large-scale, real-world applications. Additionally, establishing theoretical recovery bounds, such as a Restricted Isometry Property for theta norms, remains an open and important research direction.
Summary updated