{"id":"palomar/PALOMAR-2026-11-16-000025","url":"https://github.com/chinmayhegde/fourier-tree-rip-palomar/tree/d35425b021e53164165e9916fc26f80cec6303a1","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-16-000025-v1.json","repo":"https://github.com/chinmayhegde/fourier-tree-rip-palomar","tags":["math.NA","cs.IT","msc:42B05","msc:94A12"],"score":0,"title":"A Quadratic Lower Bound for Fourier RIP with Tree-Structured Sparsity","trust":"high","domain":"math.NA","source":"palomar","authors":["Chinmay Hegde"],"reviews":0,"subject":"math.NA","summary":"Lean 4 formalization of an explicit lower bound for uniformly row-subsampled discrete Fourier transforms acting on canonical binary-heap tree-sparse vectors. With constant distortion, at least half of frequency sequences violate tree-RIP when 20000 m <= k min(k, log_2(N/k)), with an explicit quadratic corollary. The proof uses broom supports, Fejer-kernel concentration, simultaneous Diophantine approximation, and finite counting. A full-DFT isometry theorem checks the normalization and nonvacuity of the definitions.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-16","reactions":{},"formalized":true,"formalizes":[{"title":"A Quadratic Lower Bound for Fourier RIP with Tree-Structured Sparsity","identifier":"","relationship":"formalizes"}]}