Proof of Theorem 6.5 — T_l is the spectral norm and the maximum ℓ²-singular value of the tensor A_l
ProvedTensorNP.SpectralNorm.Tl_max_singular_valuep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1singular-valuespectral-normtensor
Let be a simple graph on vertices with edges enumerated in any order, let be a positive integer, and let be the tensor whose entry is the coefficient of in the multilinear form (26). Regard as a real tensor. Then:
- ;
- is a unit -singular value of ;
- every unit -singular value of satisfies .
In the paper's words, " is just the maximum -singular value of ". This is what turns Lemma 6.11 into statements about the spectral norm and the singular values of an explicit rational tensor.
Formalization Note Singular values are taken with unit singular vectors (see the definition item): without a normalization, every nonzero real number would be a singular value of . is the sSup-based Tval, and is cliqueTensor cast entrywise to .
Preamble
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
namespace TensorNP.SpectralNorm
/-- **Proof of Theorem 6.5, `T_l` is the maximum ℓ²-singular value of `A_l`** (p. 0:24). For a
simple graph `G` on `v ≥ 1` vertices, an enumeration `ε` of its edges and a positive integer
`l`, the tensor `A_l` (read over ℝ) has spectral norm `T_l`, `T_l` is a unit ℓ²-singular value
of `A_l`, and every unit ℓ²-singular value `σ` of `A_l` satisfies `|σ| ≤ T_l`. -/
theorem Tl_max_singular_value {v e : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v))
(ε : Fin e ≃ G.edgeSet) (l : ℕ) (hl : 1 ≤ l) :
specNorm (fun i j k => (cliqueTensor G ε l i j k : ℝ)) = Tval G ε l ∧
IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) (Tval G ε l) ∧
∀ σ : ℝ, IsUnitSingularValue (fun i j k => (cliqueTensor G ε l i j k : ℝ)) σ →
|σ| ≤ Tval G ε l := by sorry
end TensorNP.SpectralNorm
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:24, proof of Theorem 6.5 ("Then T_l is just the maximum ℓ²-singular value of A_l"); p. 0:22, discussion after Definition 6.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.