Tensor theta norms and low rank recovery

Holger Rauhut, Zeljka Stojanac

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

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