I problemet med adaptiv komprimerad avkänning, vill man uppskatta en ungefärlig k-sparse vektor x R n från m linjära mätningar A 1 x, A 2 x,. .., A m x, där A i kan väljas baserat på resultaten A 1 x,. .., A i‐1 x av tidigare mätningar. Målet är att mata ut en vektorx för vilken sannolikheten är minst 2/3, där C > 0 är en approximationsfaktor. Indyk, Price and Woodruff (FOCS'11) gav en algoritm för p = q = 2 för C = 1 + med O(k/ )loglog(n/k)) mätningar och O(log * (k)log(n) rundor av anpassningsförmåga. Vi förbättrar först deras gränser, få ett schema med ) mätningar och O(log * (k)loglog(n) rundor, samt ett schema med O(k/ ) · loglog(n log(n/k))) mätningar och en optimal O(log(n) rundor. Vi tillhandahåller sedan nya adaptiva komprimerade avkänningssystem med förbättrade gränser för (p, p) för varje 0 < p < 2. Vi visar att förbättringen från O(k log (n/k)) mätningar till O(k log (n/k)) mätningar i adaptiv inställning kan fortsätta med ett bättre -beroende för andra värden av p och q. Till exempel, när (p, q) = (1, 1), vi få O( k ε · log n log 3 ( 1 )) mätningar. Vi får nästan matchande lägre gränser, visar våra algoritmer är nära optimal. Längs vägen får vi också de första nästan optimala gränserna för (p, p) system för varje 0 < p < 2 även i den icke-adaptiva inställningen.
Detta förbättrades genom REF på två ojämförbara sätt: antingen kan R förbättras till O(log log n) eller så kan provets komplexitet förbättras till O( log log 1 k + k log n), delning n och i provets komplexitet.
Improved Algorithms for Adaptive Compressed Sensing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}