Tensor theta norms and low rank recovery

Holger Rauhut, Zeljka Stojanac

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

We study extensions of compressive sensing and low rank matrix recovery to the recovery of low rank tensors from incomplete linear information. While the reconstruction of low rank matrices via nuclear norm minimization is rather well-understand by now, almost no theory is available for the extension to higher order tensors due to various theoretical and computational difficulties arising for tensor decompositions. In fact, nuclear norm minimization for matrix recovery is a tractable convex relaxation approach, but the extension of the nuclear norm to tensors is in general NP-hard to compute. In this article, we introduce convex relaxations of the tensor nuclear norm which are computable in polynomial time via semidefinite programming. Our approach is based on theta bodies, a concept from computational algebraic geometry similar to the Lasserre relaxations. We introduce polynomial ideals which are generated by the second order minors corresponding to different matricizations of the tensor (where the tensor entries are treated as variables) such that the nuclear norm ball is the convex hull of the algebraic variety of the ideal. The $k$-th theta body for such an ideal generates a new norm which we call the $\theta_k$-norm. We show that in the matrix case, these norms reduce to the nuclear norm. For tensors of order $d \geq 3$ however, we obtain new norms. The sequence of the corresponding unit-$\theta_k$-norm balls converges asymptotically to the unit tensor nuclear norm ball. By providing the Gr\"obner basis for the ideals, we explicitly give semidefinite programs for the computation of the $\theta_k$-norm and for the minimization of the $\theta_k$-norm under an affine constraint. Numerical experiments for order-3 tensor recovery via $\theta_1$-norm minimization suggest that our approach successfully reconstructs tensors of low rank from incomplete linear (random) measurements.
BibTeX
@article{rauhut2021tensor,
  author = {Holger Rauhut and Zeljka Stojanac},
  title = {{Tensor theta norms and low rank recovery}},
  journal = {Numer. Algorithms},
  year = {2021},
  doi = {10.1007/s11075-020-01029-x},
}
Figure