Theorem 4 — the fixed point iterations (2.1) with τ ∈ (0, 2/λmax(AᵀA)) converge to an optimal solution of (1.8)
ProvedMaGoldfarbFPC.Convergence.theorem4Let be linear with matrix (), let , and . Write and let be the matrix shrinkage operator. Let be generated by the fixed point iterations (2.1) from an arbitrary :
Then there is an optimal solution of problem (1.8), , such that
This is the convergence theorem for the fixed point iterations underlying the FPC and FPCA algorithms for nuclear norm regularized matrix rank minimization: the simple two-line scheme of singular value shrinkage after a gradient step reaches an exact minimizer, for every starting point and every step size below .
Formalization Note The step range is StepRange τ Aop (, ; ), written without division so that is not vacuous. is explicit; the paper needs it for . The run is the predicate IsFixedPointRun, with arbitrary and the relation IsShrink. Neither the nonemptiness of nor the boundedness of the iterates is assumed: both are part of what is to be proved. Convergence is in the Frobenius norm, to some optimal chosen after the run.
import Mathlib import Definitions.Def_MaGoldfarbFPC_Convergence_Basic
namespace MaGoldfarbFPC.Convergence
open CaiCandesShen.Convergence Filter Topology
/-- Theorem 4, p. 12: for `μ > 0` and `τ ∈ (0, 2/λ_max(AᵀA))`, every sequence `{X^k}`
generated by the fixed point iterations (2.1) from an arbitrary `X⁰` converges in the
Frobenius norm to some optimal solution `X*` of problem (1.8). -/
theorem theorem4 {m n p : ℕ} (Aop : Fin p → Mat m n) (b : Fin p → ℝ) (μ τ : ℝ)
(hμ : 0 < μ) (hτ : StepRange τ Aop) (X : ℕ → Mat m n)
(hX : IsFixedPointRun μ τ Aop b X) :
∃ Xs : Mat m n, IsOptimal μ Aop b Xs ∧
Tendsto (fun k => frobNorm (X k - Xs)) atTop (𝓝 0) := by sorry
end MaGoldfarbFPC.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.