Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information

• p. 5 Last paragraph

  has dimension |T ∪ S| − |Ω|

• p. 6 First line

  when |T ∪ S| ≥ |Ω|, and has dimension |T ∩ S| otherwise

• p. 6 Continuation of final paragraph on page 5

  when |T ∪ S| ≥ |Ω|

• p. 6 First paragraph

  dimension at most 2Nt −|Ω|

Only the authors can say what is right here.

Judge's note: Checked p.5 (bottom) and p.6 (top). My own working: the map (f,g) ↦ (f̂−ĝ)|Ω on ℓ2(T)×ℓ2(S) has image F_{T∪S→Ω}(ℓ2(T∪S)). By Lemma 1.2 (N prime) its rank is min(|T∪S|,|Ω|). So the kernel has dimension |T|+|S|−min(|T∪S|,|Ω|). That gives |T∩S| in the 'otherwise' branch, which matches the paper, and |T|+|S|−|Ω| when |T∪S|≥|Ω|, which does not match the printed |T∪S|−|Ω|. Counterexample: N=5, Ω={0,1}, T={0,1}, S={1,2} gives dimension 2, while the printed formula gives 1. The printed branches also disagree at |T∪S|=|Ω| (0 versus |T∩S|). The next sentence's bound 2N_t−|Ω| matches the corrected formula, so that consequence still holds.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 12 Lemma 2.1, second bullet

  Conversely, if f is the unique minimizer of (P1), then there exists a vector P with the above properties.

• p. 13 Converse proof

  By perturbing the hyperplane if necessary

Only the authors can say what is right here.

Judge's note: I reworked the counterexample. N=3, w=e^{2πi/3}, Ω={0,1}, f=(1,w,0). ker F_Ω is spanned by h=(1,w²,w), so ‖f+zh‖₁=|1+z|+|1+wz|+|z| ≥ 2+Re((1+w)z)+|z| ≥ 2, since |1+w|=1. Equality needs Im z=0 and Im(wz)=0, which forces z=0, so f is the unique minimiser. Any P with P̂ supported in {0,1} has the form a+bw^t. The conditions P(0)=1 and P(1)=w force a=0, b=1, so |P(2)|=|w²|=1 and the strict inequality fails. F_{supp f→Ω} is injective here, so the sufficient direction is not involved. The p.13 proof relies on a facet structure of the ℓ1 ball that the complex ball does not have. The converse direction of the stated lemma is therefore false as printed for complex f. The sufficient direction, which the main theorem uses, is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Eq. (3.3)

  an ≤ 2^{n+1} e^{−n} n^n (τ/(1−τ))^n N^n |T|^n

• p. 36 Appendix 7.1, first display

  N |T|^{2n−1} ≤ n^n 2^{n+1} e^{−n}

• p. 16 (3.3)

  an ≤2n+1 e−n nn

• p. 36 Appendix 7.1, first display

  (2n −1)2n (cτ)−(2n−1) N |T|2n−1 ≤nn 2n+1 e−n

Only the authors can say what is right here.

Judge's note: Checked on pages 16 and 36. a_n = (2n−1)^{2n} c_τ^{−(2n−1)} N |T|^{2n}, so the left side of the appendix display is a_n/|T|. Multiplying the appendix inequality by |T| gives a_n ≤ 2^{n+1}e^{−n}n^n(τ/(1−τ))^n N^n |T|^{n+1}. That is weaker by a factor of |T| than (3.3) as printed. I re-derived the appendix's second line from its first and it is consistent, so the appendix does prove the |T|^{n+1} form. The |T|^{n+1} form is also what (3.2) needs, since b_n has |T|^{n+1}. As printed, Theorem 3.3's claim that (3.3) holds is therefore not established, although (3.6) still follows from the weaker form. Probably an exponent slip in (3.3); only the authors can confirm.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Definition of an and equation (3.3)

  N |T|2n

• p. 17 Theorem 3.3

  Then (3.3) holds for any n ≥ 4

• p. 36 Appendix 7.1, first displayed inequality

  N |T|2n−1

Only the authors can say what is right here.

Judge's note: Checked a_n and (3.3) on p.16, Theorem 3.3 on p.17 and Appendix 7.1 on p.36. Recomputed for N=10000, τ=.44, n=4, α=α_M=.99, |T|=115: γ²=9.3501 and c_τ=0.65555. The middle term of (3.5) is 115.30, so (3.5) holds. Using log10: a_n ≈ 10^28.530 ≈ 3.39e28, while the RHS of (3.3) ≈ 10^26.000. The ratio is ≈339. Even with the extra |T| factor implied by the appendix (|T|^{n+1} on the right), the ratio is ≈2.95>1. So the claimed implication fails as stated. This is consistent with C066: the appendix's numerical check rests on an incorrect r_τ.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Equation (3.2)

  γ2 = 2φ2/(1 − τ)

• p. 21 Final derivation and equation (3.13)

  α(M) = 1/[29.6(M + 1)] (1 + o(1))

Only the authors can say what is right here.

Judge's note: Checked (3.2) on p.16 and the conclusion of §3.4 on p.21. I found no statement that τ→0 or that γ is redefined without (1−τ). The value 1/29.6 corresponds to τ=0 only. At fixed admissible τ (≤ .44) the dropped factor cannot be absorbed into 1+o(1). The printed constant is therefore larger than the derivation supports, for example 0.0338 versus 0.0253 at τ=1/4.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 36 Appendix 7.1

  rτ = (1 − τ)³/(e α² φ² [log((1−τ)/τ)]²)

• p. 36 Appendix 7.1, definition of rτ

  rτ = 2α2e(1 − τ)/(γ2c2τ)

• p. 36 Sentence beginning “Note that plugging”

  (1 − τ)3/(e α2 φ2

• p. 36 Equation (7.1) and following claim

  holds for τ ≤ .44 and n ≥ 4

Only the authors can say what is right here.

Judge's note: Checked p.36 and (3.2) on p.16. I re-derived r_τ from the appendix's own inequality and confirmed its first definition. Substituting γ²=2φ²/(1−τ) and c_τ=eL gives α²(1−τ)²/(eφ²L²); the printed form has (1−τ)³ and α² in the denominator. Numbers at τ=.44, α=1: L=0.24116, eφ²L²=0.41389, correct r=0.7577 (ln −0.2775), printed r=0.4243 (ln −0.857), s_τ=0.5151 (ln −0.6635). For n=4 the LHS of (7.1) is 3(−0.2775)+ln4+1/8 ≈ 0.679 > −0.6635 with the correct r, so it fails; with the printed r it holds. The claimed range 'τ ≤ .44 and n ≥ 4' in Theorem 3.3 therefore rests on this slip (see C026).

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 20 Proof of Lemma 3.6, equation (3.11)

  For each m and k such that km ≥ n

• p. 20 Equation (3.11)

  E|Xm(t)|2k ≤ 2n e−n α2n · |τN|2n

Only the authors can say what is right here.

Judge's note: Checked (3.10) on p.19, H (2.10) on p.14 and (3.11) on p.20. Counterexample worked through: N=10000, τ=.1, n=7, α=1/2, T={0}, f=δ0, t=1. α_M=0.2018 makes (3.5) hold with equality to 1. Then X_1(1)=−Σ_k I_k e^{2πik/N}, which has mean 0 and E|X|²=Nτ(1−τ)=900. For k=13 (n ≤ km < 2n, the range the proof uses), Jensen's inequality gives E|X|^26 ≥ 900^13 ≈ 10^38.405. The RHS is 14e^{−7}2^{−14}1000^{14} ≈ 10^35.892, so the inequality fails by a factor of about 326. (3.10) covers only km=n, and higher moments scale differently. Lemma 3.6 is left without a valid proof at this step.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 27 Proof of Lemma 4.4, factorised T(∼1)

  τ^{|A′/∼′|}(−1)^{|A′/∼′|−|A′|}(|A′/∼′| −1)!

• p. 26 After (4.8)

  F2(τ) = −τ + τ²

• p. 27 Lemma 4.4, equation (4.9)

  F|A′|(τ)

• p. 28 Lemma 4.5, equation (4.11)

  E[Tr(H02n)]

Only the authors can say what is right here.

Judge's note: Checked (4.8) on p.26, Lemma 4.4 on p.27, (4.11) on p.28 and (4.3)'s structure on p.25. Worked |A|=2 directly. LHS of (4.9) = τ²Σ_≠ + τΣ_= = τ²Σ_all + (τ−τ²)Σ_=. RHS = F1²Σ_all + F2Σ_= = τ²Σ_all + (τ²−τ)Σ_=. The coefficients of Σ_= have opposite signs. The unfactorised sign (−1)^{|A/∼|−|A/∼1|} splits per class as (−1)^{|A′/∼′|−1}, not (−1)^{|A′/∼′|−|A′|}. Consequence for (4.11) at n=1, N=2, T={0,1}, τ=1/4: E Tr(H0²)=|T|(|T|−1)Nτ(1−τ)=3/4>0, while (4.11) gives 4F2(1/4)=−3/4. Later bounds use |F_n| via Lemma 4.3, but (4.9) and (4.11) are false as printed.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 28 Eq. (4.12)

  P(n, k) = P(n −1, k) + (n −1)P(n −2, k −1)

• p. 28 Lemma 4.6, equation (4.14)

  P(n, k) ≤ λn (n − 1) . . . (n − 2k + 1)

• p. 29 Proof of Lemma 4.6

  P(n + 1, k)

• p. 28 (4.12)

  P(n, k) = P(n −1, k) + (n −1)P(n −2, k −1),

Only the authors can say what is right here.

Judge's note: Checked p.28 and the proof on p.29. P(5,2) is the number of 2+3 splits of 5 elements, C(5,2)=10. The printed recursion gives P(4,2)+4P(3,1)=3+4=7; the corrected recursion kP(n−1,k)+(n−1)P(n−2,k−1) gives 2·3+4=10. Lemma 4.6 fails at λ=φ: P(100,2)=2^99−101 ≈ 6.3e29, while φ^100·99·98·97 ≈ 7.9e20·9.4e5 ≈ 7.5e26. So the lemma, and the bound used in (4.19), are left without a valid proof.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 29 Proof of Lemma 4.6

  P(n + 1, k) = P(n −1, k) + (n −1)P(n −2, k −1)

• p. 28 Lemma 4.6, (4.14)

  P(n, k) ≤λn (n −1) . . . (n −2k + 1),

• p. 30 application before (4.19)

  P(2n, k) ≤φ2n (2n−1) . . . (2n−2k+1)

Only the authors can say what is right here.

Judge's note: The proof on p.29 applies (4.12) at n+1 but writes the right side of (4.12) at n, so the chain ends with the bound for P(n,k), not P(n+1,k). The recursion also lacks the factor k (C044). My counterexample: P(n,2) = S(n,2) − n = 2^{n−1} − 1 − n. At n = 70, P(70,2) = 2^69 − 71 ≈ 5.90e20. The bound is φ^70·69·68·67 ≈ 4.257e14·314364 ≈ 1.34e20, so the bound fails. Lemma 4.6 is used on p.30 (P(2n,k) ≤ φ^{2n}(2n−1)…(2n−2k+1)) in (4.19)–(4.20). The argument for Theorem 3.1 therefore loses this step as printed. Whether the theorem holds with other constants is for the authors to say.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 30 Definition (4.18)

  u, log u ≤ 1 − n

• p. 31 Lemma 4.9 and its proof

  f(k + 1) − f(k) ≥ f(k) − f(k − 1)

• p. 31 Proof of Lemma 4.9

  ρk+1 ρk−1 ≥ 1

Only the authors can say what is right here.

Judge's note: Checked (4.18) and (4.20) on p.30 and Lemma 4.9 on p.31. Recomputed with n=4, N=1000, |T|=1, u=τ/(1−τ)=0.0003, so log u ≈ −8.1 and G(2)=…=G(8)=u. From (4.20): f(1)=1000·7·u=2.1, f(2)=10^6·35·u²=3.15, f(3)=10^9·105·u³=2.835, f(4)=10^12·105·u⁴=0.8505. Then f(3)−f(2)=−0.315<1.05=f(2)−f(1), and f(2)>max(f(1),f(4)). The lemma states no restriction that excludes this regime (τ<1/2 holds).

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 31 Lemma 4.9 and its proof

  It is now a simple exercise to check that for each m ≥2, the logarithm of the right-hand is

Only the authors can say what is right here.

Judge's note: My own check against (4.18) and (4.20) on pp.30–31 (odd product, as implied by f(n) on p.31). Take τ = .001, so u = 1/999 and ln(999) ≈ 6.907. The first branch G = u applies for arguments ≤ 1 + 6.907, so G(2) = G(4) = G(6) = u. For any n ≥ 3, k = n−1: f(n)/f(n−1) = (N/|T|)·1·G(2)G(2)/G(4) = (N/|T|)u, and f(n−1)/f(n−2) = (N/|T|)·3·G(2)G(4)/G(6) = 3(N/|T|)u. With |T| = Nu: f(n) = f(n−1) and f(n−2) = f(n−1)/3. Then f(n) − f(n−1) = 0 < f(n−1) − f(n−2) = (2/3)f(n−1), contradicting the lemma as stated. Equivalently the sum of ratios is 1 + 1/3 < 2. The second display line holds only if all three G values use the second branch. The stated lemma (and its use for f(k) ≤ max(f(1), f(n))) is therefore unproved in that regime, though Theorem 3.1 might be recoverable by other means.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 38 Equation (7.3) and its justification

  since |ei

Only the authors can say what is right here.

Judge's note: Checked pp.37–38. Unit modulus allows |Σ a_i e^{iθ_i}| ≤ Σ|a_i|, not ≤ Σ a_i with signed a_i. I verified the counterexample: N=4, T={1,3}, t0=0, f(1)=1, f(3)=i, n=0, K=2. X=−(1+i)(I0−I1−I2+I3). At τ=.1, v=.09 and μ4=.0657, so E|X|⁴=4(4·.0657+36·.0081)=2.2176. The phase-free RHS of (7.3) (3 pairings × 4 t-choices × 16·F2², plus 8 t-tuples × 4·F4 with F4=−.0414) is 0.2304. With the C049 sign corrected, τ=1/4 still gives a phased moment of 6.375 against a phase-free sum of 6. So the proof of Lemma 3.5 is incomplete at this step.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 21 Section 3.4, item 3

  Lemma 3.6 assures that it is sufficient to have N^{3/2}α^n/(1 − α^n) ≤ .045

• p. 21 proof of Lemma 3.7

  ∥H∥∞· ∥R∥∞≤|T|3/2 ·

• p. 21 Section 3.4, item 3

  Lemma 3.6 assures that it is

Judge's note: Lemma 3.6 (p.19–20) fixes a0 = .91 and bounds P0 and Q0 only. Lemma 3.7 (p.20) fixes a1 = .09 and assumes |τN|^{3/2}α^n/(1−α^n) ≤ a1/2 = .045 to conclude ∥P1∥∞ ≤ a1. So the pointer in item 3 is wrong. The 1/|Ω| point in reviewer note 2 is the same defect as C034 and is judged there.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 32 Section 5, paragraph 4

  Theorem 2.1 states that f is a minimizer of (P1) if and only if there exists any trigonometric polynomial

• p. 32 Section 5, paragraph on slack in analysis

  Theorem 2.1 states that f is a minimizer of (P1) if and only if

• p. 32 Sec 5

  Theorem 2.1 states that f is a minimizer

Judge's note: Page 32 image confirms the text. A text search finds only 'Lemma 2.1' (line 615, p.12) and no Theorem 2.1 anywhere.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 5 Proof of Theorem 1.1, second paragraph

  we can find disjoint subsets T, S of Ω such that |T|, |S| ≤ 1/2|Ω| + 1 and |T| + |S| = |Ω| + 1

• p. 5 Proof of Theorem 1.1, second claim

  we can find disjoint subsets T, S of Ωsuch

• p. 5 Proof of Theorem 1.1, second claim

  disjoint subsets T, S of Ωsuch that |T|, |S| ≤1

Only the authors can say what is right here.

Judge's note: Page 5 image checked; it reads 'of Ω'. Reworked: if T and S are disjoint subsets of Ω, then |T|+|S| = |T∪S| ≤ |Ω| < |Ω|+1, so the required sets cannot exist. If T and S are taken in Z_N, the step works, using |Ω| < N to get |T∪S| = |Ω|+1 ≤ N. The bijection F_{T∪S→Ω∪{k0}} from Lemma 1.2 then gives h, and f = h|T, g = −h|S. So the step is false as printed, but the converse claim of Theorem 1.1 still stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Section 1.4, derivation following (1.10)

  with υ(ω) = (1 − e−iω)−1

• p. 8 Transformed minimization problem

  ˆδ|Ω\{0} = (υˆf)|Ω\{0}

• p. 8 Section 1.4, reduction of (1.10) to (1.5)

  with υ(ω) = (1 − e−iω)−1, the problem is identical to

• p. 8 Section 1.4, display after definition of υ

  ˆδ|Ω\{0} = (υ ˆf)|Ω\{0}, ˆδ(0) = 0,

Only the authors can say what is right here.

Judge's note: Read on the p.8 image. The line above the definition gives δ̂(ω)=(1−e^{−iω})ĝ(ω). Substituting ĝ=f̂ on Ω gives δ̂=(1−e^{−iω})f̂=υ^{−1}f̂, not υf̂. Example: at ω=π the multiplier is 2, but υ(π)=1/2. Either the exponent −1 in the definition or the use of υ in the constraint is a slip. The statement of Corollary 1.4 does not depend on which multiplier is written, so the step is faulty but the stated result stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 11 Equation (2.2)

  + µ+∗g+ + (µ−)∗g−

• p. 12 Opening sentence and equations (2.4)–(2.5)

  with µ+, µ− ≥ 0

Only the authors can say what is right here.

Judge's note: Checked (2.2) on p.11 and the displays on p.12. For a minimisation with g±≥0 and multipliers µ±≥0, the Lagrangian terms must be −µ±g±. With the printed + signs, adding the two stationarity equations gives 2+µ++µ−=0, which is impossible when µ±≥0. The p.12 stationarity display follows (2.2) (+µ+), but (2.4)–(2.5) switch to −µ+ and −µ−, so the derivation is internally inconsistent. This is the heuristic real-valued motivation; Lemma 2.1 is proved separately on p.13, so the stated results stand.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 12 Saddle-point conditions above (2.3)

  = I{g̃+(t)>0} − F*Ωλ + μ+ = 0

• p. 12 (2.4), (2.5)

  1 − (F*Ωλ)(t) − μ+ = 0

• p. 11 Lagrangian (2.2)

  + µ+∗g+ + (µ−)∗g−

• p. 12 stationarity conditions and (2.4)-(2.5)

  1 −(F∗Ωλ)(t) −µ+ = 0

Only the authors can say what is right here.

Judge's note: Reworked from the images. Differentiating (2.2) in g+(t) gives 1 − (F*λ)(t) + µ+(t), so (2.2) and the displayed derivative lines agree with each other. Setting this to zero gives F*λ = 1 + µ+ ≥ 1 on T^c. (2.4) instead gives F*λ = 1 − µ+ ≤ 1, which is the version that yields |P| ≤ 1 and matches the usual Lagrangian (objective − µ*g for g ≥ 0). Also, with the indicator form, the derivative line on T^c (g̃+ = 0) reads −F*λ + µ+ = 0, which is not (2.4). So (2.2) with the derivative lines cannot be reconciled with (2.4)–(2.5) as printed. This is a heuristic motivation; Lemma 2.1 is proved separately, so the stated result stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 12 Stationarity display before (2.3)

  I{˜g+(t)>0} − F*Ωλ + µ+

• p. 12 Same display, derivative with respect to g−

  I{˜g−(t)>0} + F*Ωλ + µ−

Only the authors can say what is right here.

Judge's note: Checked the p.12 image. The objective is linear in the split variables, so each partial derivative is 1 at every coordinate. On T^c we have g̃±=0, so the printed indicator would be 0, yet (2.4)–(2.5) write 1 − F*λ − µ+ = 0 and 1 + F*λ − µ− = 0. The display therefore does not lead to the equations that follow it. This is a separate defect from the multiplier sign in C018. It sits in the heuristic section; Lemma 2.1 is proved independently.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 15 Equation (2.11)

  P := (ι − 1/|Ω| H)

• p. 18 Section 3.3, opening display

  P = 1/|Ω| H

Only the authors can say what is right here.

Judge's note: Compared (2.11) on p.15 with the opening display of §3.3 on p.18. Off T the ι term is zero, which leaves −(1/|Ω|)H(...)^{-1}ι*sgn(f); the minus sign is lost on p.18. The later bounds work with |P(t)| and absolute-value estimates, so the stated results are unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 17 Display after 'it follows from the Markov inequality that'

  P(∥H0^n∥F ≥ α^n · |τN|^n) = E∥H0^n∥²F / (α^{2n}|τN|^{2n})

• p. 17 display before (3.4)

  P(∥Hn0 ∥F ≥αn · |τN|n) = E∥Hn0 ∥2F

Only the authors can say what is right here.

Judge's note: Page 17 image shows '='. As printed the relation is false in general: if the norm is deterministically c with threshold c/2, the left side is 1 and the right side is 4. The next display, (3.4), correctly uses ≤, so the stated result stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 Section 3.2, bound on R

  ∥ι∗H∥F ≤α · |Ω|, then

• p. 20 Lemma 3.7 statement

  on the event A ∩{∥ι∗H∥F ≤α|Ω|}

Only the authors can say what is right here.

Judge's note: From the images, R = Σ_{k≥1}((ι*H)^n/|Ω|^n)^k, so the R bound needs only ‖(ι*H)^n‖_F ≤ α^n|Ω|^n, which (3.6)/Cor. 3.4 do control. The printed event ‖ι*H‖_F ≤ α|Ω| is not shown to have high probability anywhere. The proof of Lemma 3.7 (p.21) nonetheless asserts the (3.8)-based bound 'with probability at least 1 − O(N^{−M})'. My own check, assuming Bernoulli(τ) selection: E|Σ_{ω∈Ω}e^{iωu}|² = τ(1−τ)N for u ≠ 0, so E‖H_0‖_F² = |T|(|T|−1)τ(1−τ)N. For |T| of order τN/log N this far exceeds (α|Ω|)² ≈ α²τ²N². The paper itself notes on p.15 that the Frobenius route works only for |T| ≪ √|Ω|. I showed this in expectation only, not as a tail bound. The stated result appears recoverable by putting the event on (ι*H)^n, so this is a gap in a hypothesis, not in the theorem.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 Section 3.3, first display

  P = 1 |Ω|H(ι∗ι −1 |Ω|ι∗H)−1ι∗sgn(f),

• p. 19 definition of P0, P1, S_n

  P0 = Snsgn(f),

Only the authors can say what is right here.

Judge's note: Reworked from (2.11) on p.15: for t ∉ T, (ιx)(t) = 0, so P(t) = −(1/|Ω|)(Hx)(t). The minus sign in the definition of H (2.10) is internal to H and does not cancel this. Substituting (3.7) gives −Σ_{m=1}^n|Ω|^{−m}(Hι*)^m sgn(f) = −S_n sgn(f), and P1 changes sign likewise. Only |P0|, |P1| and ‖·‖_∞ are bounded afterwards, so the stated results stand.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 21 Section 3.4, first paragraph

  we proved the invertibility of i*i − 1/|Ω| ι*H with probability O(N^{−M})

• p. 21 Section 3.4, item 1

  is invertible with probability O(N^{−M})

Judge's note: Page 21 image shows 'probability O(N^{−M})' in both places, with no '1 −'. Corollary 3.4 (p.17) states probability at least 1 − (1 + 2/γ²)N^{−M}, and p.15 says 'with probability 1 − O(N^{−M})'.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 21 Section 3.4, item 2

  both P0 and Q0 are bounded by .91 outside of T^c

• p. 21 Section 3.4 items 2-3

  bounded by .91 outside of T c

Judge's note: Page 21 image confirms the wording, and item 3 likewise says 'outside T^c'. Lemma 3.6 and the definition of P0 (t ∈ T^c, p.19) concern t ∈ T^c. On T, P = sgn(f) has modulus 1.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send