Proof of Proposition 6.8, p. 19 — shelling bound ‖σ^(j+1)‖₂ ≤ ℓ^(−1/2)‖σ^(j)‖₁ for a nonincreasing sequence
ProvedIRLSM.RIP.shelling_boundcompressed-sensinglow-rank-recoveryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonincreasing sequence of nonnegative reals and let be an integer. Cut the indices into consecutive blocks of length . Each block has Euclidean norm at most times the norm of the block before it: for every ,
In the proof of Proposition 6.8 the sequence is the vector of singular values of , the blocks are the vectors , and the bound reads . Summed over , it controls the tail of in display (6.7).
Formalization Note. Indices are 0-based, so the block is the paper's . The paper states the bound "for "; (6.7) uses it for every block, and it holds for every block for the same reason, so it is stated for all .
Preamble
import Mathlib import Definitions.Def_IRLSM_Convergence_Basic open HighDimStat.MatrixRank Matrix
Formal statement
namespace IRLSM.RIP
/-- The shelling bound: if `s` is a nonincreasing nonnegative sequence and the indices are
split into consecutive blocks of length `ℓ > 0`, the Euclidean norm of each block is at most
`ℓ^{-1/2}` times the `ℓ₁` norm of the block before it:
`(∑_{i=(j+1)ℓ}^{(j+2)ℓ-1} s_i²)^{1/2} ≤ ℓ^{-1/2} ∑_{i=jℓ}^{(j+1)ℓ-1} s_i`.
Fornasier–Rauhut–Ward, arXiv:1010.2471v4, proof of Proposition 6.8, p. 19 (the bound
`‖H_{j+1}‖_F ≤ ℓ^{-1/2}‖H_j‖_*`, in its vector form: the singular values of `H_j` are the entries
of `σ^{(j)}`).
Formalization Notes: 0-based indices, so the block `Ico (jℓ) ((j+1)ℓ)` is the vector `σ^{(j+1)}`
of the page. The page says "for j ≥ 2"; the same argument holds, and display (6.7) uses it, for
every block, so it is stated for every `j : ℕ`. -/
theorem shelling_bound (s : ℕ → ℝ) (hs : Antitone s) (h0 : ∀ i, 0 ≤ s i) (ℓ : ℕ) (hℓ : 0 < ℓ)
(j : ℕ) :
Real.sqrt (∑ i ∈ Finset.Ico ((j + 1) * ℓ) ((j + 2) * ℓ), s i ^ 2) ≤
(1 / Real.sqrt ℓ) * ∑ i ∈ Finset.Ico (j * ℓ) ((j + 1) * ℓ), s i := by sorry
end IRLSM.RIP
Source
Fornasier, Rauhut, Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, arXiv:1010.2471v4 (2011), proof of Proposition 6.8, p. 19, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.