Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.11 — IRLS-M converges to the nuclear norm minimizer under the strong rank null space property

Proved
IRLSM.Convergence.theorem_6_11

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

iteratively-reweighted-least-squareslow-rank-recoverynull-space-propertyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the IRLS-M algorithm with parameters γ=1/n\gamma=1/nγ=1/n and K∈NK\in\mathbb NK∈N, for a surjective linear map S:Rn×p→Rm\mathcal S:\mathbb R^{n\times p}\to\mathbb R^mS:Rn×p→Rm and data M∈Rm\mathscr M\in\mathbb R^mM∈Rm. Let (Xℓ,εℓ)(X^\ell,\varepsilon_\ell)(Xℓ,εℓ​) be a run. Then:

  1. If S\mathcal SS satisfies the strong rank null space property of order KKK and lim⁡ℓ→∞εℓ=0\lim_{\ell\to\infty}\varepsilon_\ell=0limℓ→∞​εℓ​=0, then XℓX^\ellXℓ converges to a matrix Xˉ\bar XXˉ of rank at most KKK with S(Xˉ)=M\mathcal S(\bar X)=\mathscr MS(Xˉ)=M, and Xˉ\bar XXˉ is the unique nuclear norm minimizer: ∥Xˉ∥∗<∥Y∥∗\|\bar X\|_*<\|Y\|_*∥Xˉ∥∗​<∥Y∥∗​ for every Y≠XˉY\ne\bar XY=Xˉ with S(Y)=M\mathcal S(Y)=\mathscr MS(Y)=M.
  2. If lim⁡ℓ→∞εℓ=ε>0\lim_{\ell\to\infty}\varepsilon_\ell=\varepsilon>0limℓ→∞​εℓ​=ε>0, then every subsequence of (Xℓ)(X^\ell)(Xℓ) has a convergent subsequence; every accumulation point X~\tilde XX~ of (Xℓ)ℓ≥1(X^\ell)_{\ell\ge1}(Xℓ)ℓ≥1​ is a minimizer of Jε\mathcal J_\varepsilonJε​ subject to S(X)=M\mathcal S(X)=\mathscr MS(X)=M; and if this minimizer is unique, the whole sequence converges to it. If in addition S\mathcal SS satisfies the SRNSP of order KKK with constant η<1−2K−2\eta<1-\frac{2}{K-2}η<1−K−22​, then every accumulation point Xˉ\bar XXˉ satisfies, for every XXX with S(X)=M\mathcal S(X)=\mathscr MS(X)=M and every k<K−2η1−ηk<K-\frac{2\eta}{1-\eta}k<K−1−η2η​,
∥X−Xˉ∥∗≤Λ ρk(X)∗,Λ=4(1+η)2(1−η)2((K−k)(1−η)−2η)+2(1+η)1−η.\|X-\bar X\|_*\le\Lambda\,\rho_k(X)_*,\qquad \Lambda=\frac{4(1+\eta)^2}{(1-\eta)^2\big((K-k)(1-\eta)-2\eta\big)}+\frac{2(1+\eta)}{1-\eta}.∥X−Xˉ∥∗​≤Λρk​(X)∗​,Λ=(1−η)2((K−k)(1−η)−2η)4(1+η)2​+1−η2(1+η)​.
  1. If S\mathcal SS satisfies the SRNSP of order KKK with constant η<1−2K−2\eta<1-\frac{2}{K-2}η<1−K−22​ and some XXX of rank at most kkk satisfies S(X)=M\mathcal S(X)=\mathscr MS(X)=M (with k<K−2η1−ηk<K-\frac{2\eta}{1-\eta}k<K−1−η2η​), then lim⁡ℓεℓ=0\lim_\ell\varepsilon_\ell=0limℓ​εℓ​=0.

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 (n×pn\times pn×p, with the paper's standing assumption n≤pn\le pn≤p where n×nn\times nn×n objects occur); the measurement map is S(X)l=⟨Al,X⟩\mathcal S(X)_l=\langle A_l,X\rangleS(X)l​=⟨Al​,X⟩ for measurement matrices A1,…,AmA_1,\dots,A_mA1​,…,Am​, so S∗\mathcal S^*S∗ is u↦∑lulAlu\mapsto\sum_l u_lA_lu↦∑l​ul​Al​ and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle⟨⋅,⋅⟩ is the trace inner product. The run is the relation IsRun (any minimizer at each step; εj=0\varepsilon_j=0εj​=0 after a stop; X0X^0X0 unconstrained). The nonincreasing, nonnegative sequence εℓ\varepsilon_\ellεℓ​ always converges, and "ε=0\varepsilon=0ε=0" in item 3 is εℓ→0\varepsilon_\ell\to0εℓ​→0. Accumulation points are cluster points of the sequence. In item 3, kkk ranges over the same k<K−2η/(1−η)k<K-2\eta/(1-\eta)k<K−2η/(1−η) as in item 2, which its proof uses. The condition η<1−2/(K−2)\eta<1-2/(K-2)η<1−2/(K−2) is kept literally in R\mathbb RR; for K≤2K\le2K≤2 it is implied by η<1\eta<1η<1, part of the SRNSP.

Preamble
import Mathlib
import Definitions.Def_IRLSM_Convergence_Algorithm

open HighDimStat.MatrixRank Matrix Filter Topology
Formal statement
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
Source
Fornasier, Rauhut, Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, arXiv:1010.2471v4 (2011), Theorem 6.11, pp. 20–21
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me