Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.7 — Uniqueness implies a minimal sampling rate

Proved
CandesTao.LowerBound.uniqueness_implies_minimal_sampling_rate

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

lower-boundmatrix-completionp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity

Fix integers 1≤m1 \le m1≤m and 1≤r≤n1 \le r \le n1≤r≤n, a real μ0≥1\mu_0 \ge 1μ0​≥1 and 0<δ<1/20 < \delta < 1/20<δ<1/2, and assume that ℓ:=n/(μ0r)\ell := n/(\mu_0 r)ℓ:=n/(μ0​r) is an integer. Observe the entries of n×nn\times nn×n real matrices under the Bernoulli model: the observed set Ω⊆[n]×[n]\Omega \subseteq [n]\times[n]Ω⊆[n]×[n] contains each entry independently with probability p=m/n2p = m/n^2p=m/n2, and PΩ(X)\mathcal{P}_\Omega(X)PΩ​(X) keeps the entries of XXX in Ω\OmegaΩ and sets the others to zero.

Suppose that at least one of the sampling conditions fails:

m≥n2(1−e−μ0rnlog⁡(n2δ))(I.20)m \ge n^2\left(1 - e^{-\frac{\mu_0 r}{n}\log\left(\frac{n}{2\delta}\right)}\right) \qquad \text{(I.20)}m≥n2(1−e−nμ0​r​log(2δn​))(I.20) m≥(1−ϵ) μ0nrlog⁡(n2δ),ϵ:=12μ0rnlog⁡(n2δ).(I.21)m \ge (1-\epsilon)\,\mu_0 n r\log\left(\frac{n}{2\delta}\right), \quad \epsilon := \frac12\frac{\mu_0 r}{n}\log\left(\frac{n}{2\delta}\right). \qquad \text{(I.21)}m≥(1−ϵ)μ0​nrlog(2δn​),ϵ:=21​nμ0​r​log(2δn​).(I.21)

Then, with probability at least δ\deltaδ over Ω\OmegaΩ, there are infinitely many pairs (M,M′)(M, M')(M,M′) of n×nn\times nn×n matrices with

M≠M′,PΩ(M)=PΩ(M′),M \ne M', \qquad \mathcal{P}_\Omega(M) = \mathcal{P}_\Omega(M'),M=M′,PΩ​(M)=PΩ​(M′),

both of rank at most rrr and both obeying the incoherence property (I.18) with parameter μ0\mu_0μ0​ (∥PUea∥2≤μ0r/n\|P_U e_a\|^2 \le \mu_0 r/n∥PU​ea​∥2≤μ0​r/n and ∥PVeb∥2≤μ0r/n\|P_V e_b\|^2 \le \mu_0 r/n∥PV​eb​∥2≤μ0​r/n for the column and row spaces).

Consequently, even knowing the rank bound and the coherence ahead of time, no method that sees only PΩ(M)\mathcal{P}_\Omega(M)PΩ​(M) can recover every such matrix with probability greater than 1−δ1-\delta1−δ unless (I.20) holds; up to the factor 1−ϵ1-\epsilon1−ϵ, about μ0nrlog⁡n\mu_0 n r\log nμ0​nrlogn samples are necessary.

Formalization Note The event is "the set of such pairs is infinite", evaluated for each observation set Ω\OmegaΩ; its probability under the Bernoulli model is the platform's bernoulliEventProb (m/n²). The pairs may depend on Ω\OmegaΩ, which is the reading the paper proves in Section II and uses in the sentence following the theorem. The integrality of ℓ=n/(μ0r)\ell = n/(\mu_0 r)ℓ=n/(μ0​r) is the paper's own "without loss of generality" of Section II, stated as a hypothesis. The hypothesis "(I.20) fails or (I.21) fails" covers both parts of the theorem. The logarithm is natural. The standing assumptions of Section I-H (m≥2nrm \ge 2nrm≥2nr, nnn larger than an absolute constant) serve the upper bounds and are not imposed; the theorem's own ranges are.

Preamble
import Definitions.Def_CandesTao_LowerBound_Incoherence
import Definitions.Def_CandesTao_LowerBound_SamplingConditions
open MatrixCompletion
Formal statement
namespace CandesTao.LowerBound

theorem uniqueness_implies_minimal_sampling_rate
    (n m r : ℕ) (μ₀ δ : ℝ) (ℓ : ℕ)
    (hm : 1 ≤ m) (hr : 1 ≤ r) (hrn : r ≤ n) (hμ₀ : 1 ≤ μ₀)
    (hδ : 0 < δ) (hδ' : δ < 1 / 2)
    (hℓ : (ℓ : ℝ) = n / (μ₀ * r))
    (hnot : ¬ SamplingConditionI20 n m r μ₀ δ ∨ ¬ SamplingConditionI21 n m r μ₀ δ) :
    bernoulliEventProb ((m : ℝ) / (n : ℝ) ^ 2)
        (fun Ω : Finset (Fin n × Fin n) =>
          {P : RealMatrix n n × RealMatrix n n |
            P.1 ≠ P.2 ∧ IncoherentRankAtMost r μ₀ P.1 ∧ IncoherentRankAtMost r μ₀ P.2 ∧
              samplingProjection Ω P.1 = samplingProjection Ω P.2}.Infinite) ≥ δ := by sorry

end CandesTao.LowerBound
Source
Candès & Tao, The Power of Convex Relaxation: Near-Optimal Matrix Completion, IEEE Trans. Inf. Theory 56(5), 2010, p. 2058, Theorem 1.7 (Uniqueness Implies a Minimal Sampling Rate), Eqs. (I.20), (I.21); incoherence (I.18) on p. 2057; proof in Section II, pp. 2059–2060
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let n,m,r,ℓn, m, r, \elln,m,r,ℓ be natural numbers and let μ0,δ\mu_0, \deltaμ0​,δ be real numbers. The statement makes these assumptions:

  • m≥1m \ge 1m≥1;
  • 1≤r≤n1 \le r \le n1≤r≤n;
  • μ0≥1\mu_0 \ge 1μ0​≥1;
  • 0<δ<120 < \delta < \tfrac120<δ<21​;
  • ℓ\ellℓ, taken as a real number, equals nμ0 r\dfrac{n}{\mu_0\, r}μ0​rn​ under real division. ℓ\ellℓ appears nowhere else in the statement, so this hypothesis only limits the parameters: n/(μ0r)n/(\mu_0 r)n/(μ0​r) must be a natural number.
  • At least one of two imported sampling conditions fails. They are called "Sampling Condition I20" and "Sampling Condition I21", and each depends on (n,m,r,μ0,δ)(n, m, r, \mu_0, \delta)(n,m,r,μ0​,δ). Their definitions come from an imported file and are not shown here, so this read-back cannot expand them. The hypothesis says only that ¬ I20(n,m,r,μ0,δ)\neg\,\mathrm{I20}(n,m,r,\mu_0,\delta)¬I20(n,m,r,μ0​,δ) or ¬ I21(n,m,r,μ0,δ)\neg\,\mathrm{I21}(n,m,r,\mu_0,\delta)¬I21(n,m,r,μ0​,δ) holds.

Given these, the statement concludes the following. Write [n]={0,…,n−1}[n] = \{0,\dots,n-1\}[n]={0,…,n−1}. For a set of positions Ω⊆[n]×[n]\Omega \subseteq [n]\times[n]Ω⊆[n]×[n], define the property E(Ω)E(\Omega)E(Ω) to mean that this set is infinite:

SΩ  =  {(M1,M2)∈Rn×n×Rn×n  :  M1≠M2,  M1,M2∈I(r,μ0),  PΩ(M1)=PΩ(M2)}.S_\Omega \;=\; \bigl\{(M_1, M_2) \in \mathbb{R}^{n\times n}\times\mathbb{R}^{n\times n} \;:\; M_1 \ne M_2,\ \ M_1, M_2 \in \mathcal{I}(r,\mu_0),\ \ \mathcal{P}_\Omega(M_1) = \mathcal{P}_\Omega(M_2)\bigr\}.SΩ​={(M1​,M2​)∈Rn×n×Rn×n:M1​=M2​,  M1​,M2​∈I(r,μ0​),  PΩ​(M1​)=PΩ​(M2​)}.

Here:

  • SΩS_\OmegaSΩ​ contains ordered pairs of distinct real n×nn\times nn×n matrices.
  • I(r,μ0)\mathcal{I}(r,\mu_0)I(r,μ0​) is the set of matrices satisfying the imported predicate "incoherent with rank at most rrr and parameter μ0\mu_0μ0​". Its definition is not shown here. Judging by the name only, it is some rank-at-most-rrr condition combined with some incoherence condition with parameter μ0\mu_0μ0​.
  • PΩ\mathcal{P}_\OmegaPΩ​ is the imported "sampling projection" onto Ω\OmegaΩ. Its definition is not shown either. By name, it keeps the entries indexed by Ω\OmegaΩ.

The claim is

BernoulliEventProb ⁣(p,  E)  ≥  δ,p=mn2 (real division).\mathrm{BernoulliEventProb}\!\left(p,\; E\right) \;\ge\; \delta, \qquad p = \frac{m}{n^2}\ \text{(real division)}.BernoulliEventProb(p,E)≥δ,p=n2m​ (real division).

BernoulliEventProb\mathrm{BernoulliEventProb}BernoulliEventProb is another imported definition that is not shown. By name, it is the probability that E(Ω)E(\Omega)E(Ω) holds when Ω\OmegaΩ is a random subset of [n]×[n][n]\times[n][n]×[n] that includes each position independently with probability ppp. So the conclusion says: with probability at least δ\deltaδ under this sampling model, there are infinitely many ordered pairs of distinct matrices in I(r,μ0)\mathcal{I}(r,\mu_0)I(r,μ0​) that agree on every entry in Ω\OmegaΩ. The statement does not say that Ω\OmegaΩ has exactly mmm elements. mmm enters only through p=m/n2p = m/n^2p=m/n2.

Degenerate cases:

  • n=0n = 0n=0: excluded, because 1≤r≤n1 \le r \le n1≤r≤n. So n≥1n \ge 1n≥1, the index set [n][n][n] is nonempty, and n2>0n^2 > 0n2>0, so the formula for ppp never divides by zero.
  • What the ℓ\ellℓ hypothesis forces: μ0r>0\mu_0 r > 0μ0​r>0 and n≥1n \ge 1n≥1, so n/(μ0r)>0n/(\mu_0 r) > 0n/(μ0​r)>0, which rules out ℓ=0\ell = 0ℓ=0. Hence ℓ≥1\ell \ge 1ℓ≥1 and μ0=n/(ℓr)\mu_0 = n/(\ell r)μ0​=n/(ℓr). Only values of μ0\mu_0μ0​ of that form with 1≤ℓ≤n/r1 \le \ell \le n/r1≤ℓ≤n/r are allowed. For example:
    • when n=1n = 1n=1, it forces r=1r = 1r=1, μ0=1\mu_0 = 1μ0​=1 and ℓ=1\ell = 1ℓ=1;
    • when r=nr = nr=n, it forces μ0=1\mu_0 = 1μ0​=1 and ℓ=1\ell = 1ℓ=1.
  • p>1p > 1p>1: nothing prevents m>n2m > n^2m>n2, which makes p>1p > 1p>1. What BernoulliEventProb\mathrm{BernoulliEventProb}BernoulliEventProb returns for a parameter outside [0,1][0,1][0,1] depends on its unseen definition.
  • Range of δ\deltaδ: δ\deltaδ is strictly between 000 and 12\tfrac1221​, so the conclusion is never trivially true through δ≤0\delta \le 0δ≤0.
  • Possible vacuity: the disjunctive hypothesis may be impossible to satisfy for some or all parameter values, for example if I20 and I21 always hold. Whether that happens depends on the unseen definitions. Wherever both conditions hold, the statement says nothing.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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