Abstrakt. Vi ger en ny explicit konstruktion av n × N matriser som uppfyller den begränsade Isometry Property (RIP). Nämligen, för vissa ε > 0, stora N och alla n som uppfyller N 1−ε ≤ n ≤ N, konstruerar vi RIP matriser av ordningen k ≥ n 1/2+ε och konstant ε = n −ε. Detta övervinner den naturliga barriären k = O(n 1/2 ) för bevis baserade på liten samstämmighet, som används i alla tidigare explicita konstruktioner av översynsperioden matriser. Viktiga ingredienser i vårt bevis är nya uppskattningar för summor i produktuppsättningar och för exponentiella summor med produkter av uppsättningar med särskild additiv struktur. Vi ger också en konstruktion av uppsättningar av n komplexa tal vars k-th ögonblick är jämnt små för 1 ≤ k ≤ N (Turáns effektsumma problem), vilket förbättrar vid kända explicita konstruktioner när (log N ) 1+o(1) ≤ n ≤ (log N ) 4+o(1). Denna senare konstruktion ger elementära explicita exempel på n × N matriser som uppfyller översynsperioden och vars kolumner utgör en ny sfärisk kod; för dessa problem parametrarna överensstämmer nära de av befintliga konstruktioner i intervallet (log N ) 1+o(1) ≤ n ≤ (log N ) 5/2+o(1).
Med hjälp av nya uppskattningar av summor i produktuppsättningar och för exponentiella summor med produkter av satser med särskild tillsatsstruktur kunde Bourgain, Dilworth, Ford, Konyagin och Kutzarva REF övervinna
Explicit constructions of RIP matrices and related problems
{'venue': 'Duke Math. J. 159, no. 1 (2011), 145-185', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}