Theorem 1.7 — Uniqueness implies a minimal sampling rate
ProvedCandesTao.LowerBound.uniqueness_implies_minimal_sampling_rateFix integers and , a real and , and assume that is an integer. Observe the entries of real matrices under the Bernoulli model: the observed set contains each entry independently with probability , and keeps the entries of in and sets the others to zero.
Suppose that at least one of the sampling conditions fails:
Then, with probability at least over , there are infinitely many pairs of matrices with
both of rank at most and both obeying the incoherence property (I.18) with parameter ( and for the column and row spaces).
Consequently, even knowing the rank bound and the coherence ahead of time, no method that sees only can recover every such matrix with probability greater than unless (I.20) holds; up to the factor , about samples are necessary.
Formalization Note The event is "the set of such pairs is infinite", evaluated for each observation set ; its probability under the Bernoulli model is the platform's bernoulliEventProb (m/n²). The pairs may depend on , which is the reading the paper proves in Section II and uses in the sentence following the theorem. The integrality of 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 (, larger than an absolute constant) serve the upper bounds and are not imposed; the theorem's own ranges are.
import Definitions.Def_CandesTao_LowerBound_Incoherence import Definitions.Def_CandesTao_LowerBound_SamplingConditions open MatrixCompletion
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be natural numbers and let be real numbers. The statement makes these assumptions:
- ;
- ;
- ;
- ;
- , taken as a real number, equals under real division. appears nowhere else in the statement, so this hypothesis only limits the parameters: 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 . Their definitions come from an imported file and are not shown here, so this read-back cannot expand them. The hypothesis says only that or holds.
Given these, the statement concludes the following. Write . For a set of positions , define the property to mean that this set is infinite:
Here:
- contains ordered pairs of distinct real matrices.
- is the set of matrices satisfying the imported predicate "incoherent with rank at most and parameter ". Its definition is not shown here. Judging by the name only, it is some rank-at-most- condition combined with some incoherence condition with parameter .
- is the imported "sampling projection" onto . Its definition is not shown either. By name, it keeps the entries indexed by .
The claim is
is another imported definition that is not shown. By name, it is the probability that holds when is a random subset of that includes each position independently with probability . So the conclusion says: with probability at least under this sampling model, there are infinitely many ordered pairs of distinct matrices in that agree on every entry in . The statement does not say that has exactly elements. enters only through .
Degenerate cases:
- : excluded, because . So , the index set is nonempty, and , so the formula for never divides by zero.
- What the hypothesis forces: and , so , which rules out . Hence and . Only values of of that form with are allowed. For example:
- when , it forces , and ;
- when , it forces and .
- : nothing prevents , which makes . What returns for a parameter outside depends on its unseen definition.
- Range of : is strictly between and , so the conclusion is never trivially true through .
- 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.