Abstract-Målet med (stabil) sparsam återhämtning är att återställa en k-sparse approximation x * av en vektor x från linjära mätningar av x. Särskilt är målet att återhämta sig för vissa konstant C och norm parametrar p och q. Det är känt att för p = q = 1 eller p = q = 2, denna uppgift kan utföras med hjälp av m = O(k log(n/k)) icke-adaptiva mätningar [3] och att denna gräns är tight [9], [12], [28]. I detta papper visar vi att om man tillåts utföra mätningar som är adaptiva kan antalet mätningar minskas avsevärt. Speciellt för C = 1+ och p = q = 2 visar vi rundor. Detta är en signifikant förbättring jämfört med bästa möjliga icke adaptiva bindning. • Ett schema med m = O( 1 k log(k/ ) + k log( n/ k)) mätningar som använder två rundor. Detta förbättras över bästa möjliga icke-adaptiva bundet. Såvitt vi vet är detta de första resultaten av denna typ.
På litteraturens glesa återvinningssida gav REF en fullt adaptiv algoritm med hjälp av O( 1 k log n) mätningar utförda i R = O(log log n log * k) rundor.
On the Power of Adaptivity in Sparse Recovery
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}