Theorem 3.2 β if Ξ΄_2r < 1, Xβ is the only matrix of rank at most r with π(X) = π(Xβ)
ProvedMinRankRecovery.Recovery.theorem_3_2Let be a linear map with restricted isometry constants , let be an integer, and let have rank at most . Set . If
then is the only matrix of rank at most satisfying .
This is the uniqueness half of the theory: under the restricted isometry condition the linear measurements determine a low-rank matrix among all matrices of the same rank bound. It does not by itself give an efficient recovery procedure; Theorem 3.3 does.
Formalization Note The paper's section assumes ; the statement here assumes , a mild generalization: the paper's proof uses only that has rank at most , which holds whenever both matrices have rank at most . The map is represented by measurement matrices as in Definition 3.1.
import Mathlib import Definitions.Def_HighDimStat_MatrixRank_Core import Definitions.Def_MinRankRecovery_Recovery_ripConst open HighDimStat.MatrixRank Matrix
namespace MinRankRecovery.Recovery
/-- Theorem 3.2, p. 12: if `Ξ΄_2r < 1` for some `r β₯ 1`, then `X0` (of rank at most `r`) is the
only matrix of rank at most `r` with `π(X) = π(X0)`. -/
theorem theorem_3_2 {m n p : β} (Xs : Fin p β Matrix (Fin m) (Fin n) β) (r : β) (hr : 1 β€ r)
(hΞ΄ : ripConst Xs (2 * r) < 1) (X0 : Matrix (Fin m) (Fin n) β) (hX0 : X0.rank β€ r) :
β X : Matrix (Fin m) (Fin n) β, X.rank β€ r β
observationOp Xs X = observationOp Xs X0 β X = X0 := by sorry
end MinRankRecovery.Recovery
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.