For-All Sparse Recovery in Near-Optimal Time
| العنوان: | For-All Sparse Recovery in Near-Optimal Time |
|---|---|
| المؤلفون: | Martin J. Strauss, Ely Porat, Yi Li, Anna C. Gilbert |
| المصدر: | ACM Transactions on Algorithms. 13:1-26 |
| بيانات النشر: | Association for Computing Machinery (ACM), 2017. |
| سنة النشر: | 2017 |
| مصطلحات موضوعية: | FOS: Computer and information sciences, Sublinear function, Deterministic algorithm, Computer Science - Information Theory, Information Theory (cs.IT), E.4, Hash function, List decoding, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Binary logarithm, 01 natural sciences, Upper and lower bounds, Combinatorics, Mathematics (miscellaneous), 010201 computation theory & mathematics, Norm (mathematics), Computer Science - Data Structures and Algorithms, F.2.2, 0202 electrical engineering, electronic engineering, information engineering, Expander graph, Data Structures and Algorithms (cs.DS), Mathematics |
| الوصف: | An approximate sparse recovery system in ℓ 1 norm consists of parameters k , ϵ, N ; an m -by- N measurement Φ; and a recovery algorithm R . Given a vector, x , the system approximates x by xˆ = R (Φ x ), which must satisfy ‖ xˆ- x ‖ 1 ≤ (1+ϵ)‖ x - x k ‖ 1 . We consider the “for all” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x . The best existing sublinear algorithm by Porat and Strauss [2012] uses O (ϵ −3 k log ( N / k )) measurements and runs in time O ( k 1 − α N α ) for any constant α > 0. In this article, we improve the number of measurements to O (ϵ − 2 k log ( N / k )), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O ( k 1+β poly(log N ,1/ϵ)), with a modest restriction that k ⩽ N 1 − α and ϵ ⩽ (log k /log N ) γ for any constants α, β, γ > 0. When k ⩽ log c N for some c > 0, the runtime is reduced to O ( k poly( N ,1/ϵ)). With no restrictions on ϵ, we have an approximation recovery system with m = O ( k /ϵlog ( N / k )((log N /log k ) γ + 1/ϵ)) measurements. The overall architecture of this algorithm is similar to that of Porat and Strauss [2012] in that we repeatedly use a weak recovery system (with varying parameters) to obtain a top-level recovery algorithm. The weak recovery system consists of a two-layer hashing procedure (or with two unbalanced expanders for a deterministic algorithm). The algorithmic innovation is a novel encoding procedure that is reminiscent of network coding and that reflects the structure of the hashing stages. The idea is to encode the signal position index i by associating it with a unique message m i , which will be encoded to a longer message m ′ i (in contrast to Porat and Strauss [2012] in which the encoding is simply the identity). Portions of the message m ′ i correspond to repetitions of the hashing, and we use a regular expander graph to encode the linkages among these portions. The decoding or recovery algorithm consists of recovering the portions of the longer messages m ′ i and then decoding to the original messages m i , all the while ensuring that corruptions can be detected and/or corrected. The recovery algorithm is similar to list recovery introduced in Indyk et al. [2010] and used in Gilbert et al. [2013]. In our algorithm, the messages { m i } are independent of the hashing, which enables us to obtain a better result. |
| تدمد: | 1549-6333 1549-6325 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bec313ae87388ea36fe947d83a959d52 https://doi.org/10.1145/3039872 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....bec313ae87388ea36fe947d83a959d52 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 15496333 15496325 |
|---|