Proposition 6.10 (He–Li–Zhang) — max over u, v of Σ (uᵀA_k v)² equals max over v of Σ (vᵀA_k v)² for symmetric A_k
ProvedTensorNP.SpectralNorm.proposition_6_10matrix-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-optimizationspectral-norm
Let be symmetric matrices. Then
The proposition, embedded in a proof of He, Li and Zhang (2010), lets the bilinear maximization produced by Cauchy–Schwarz in Lemma 6.11 be replaced by the quadratic maximization .
Formalization Note The two maxima are written as sSup of the sets of attained values over the unit spheres; both sets are compact, so the suprema are maxima when (for both sets are empty and both sides are ). Symmetry is Mathlib's Matrix.IsSymm. The paper's printed proof claims that is the 4-linear form of a symmetric 4-tensor, which is not literally true (it is not symmetric under ); the proposition itself is true, and only the statement is posed here.
Preamble
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor
Formal statement
namespace TensorNP.SpectralNorm
open Matrix
/-- **Proposition 6.10 (He–Li–Zhang).** For symmetric real matrices `A_1, …, A_m ∈ ℝ^{n×n}`,
`max_{‖u‖₂=‖v‖₂=1} Σ_k (uᵀA_k v)² = max_{‖v‖₂=1} Σ_k (vᵀA_k v)²` (25). -/
theorem proposition_6_10 {m n : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ)
(hA : ∀ k, (A k).IsSymm) :
sSup {t : ℝ | ∃ u v : Fin n → ℝ, l2norm u = 1 ∧ l2norm v = 1 ∧
t = ∑ k, (u ⬝ᵥ (A k *ᵥ v)) ^ 2} =
sSup {t : ℝ | ∃ v : Fin n → ℝ, l2norm v = 1 ∧ t = ∑ k, (v ⬝ᵥ (A k *ᵥ v)) ^ 2} := 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:23, Proposition 6.10 (He–Li–Zhang 2010), (25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.