Theorem 6.11 — IRLS-M converges to the nuclear norm minimizer under the strong rank null space property
ProvedIRLSM.Convergence.theorem_6_11Consider the IRLS-M algorithm with parameters and , for a surjective linear map and data . Let be a run. Then:
- If satisfies the strong rank null space property of order and , then converges to a matrix of rank at most with , and is the unique nuclear norm minimizer: for every with .
- If , then every subsequence of has a convergent subsequence; every accumulation point of is a minimizer of subject to ; and if this minimizer is unique, the whole sequence converges to it. If in addition satisfies the SRNSP of order with constant , then every accumulation point satisfies, for every with and every ,
- If satisfies the SRNSP of order with constant and some of rank at most satisfies (with ), then .
This is the main result of the paper: IRLS-M recovers low-rank matrices exactly, and approximately low-rank matrices stably, whenever the measurement map has the strong rank null space property.
Formalization Note Matrices are real (, with the paper's standing assumption where objects occur); the measurement map is for measurement matrices , so is and is the trace inner product. The run is the relation IsRun (any minimizer at each step; after a stop; unconstrained). The nonincreasing, nonnegative sequence always converges, and "" in item 3 is . Accumulation points are cluster points of the sequence. In item 3, ranges over the same as in item 2, which its proof uses. The condition is kept literally in ; for it is implied by , part of the SRNSP.
import Mathlib import Definitions.Def_IRLSM_Convergence_Algorithm open HighDimStat.MatrixRank Matrix Filter Topology
namespace IRLSM.Convergence
/-- **Theorem 6.11.** Consider the IRLS-M algorithm with `γ = 1/n` and `K ∈ ℕ`, for a surjective
`S : M_{n×p} → ℝ^m` and data `𝓜`. The iterates `(X^ℓ)` satisfy:
(i) if `S` has the SRNSP of order `K` and `ε_ℓ → 0`, then `X^ℓ` converges to a matrix `X̄` of rank
at most `K` with `S(X̄) = 𝓜`, which is the unique nuclear norm minimizer;
(ii) if `ε_ℓ → ε > 0`, then every subsequence has a convergent subsequence, every accumulation
point is a minimizer of `𝒥_ε` subject to `S(X) = 𝓜`, the whole sequence converges if this
minimizer is unique; and if `S` has the SRNSP of order `K` with constant `η < 1 − 2/(K − 2)`, every
accumulation point `X̄` satisfies `‖X − X̄‖_* ≤ Λ ρ_k(X)_*` for every feasible `X` and every
`k < K − 2η/(1 − η)`;
(iii) under that SRNSP, if some feasible matrix has rank at most `k`, then `ε = 0`.
Fornasier–Rauhut–Ward, arXiv:1010.2471v4, Theorem 6.11, pp. 20–21.
Formalization Notes: real matrices; `S(X)_l = ⟨A_l, X⟩`; `n ≤ p` is the page's standing assumption
(p. 4); the run is `IsRun` (`X 0` free, `ε_j = 0` after a stop). `ε_ℓ` is nonincreasing and
nonnegative, so it always converges; "`lim ε_ℓ = ε`" is `Tendsto ε atTop (𝓝 e)`, and (iii)'s
"`ε = 0`" is `Tendsto ε atTop (𝓝 0)`. Accumulation points are `MapClusterPt`. In (ii)(d) the
page's `X` is `Y` and `X̄` is `Xt`; `Λ` is `Lambda η K k`. In (iii) `k` ranges over the same
`k < K − 2η/(1 − η)` as in (ii), which its proof uses. The condition `η < 1 − 2/(K − 2)` is kept
literally in `ℝ` (for `K ≤ 2` it is implied by `η < 1`, part of the SRNSP). The goal's "unique
nuclear norm minimizer" is the strict inequality `‖X̄‖_* < ‖Y‖_*` for every feasible `Y ≠ X̄`. -/
theorem theorem_6_11 {n p m : ℕ} (A : Fin m → Matrix (Fin n) (Fin p) ℝ) (M : Fin m → ℝ) (K : ℕ)
(X : ℕ → Matrix (Fin n) (Fin p) ℝ) (ε : ℕ → ℝ) (hnp : n ≤ p)
(hS : Function.Surjective (observationOp A)) (hrun : IsRun A M K (1 / (n : ℝ)) X ε) :
-- (i)
((∃ η : ℝ, SRNSP A K η) → Tendsto ε atTop (𝓝 0) →
∃ Xbar : Matrix (Fin n) (Fin p) ℝ, Tendsto X atTop (𝓝 Xbar) ∧ Xbar.rank ≤ K ∧
observationOp A Xbar = M ∧
∀ Y : Matrix (Fin n) (Fin p) ℝ, observationOp A Y = M → Y ≠ Xbar →
nuclearNorm Xbar < nuclearNorm Y) ∧
-- (ii)
(∀ e : ℝ, 0 < e → Tendsto ε atTop (𝓝 e) →
(∀ φ : ℕ → ℕ, StrictMono φ → ∃ ψ : ℕ → ℕ, StrictMono ψ ∧
∃ L : Matrix (Fin n) (Fin p) ℝ, Tendsto (X ∘ φ ∘ ψ) atTop (𝓝 L)) ∧
(∀ Xt : Matrix (Fin n) (Fin p) ℝ, MapClusterPt Xt atTop X →
observationOp A Xt = M ∧
∀ Y : Matrix (Fin n) (Fin p) ℝ, observationOp A Y = M → Jeps e Xt ≤ Jeps e Y) ∧
(∀ Xm : Matrix (Fin n) (Fin p) ℝ,
(observationOp A Xm = M ∧
∀ Y : Matrix (Fin n) (Fin p) ℝ, observationOp A Y = M → Jeps e Xm ≤ Jeps e Y) →
(∀ Z : Matrix (Fin n) (Fin p) ℝ, observationOp A Z = M →
(∀ Y : Matrix (Fin n) (Fin p) ℝ, observationOp A Y = M → Jeps e Z ≤ Jeps e Y) →
Z = Xm) →
Tendsto X atTop (𝓝 Xm)) ∧
(∀ η : ℝ, SRNSP A K η → η < 1 - 2 / ((K : ℝ) - 2) →
∀ Xt : Matrix (Fin n) (Fin p) ℝ, MapClusterPt Xt atTop X →
∀ Y : Matrix (Fin n) (Fin p) ℝ, observationOp A Y = M →
∀ k : ℕ, (k : ℝ) < K - 2 * η / (1 - η) →
nuclearNorm (Y - Xt) ≤ Lambda η K k * rho k Y)) ∧
-- (iii)
(∀ η : ℝ, SRNSP A K η → η < 1 - 2 / ((K : ℝ) - 2) →
∀ k : ℕ, (k : ℝ) < K - 2 * η / (1 - η) →
(∃ X₀ : Matrix (Fin n) (Fin p) ℝ, X₀.rank ≤ k ∧ observationOp A X₀ = M) →
Tendsto ε atTop (𝓝 0)) := by sorry
end IRLSM.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.