For-All Sparse Recovery in Near-Optimal Time
For-All Sparse Recovery in Near-Optimal Time
复制标题
在接近最佳的时间内实现所有稀疏恢复
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Strauss
中科院分区：
文献类型：
--
作者：
A. Gilbert;Yi Li;E. Porat;M. Strauss
ℓ1规范中的稀疏恢复系统由参数k，ε，n组成； n; ，必须满足“ xˆ-x”1≤（1+ε）” x-xk” 1。 ，用于所有信号x Porat and Strauss [2012]的现有sublinear算法使用O（ε -3Klog（n/k））测量值，并在时间O（K1 -αNαα）中运行任何常数α> 0。在本文中，我们改善了测量的数量到O（ε-2Klog（n/k）），与最佳现有上限（通过超级线性算法实现）匹配，并且运行时与O（k1+βpoly（log n，1/ε）），并具有适度k⩽N1 -α和ε⩽（log K/log）的限制n）γ对于任何常数α，β，γ> 0。当k⩽log cn在某些c> 0时，运行时会降低到o（kpoly（n，1/ε））。具有M = O（k/εlog（n/k）的近似恢复系统（（log n/log k）γ + 1/ε））测量该算法的整体体系结构与Porat和Strauss [2012》 [ ]因为我们反复使用弱恢复系统（具有不同参数）来获得顶级恢复算法。哈希阶段。 strauss [2012]，其中的编码仅是消息M'i的一部分。恢复较长的消息M'i的部分，然后解码到原始消息MI，同时确保可以检测到校正和/或更正恢复算法。 Indyk等。
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 - xk‖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(ε−3klog (N/k)) measurements and runs in time O(k1 − αNα) for any constant α > 0. In this article, we improve the number of measurements to O(ε − 2klog (N/k)), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O(k1+βpoly(log N,1/ε)), with a modest restriction that k ⩽ N1 − α and ε ⩽ (log k/log N)γ for any constants α, β, γ > 0. When k ⩽ log cN for some c > 0, the runtime is reduced to O(kpoly(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 mi, 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 mi, 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 {mi} are independent of the hashing, which enables us to obtain a better result.