Lemma 2 — for τ ∈ (0, 2/λmax(AᵀA)) the gradient step h = I − τg is nonexpansive, with equality iff h(X) − h(X′) = X − X′
ProvedMaGoldfarbFPC.Convergence.lemma2nonexpansivep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient
Let be linear with matrix , i.e. , let , and let . Let and . Then for all
and if and only if .
Together with Lemma 1 it makes the iteration map non-expansive, with a usable description of when distances are preserved.
Formalization Note , and the range is the predicate StepRange τ Aop: and , which for is as on paper. "Let " in the paper fixes notation for the matrix of ; it is not a hypothesis. The statement holds for every .
Preamble
import Mathlib import Definitions.Def_MaGoldfarbFPC_Convergence_Basic
Formal statement
namespace MaGoldfarbFPC.Convergence
open CaiCandesShen.Convergence
/-- Lemma 2, p. 11: for `τ ∈ (0, 2/λ_max(AᵀA))` the operator `h(·) = I(·) − τg(·)` is
non-expansive in the Frobenius norm, and `h(X) − h(X′) = X − X′` if and only if
`‖h(X) − h(X′)‖_F = ‖X − X′‖_F`. -/
theorem lemma2 {m n p : ℕ} (Aop : Fin p → Mat m n) (b : Fin p → ℝ) (τ : ℝ)
(hτ : StepRange τ Aop) (X X' : Mat m n) :
frobNorm (h τ Aop b X - h τ Aop b X') ≤ frobNorm (X - X') ∧
(h τ Aop b X - h τ Aop b X' = X - X' ↔
frobNorm (h τ Aop b X - h τ Aop b X') = frobNorm (X - X')) := by sorry
end MaGoldfarbFPC.Convergence
Source
Ma, Goldfarb and Chen, Fixed point and Bregman iterative methods for matrix rank minimization, arXiv:0905.1643v2, p. 11, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.