Proposition 6.8 — δ_4k < √2 − 1 implies the strong rank null space property of order k with η = √2 δ_4k/(1 − δ_3k)
ProvedIRLSM.RIP.proposition_6_8Let be a linear map whose rank restricted isometry constants (Definition 1.1) satisfy and
Then satisfies the strong rank null space property of order (Definition 6.4) with constant
That is, for every nonzero in the kernel of and every decomposition with , there are with , , , , and .
Together with the convergence analysis of the IRLS-M algorithm, this shows that the algorithm recovers every matrix of rank at most from measurements with a small restricted isometry constant, and that nuclear-norm minimization does so stably.
Formalization Note. Real matrices; . is the squared-form constant of Definition 1.1, defined for every (here may exceed ). The hypothesis is Definition 1.1's own requirement ; without it could be . The conclusion includes , which is part of Definition 6.4.
import Mathlib import Definitions.Def_IRLSM_Convergence_Basic open HighDimStat.MatrixRank Matrix
namespace IRLSM.RIP
/-- Proposition 6.8: if the rank restricted isometry constant satisfies `δ_{4k} < √2 − 1`, then
`S` has the strong rank null space property of order `k` with constant
`η = √2 δ_{4k}/(1 − δ_{3k}) ∈ (0, 1)`.
Fornasier–Rauhut–Ward, arXiv:1010.2471v4, Proposition 6.8 with (6.6), p. 18.
Formalization Notes: real matrices; `S(X)_l = ⟨A_l, X⟩`; `δ_k` is `ripConst A k` (squared form
of Definition 1.1, defined for every `k`, since `4k` may exceed `n`). The hypothesis
`0 < δ_{4k}` is the positivity "δ_k > 0" of Definition 1.1; without it `η` could be
`0 ∉ (0, 1)`. `SRNSP` contains `0 < η < 1`, so the conclusion includes "η ∈ (0, 1)". -/
theorem proposition_6_8 {n p m : ℕ} (A : Fin m → Matrix (Fin n) (Fin p) ℝ) (k : ℕ)
(hpos : 0 < IRLSM.Convergence.ripConst A (4 * k)) (h66 : IRLSM.Convergence.ripConst A (4 * k) < Real.sqrt 2 - 1) :
IRLSM.Convergence.SRNSP A k (Real.sqrt 2 * IRLSM.Convergence.ripConst A (4 * k) / (1 - IRLSM.Convergence.ripConst A (3 * k))) := by sorry
end IRLSM.RIP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.