PaperlayerView exact revision on arXiv

Source-linked AI summary

Nuclear Norm of Higher-Order Tensors

Shmuel Friedland, Lek-Heng Lim

arXiv:1410.6072v3cs.CCquant-ph

TL;DR

The paper investigates the mathematical structure and computational complexity of nuclear norms for higher-order tensors. It proves norm-attaining and symmetric decompositions, establishes base-field dependence and symmetric-norm equivalence, and shows broad NP-hardness alongside tractable special cases.

  • Problem

    Higher-order tensor nuclear norms require characterization of their mathematical properties, field dependence, and computational tractability.

  • Method

    The paper analyzes tensor norm definitions, duality, decompositions, base-field examples, and reductions establishing computational complexity results.

  • Results

    The nuclear norm is attained by finite decompositions, symmetric tensors admit symmetric decompositions, norms depend on the base field, and spectral and nuclear norm computation is NP-hard in broad higher-order settings.

  • Takeaways & Limitations

    Nuclear norms provide well-defined continuous rank-related quantities, but higher-order exact computation is generally intractable and requires approximation or special-case structure.

  • Takeaways & Limitations

    The analysis focuses on finite-dimensional tensor spaces over R or C, and orthogonal decompositions do not generally exist for d ≥ 3.

Abstract

from arXiv · show

We establish several mathematical and computational properties of the nuclear norm for higher-order tensors. We show that like tensor rank, tensor nuclear norm is dependent on the choice of base field --- the value of the nuclear norm of a real 3-tensor depends on whether we regard it as a real 3-tensor or a complex 3-tensor with real entries. We show that every tensor has a nuclear norm attaining decomposition and every symmetric tensor has a symmetric nuclear norm attaining decomposition. There is a corresponding notion of nuclear rank that, unlike tensor rank, is upper semicontinuous. We establish an analogue of Banach's theorem for tensor spectral norm and Comon's conjecture for tensor rank --- for a symmetric tensor, its symmetric nuclear norm always equals its nuclear norm. We show that computing tensor nuclear norm is NP-hard in several sense. Deciding weak membership in the nuclear norm unit ball of 3-tensors is NP-hard, as is finding an $\varepsilon$-approximation of nuclear norm for 3-tensors. In addition, the problem of computing spectral or nuclear norm of a 4-tensor is NP-hard, even if we restrict the 4-tensor to be bi-Hermitian, bisymmetric, positive semidefinite, nonnegative valued, or all of the above. We discuss some simple polynomial-time approximation bounds. As an aside, we show that the nuclear $(p,q)$-norm of a matrix is NP-hard in general but can be computed in polynomial-time if $p=1$, $q = 1$, or $p=q=2$, with closed-form expressions for the nuclear $(1,q)$- and $(p,1)$-norms.

1. Introduction

The paper develops mathematical properties of higher-order tensor nuclear norms and establishes broad computational complexity results, alongside tractable matrix special cases.

  • Mathematical properties: Every tensor has a nuclear norm-attaining decomposition, and nuclear rank is upper semicontinuous unlike tensor rank.The nuclear decomposition uses norm-one rank-one terms whose coefficient l1-norm equals the nuclear norm.
  • Mathematical properties: For symmetric tensors, symmetric nuclear norm equals nuclear norm, and every symmetric tensor has a symmetric nuclear decomposition.This is presented as a nuclear-norm analogue of Banach’s theorem and a continuous analogue of Comon’s conjecture.
  • Base-field dependence: Nuclear and spectral norms of higher-order tensors depend on the base field, so real tensors can have different norms over R and C.The paper gives explicit nuclear and symmetric nuclear decompositions for tensors B and C over both fields.
  • Computational properties: For matrix nuclear (p,q)-norms, computation is polynomial-time when p = 1, q = 1, or p = q = 2, and nuclear (1,q)- and (p,1)-norms have closed forms.The paper contrasts these tractable cases with NP-hardness otherwise.
  • Computational properties: Nuclear norm computation is NP-hard for nuclear p-norms of 2-tensors outside selected cases and for nuclear 2-norms of real tensors of order d ≥ 3.For complex tensors, nuclear 2-norm computation is NP-hard for d ≥ 4; related weak-membership and approximation problems are also hard.

2. Hilbert–Schmidt, spectral, and nuclear norms for higher-order tensors

This section formulates Hilbert–Schmidt, spectral, and nuclear norms for finite-dimensional tensors over R or C, relating the latter two as dual norms.

  • Setup: The paper treats d-tensors as coordinate representations in F^(n1×···×nd), with F equal to R or C and finite-dimensional factor spaces.A coordinate-free tensor-product viewpoint is also noted, but the article adopts the hypermatrix representation.
  • Norms: The Hilbert–Schmidt norm is field-independent, whereas spectral and nuclear norms can differ between real and complex interpretations when d > 2.The Hilbert–Schmidt norm is the Euclidean norm after identifying the tensor space with F^n.
  • Duality: The spectral and nuclear norms are dual: |⟨A, B⟩| ≤ ∥A∥σ∥B∥∗.This duality connects the two norms through the tensor inner product.
  • Rank-one tensors: For a rank-one tensor, the Hilbert–Schmidt, spectral, and nuclear norms all equal the product of the factor norms.For norm-one factors, each of these norms is therefore one.
  • Tensor-product interpretation: The framework corresponds in order two to the injective and projective tensor norms, while the article restricts attention to finite dimensions.Finite-dimensionality avoids complications associated with infinite-dimensional tensor products.

3. Tensor nuclear norm is special

The tensor nuclear norm is a genuine norm with attained decompositions, but extending the construction to coefficient lp-norms for p > 1 collapses the infimum to zero.

  • Interpretation: The nuclear norm is the dual norm of the spectral norm and is tied to tensor rank; for density matrices, unit nuclear norm characterizes multipartite separability.The paper explicitly selects this Grothendieck–Schatten definition rather than flattening-based alternatives.
  • Why the nuclear norm is special: For any p > 1, replacing the coefficient l1-norm by an lp-norm makes the corresponding infimum identically zero.The paper explains this through splitting a rank-one tensor into many identical terms.
  • Why the nuclear norm is special: The construction reproduces the matrix Schatten p-norm only in the order-two setting, because orthonormal factor constraints are unavailable for general higher-order tensors.For d ≥ 3, an orthogonal decomposition does not exist in general by a dimension-count argument.
  • Nuclear norm construction: The nuclear norm is a norm on finite-dimensional tensor spaces, and its defining infimum is always attained.The minimum is realized by a finite decomposition into norm-one rank-one tensors.

4. Nuclear decompositions of tensors

The section establishes nuclear decompositions that attain the nuclear norm, defines nuclear rank, and shows its upper semicontinuity, ensuring best nuclear rank-r approximations exist.

  • Nuclear decompositions: A nuclear decomposition is a finite rank-one decomposition whose coefficient l1-norm attains the tensor nuclear norm.A decomposition can equivalently be certified by a spectral-norm dual tensor satisfying the supporting equalities.
  • Nuclear rank: Nuclear rank is the minimum number of extreme-point terms in a nuclear decomposition attaining the norm.For tensor nuclear norm over R, the extreme points are unit rank-one tensors, and nuclear rank decompositions can be written with ordered nonnegative coefficients.
  • Nuclear decompositions: Every orthogonally decomposable tensor has an orthogonal decomposition that is also a nuclear decomposition.For such tensors, the nuclear norm equals the sum of the decomposition coefficients.
  • Nuclear rank: Unlike tensor rank, nuclear rank is upper semicontinuous when the extreme-point set of the unit ball is compact.A convergent sequence with nuclear rank at most r has a limit with nuclear rank at most r.
  • Existence results: Every tensor has a nuclear norm-attaining decomposition, and every best nuclear rank-r approximation problem over R has a solution.The latter follows because the set of tensors with nuclear rank at most r is closed.

5. Analogue of Comon’s conjecture and Banach’s theorem for nuclear norm

For symmetric tensors, the symmetric nuclear norm equals the unrestricted nuclear norm over both real and complex fields, yielding symmetric norm-attaining decompositions.

  • Main theorem: The paper proves the nuclear-norm analogue of Banach’s theorem over both R and C.For symmetric tensors, restricting spectral or nuclear decompositions to symmetric rank-one terms does not change the relevant nuclear norm.
  • Real case: The real symmetric nuclear norm is characterized by decompositions into signed symmetric rank-one tensors.The infimum over such decompositions is attained, and the corresponding norm agrees with the unrestricted nuclear norm.
  • Symmetric decompositions: Every symmetric tensor has a symmetric nuclear decomposition attaining its nuclear norm.The decomposition uses symmetric rank-one terms and is attained rather than merely approached.
  • Extensions: The same result extends to partially symmetric tensors, with signs unnecessary except over R when all symmetry orders are even.The extension uses the corresponding analogue of Banach’s theorem for partially symmetric tensors.

6. Base field dependence

Tensor spectral and nuclear norms can depend on whether real entries are treated over R or C, and the section gives explicit low-dimensional examples demonstrating this dependence.

  • Base-field dependence: For tensor order d ≥3, nuclear and spectral norms can depend on the choice of base field.This parallels the known base-field dependence of tensor rank.
  • Examples: A tensor can have lower complex tensor rank than real tensor rank, with rank_C(A) = 2 < 3 = rank_R(A).The same examples motivate examining field dependence for spectral and nuclear norms.
  • Examples: The paper provides explicit nuclear and symmetric nuclear decompositions for real 2×2×2 tensors viewed over R and C.The examples include tensors B and C and their field-specific decompositions.
  • Examples: For the constructed tensor C, the complex nuclear norm is ∥C∥∗,C = 3/2.The value follows from a symmetric nuclear decomposition over C.
  • Absolute-value comparison: The nuclear-norm inequality ∥A∥∗,C ≤ ∥|A|∥∗,C holds in some special cases but is false in general.The paper contrasts this with the corresponding spectral-norm inequality and uses an explicit tensor example.

7. Nuclear (p, q)-norm of a matrix

The matrix nuclear (p,q)-norm is characterized through duality with the operator (p,q)-norm, yielding hardness results, tractable boundary cases, and closed-form formulas.

  • Duality: The dual of the operator (p,q)-norm is the nuclear (q∗, p)-norm.This identifies the nuclear norm through the convex hull of rank-one matrices with normalized factors.
  • Complexity: The nuclear (p,q)-norm is NP-hard in several parameter regimes, including p∗ < q and p=q outside p ∈ {1,2,∞}.These results follow from polynomial-time interreducibility of norms and their duals.
  • Closed forms: Nuclear (1,p)-norms and (p,1)-norms have closed-form expressions.These formulas are obtained as dual consequences of closed-form operator (1,p)- and (p,∞)-norms.
  • Base fields: For real matrices, nuclear (p,q)-norm values agree with complex-field values for all matrices exactly when q ≤ p∗.Outside this condition, the real and complex norm values can differ.

8. Tensor nuclear norm is NP-hard

The paper establishes broad NP-hardness results for tensor spectral and nuclear norms, including approximation and weak-membership problems. Hardness persists over both real and complex fields and under strong structural restrictions on 4-tensors.

  • NP-hardness of the 3-tensor nuclear norm follows from polynomial-time interreducibility between a norm and its dual, together with spectral-norm hardness.
  • The spectral and nuclear norms of d-tensors over R are NP-hard for every d ≥3.
  • Weak membership in both spectral- and nuclear-norm unit balls is NP-hard for restricted 4-tensors over R and C.
  • The 4-tensor hardness construction remains valid when tensors are bi-Hermitian, bisymmetric, bi-positive semidefinite, and nonnegative-valued.
  • Graph clique reductions show that spectral norms of constructed 4-tensors are NP-hard over both R and C and cannot be approximated to arbitrary accuracy in polynomial time unless P = NP.
  • The spectral and nuclear norms of d-tensors over C are NP-hard for every d ≥4, extending the restricted 4-tensor results to higher orders.

9. Polynomial-time approximation bounds

The paper develops polynomial-time computable bounds for tensor spectral and nuclear norms. These bounds can depend on multilinear rank rather than only ambient dimension, and extend to higher-order tensors through flattenings.

  • Polynomial-time approximation bounds are introduced because arbitrary-accuracy approximation of spectral and nuclear norms is NP-hard unless P = NP.
  • Flattening maps convert a 3-tensor into matrices along each index, whose ranks define its multilinear rank.
  • The spectral and nuclear norms admit corresponding inequalities because the nuclear norm is the dual norm of the spectral norm.
  • Bounds based on multilinear rank provide polynomial-time computable estimates that depend on a tensor’s intrinsic dimension rather than ambient dimension.
  • The flattening-based approach extends the polynomial-time bounds from 3-tensors to tensors of any order d > 3.
Loading 1410.6072v3…