科研之友
微信
新浪微博
Facebook
分享链接
摘要
Exact reconstruction of a sparse signal for an under-determined linear system using the to-measure is, in general, an NP-hard problem. The most popular approach is to relax the to-optimization problem to an l(1)-approximation. However, the strength of this convex approximation relies upon rigid properties on the system, which are not verifiable in practice. Greedy algorithms have been proposed in the past to speed up the optimization of the l(1) problem, but their computational efficiency comes at the expense of a larger error. In an effort to control error and complexity, this paper goes beyond the l(1)-approximation by growing neighborhoods of the l(1)-solution that moves towards the optimal solution. The size of the neighborhood is tunable depending on the computational resources. The proposed algorithm, termed Approximate Kernel RecONstruction (AKRON), yields significantly smaller errors than current greedy methods with a controllable computational cost. By construction, the error of AKRON is smaller than or to equal the l(1)-solution. AKRON enjoys all the error bounds of l(1) under the restricted isometry property condition. We benchmarked AKRON on simulated data from several under-determined systems, and the results show that AKRON can significantly improve the reconstruction error with slightly more computational cost than solving the l(1) problem directly.
- 出版日期2018-3
