Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.3 — if δ_5r < 1/10, nuclear norm minimization recovers X₀ exactly

Proved
MinRankRecovery.Recovery.nuclear_norm_recovery

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

low-rank-recoverynuclear-normp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1restricted-isometry

Let A:Rm×n→Rp\mathcal A:\mathbb R^{m\times n}\to\mathbb R^pA:Rm×n→Rp be a linear map with restricted isometry constants δr=δr(A)\delta_r=\delta_r(\mathcal A)δr​=δr​(A) (Definition 3.1), let r≥1r\ge1r≥1 be an integer, and let X0∈Rm×nX_0\in\mathbb R^{m\times n}X0​∈Rm×n have rank at most rrr. Put b=A(X0)b=\mathcal A(X_0)b=A(X0​) and consider the convex program

X∗:=arg⁡min⁡X ∥X∥∗s.t.A(X)=b.(3.1)X^*:=\arg\min_X\ \|X\|_*\quad\text{s.t.}\quad\mathcal A(X)=b. \tag{3.1}X∗:=argXmin​ ∥X∥∗​s.t.A(X)=b.(3.1)

If

δ5r<110,\delta_{5r}<\tfrac1{10},δ5r​<101​,

then X∗=X0X^*=X_0X∗=X0​: every matrix XXX with A(X)=b\mathcal A(X)=bA(X)=b and ∥X∥∗≤∥X0∥∗\|X\|_*\le\|X_0\|_*∥X∥∗​≤∥X0​∥∗​ equals X0X_0X0​. In particular X0X_0X0​ is the unique minimizer of (3.1).

This is the paper's main deterministic recovery guarantee: a restricted isometry condition on the measurement map, with an absolute constant independent of m,n,r,pm,n,r,pm,n,r,p, ensures that the tractable convex relaxation recovers every matrix of rank at most rrr exactly. Section 4 of the paper shows that many random maps satisfy the condition with ppp of order r(m+n)log⁡(mn)r(m+n)\log(mn)r(m+n)log(mn).

Formalization Note The conclusion is phrased so that it does not depend on how an arg min is chosen: since X0X_0X0​ is itself feasible, "every feasible XXX with ∥X∥∗≤∥X0∥∗\|X\|_*\le\|X_0\|_*∥X∥∗​≤∥X0​∥∗​ equals X0X_0X0​" says exactly that X0X_0X0​ is the unique minimizer. The paper's setting takes rank⁡X0=r\operatorname{rank}X_0=rrankX0​=r; here rank⁡X0≤r\operatorname{rank}X_0\le rrankX0​≤r, which is equivalent because δ5r′≤δ5r\delta_{5r'}\le\delta_{5r}δ5r′​≤δ5r​ for r′≤rr'\le rr′≤r. The constant δr\delta_rδr​ is defined for every rrr (the paper restricts to 1≤r≤m1\le r\le m1≤r≤m under m≤nm\le nm≤n); m≤nm\le nm≤n, p≥1p\ge1p≥1 and X0≠0X_0\ne0X0​=0 are not assumed.

Preamble
import Mathlib
import Definitions.Def_HighDimStat_MatrixRank_Core
import Definitions.Def_MinRankRecovery_Recovery_ripConst

open HighDimStat.MatrixRank Matrix
Formal statement
namespace MinRankRecovery.Recovery

/-- Theorem 3.3, p. 12: if `r ≥ 1` and `δ_5r < 1/10`, then for every `X₀` of rank at most `r`,
`X₀` is the unique minimizer of `‖X‖_*` subject to `𝒜(X) = 𝒜(X₀)`: every feasible `X` with
`‖X‖_* ≤ ‖X₀‖_*` equals `X₀`. -/
theorem nuclear_norm_recovery {m n p : ℕ} (Xs : Fin p → Matrix (Fin m) (Fin n) ℝ) (r : ℕ)
    (hr : 1 ≤ r) (hδ : ripConst Xs (5 * r) < 1 / 10) (X0 : Matrix (Fin m) (Fin n) ℝ)
    (hX0 : X0.rank ≤ r) :
    ∀ X : Matrix (Fin m) (Fin n) ℝ, observationOp Xs X = observationOp Xs X0 →
      nuclearNorm X ≤ nuclearNorm X0 → X = X0 := by sorry

end MinRankRecovery.Recovery
Source
Recht, Fazel & Parrilo, arXiv:0706.4138v1, Theorem 3.3, p. 12 (problem (3.1), p. 11)
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