Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard

Technical Summary: Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard

Problem Formulation
The paper investigates the computational complexity of the Tensor Spectral Threshold problem. While the existence of a maximizer for the tensor spectral norm is trivial due to the compactness of the feasible domain (the product of unit spheres), the decision problem regarding the value of the norm is non-trivial. Specifically, given a tensor $T$ and a rational scalar $\alpha$, the problem asks whether the spectral norm $\|T\|_{op}$ exceeds $\alpha$.

For symmetric tensors of order $d$, this is equivalent to determining if there exists a unit vector $x$ such that $|T(x, \dots, x)| \ge \alpha$. In the specific case of order-4 tensors, this reduces to deciding whether a homogeneous quartic polynomial achieves a value of at least $\alpha$ on the unit sphere. The authors argue that this threshold formulation is the correct complexity-theoretic object, as the "attainment" formulation (asking if an optimizer exists) is always a YES-instance.

Methodology and Reduction Chain
The paper establishes that the Tensor Spectral Threshold problem is $\exists\mathbb{R}$-hard through a purely algebraic, polynomial-time reduction chain. The proof avoids optimization-theoretic machinery such as KKT conditions, Lagrangian duality, or variational arguments. Instead, it relies on the structural ability of polynomial forms to encode feasibility constraints. The reduction proceeds in two main stages:

1. From Bounded Quartic Equality to Homogeneous Quadratic Sphere Feasibility (HQSF):

   • Source: The reduction begins with the Bounded Quartic Equality Feasibility (BQ4E) problem, which asks if a degree-4 polynomial $h(x)=0$ has a solution in the hypercube $[-1, 1]^n$. This problem is known to be $\exists\mathbb{R}$-hard.
   • Transformation: The authors transform the bounded quartic instance into a system of homogeneous quadratic equations on the unit sphere.
     • Homogenization: A new variable is introduced to convert the quartic equation into a homogeneous form.
     • Box Encoding: Slack variables are used to encode the box constraints $[-1, 1]^n$ as quadratic equalities ($z_i^2 + s_i^2 - x_0^2 = 0$).
     • Quadratic Lifting: The degree-4 homogenized polynomial is lifted into a system of quadratic equations by introducing new variables representing products of the original variables (e.g., $u_{ab} = v_a v_b$).
   • Normalization: The system is normalized to the unit sphere to exclude the trivial zero solution, resulting in an instance of Homogeneous Quadratic Sphere Feasibility (HQSF).

2. From HQSF to Tensor Spectral Threshold:

   • Target: The HQSF instance consists of finding a unit vector $z$ such that $z^\top Q_i z = 0$ for a set of symmetric matrices $\{Q_i\}$.
   • Construction: The authors construct a specific homogeneous quartic polynomial:
     $$p(z) = B\|z\|^4 - \sum_{i=1}^r (z^\top Q_i z)^2$$
     where $B$ is a constant strictly larger than the sum of the squared Frobenius norms of the matrices $Q_i$.
   • Equivalence:
     • If the quadratic system is feasible (i.e., there exists a $z$ where all $z^\top Q_i z = 0$), then $p(z) = B$.
     • If the system is infeasible, the sum of squares term is strictly positive, forcing $p(z) < B$.
     • Since $p(z)$ is strictly positive on the sphere, maximizing $|p(z)|$ is equivalent to maximizing $p(z)$.
   • Tensorization: By the correspondence between symmetric tensors and homogeneous polynomials, $p(z)$ is represented as a symmetric order-4 tensor $T_p$. The maximum of $|p(z)|$ over the sphere is exactly the spectral norm $\|T_p\|_{sym, op}$. Thus, deciding if $\|T_p\|_{sym, op} \ge B$ is equivalent to deciding the feasibility of the original quadratic system.

Key Contributions

• Correct Decision Formulation: The paper identifies the Tensor Spectral Threshold problem as the appropriate decision formulation for tensor spectral norms, distinguishing it from the trivial attainment problem.
• $\exists\mathbb{R}$-Hardness Proof: It proves that determining if a tensor's spectral norm exceeds a rational threshold is $\exists\mathbb{R}$-hard. This places the problem in the complexity class of deciding the existence of real solutions to polynomial systems, which is distinct from and generally believed to be harder than NP-hardness.
• Algebraic Reduction: The reduction is entirely algebraic and explicit. It does not rely on combinatorial gadgets or discrete encodings often found in NP-hardness proofs, but rather exploits the intrinsic relationship between quadratic systems and quartic forms.
• Robustness: The result is shown to extend to:
  • Non-symmetric tensors (since symmetric tensors are a subset).
  • Higher-order tensors ($d \ge 4$) via constraint-preserving embeddings.
  • Multilinear formulations (via Banach's symmetrization theorem).
  • Equality variants (deciding if $\|T\|_{op} = \alpha$).

Results and Significance
The primary result is that the computational obstruction in tensor spectral norm is not merely a consequence of non-convex optimization or combinatorial search, but is fundamentally rooted in real algebraic feasibility.

• Conceptual Shift: The paper argues that tensor problems should be viewed through the lens of semialgebraic geometry. The hardness arises because quartic forms can naturally encode systems of quadratic equations, and symmetric tensors are simply quartic forms in disguise.
• Implications for Algorithms: The result implies that a polynomial-time algorithm for the exact Tensor Spectral Threshold problem would imply $\exists\mathbb{R} \subseteq P$. Furthermore, it suggests that one should not expect a simple characterization of tractability for general tensor spectral problems, as the exact decision problem is already $\exists\mathbb{R}$-hard.
• Relation to Prior Work: While previous work (e.g., Håstad; Hillar and Lim) established NP-hardness for tensor rank and approximation, this paper refines the understanding by isolating the algebraic nature of the hardness for the spectral norm itself. It complements existing discrete hardness results by establishing hardness at the level of real algebraic feasibility.

Limitations and Scope
The authors explicitly note that they establish $\exists\mathbb{R}$-hardness but do not claim $\exists\mathbb{R}$-completeness, as membership in $\exists\mathbb{R}$ (under a specific encoding) is not addressed. The reduction relies on the quartic structure (order-4), and the analysis is restricted to exact decision problems, not approximation or numerical complexity. The paper does not propose new algorithms or experimental applications, focusing strictly on the theoretical complexity classification.