§3, p. 12 — δ_r(𝒜) ≤ δ_r′(𝒜) for r ≤ r′
ProvedMinRankRecovery.Recovery.ripConst_monop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1restricted-isometry
Let be a linear map and its -restricted isometry constant. For integers ,
Every matrix of rank at most also has rank at most , so the restricted isometry inequality at level is the stronger requirement. The proof of Theorem 3.3 uses this in the form .
Formalization Note Stated for all natural numbers , with as defined in this mission (ripConst, an infimum over ).
Preamble
import Mathlib import Definitions.Def_HighDimStat_MatrixRank_Core import Definitions.Def_MinRankRecovery_Recovery_ripConst open HighDimStat.MatrixRank Matrix
Formal statement
namespace MinRankRecovery.Recovery
/-- §3, p. 12: `δ_r(𝒜) ≤ δ_{r'}(𝒜)` for `r ≤ r'`. -/
theorem ripConst_mono {m n p : ℕ} (Xs : Fin p → Matrix (Fin m) (Fin n) ℝ) {r r' : ℕ}
(h : r ≤ r') : ripConst Xs r ≤ ripConst Xs r' := by sorry
end MinRankRecovery.Recovery
Source
Recht, Fazel & Parrilo, arXiv:0706.4138v1, §3, first sentence of p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.