Theorem 3.3 — if δ_5r < 1/10, nuclear norm minimization recovers X₀ exactly
ProvedMinRankRecovery.Recovery.nuclear_norm_recoveryLet be a linear map with restricted isometry constants (Definition 3.1), let be an integer, and let have rank at most . Put and consider the convex program
If
then : every matrix with and equals . In particular 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 , ensures that the tractable convex relaxation recovers every matrix of rank at most exactly. Section 4 of the paper shows that many random maps satisfy the condition with of order .
Formalization Note The conclusion is phrased so that it does not depend on how an arg min is chosen: since is itself feasible, "every feasible with equals " says exactly that is the unique minimizer. The paper's setting takes ; here , which is equivalent because for . The constant is defined for every (the paper restricts to under ); , and are not assumed.
import Mathlib import Definitions.Def_HighDimStat_MatrixRank_Core import Definitions.Def_MinRankRecovery_Recovery_ripConst open HighDimStat.MatrixRank Matrix
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.