Article
AKRON: An Algorithm for Approximating Sparse Kernel Reconstruction
Signal Processing
(2018)
Abstract
Exact reconstruction of a sparse signal for an under-determined linear system using the ℓ0-measure is, in general, an NP-hard problem. The most popular approach is to relax the ℓ0-optimization problem to an ℓ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 ℓ1problem, 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 ℓ1-approximation by growing neighborhoods of the ℓ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 ℓ1-solution. AKRON enjoys all the error bounds of ℓ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 ℓ1 problem directly.
Disciplines
Publication Date
January 3, 2018
DOI
10.1016/j.sigpro.2017.10.020
Citation Information
Gregory Ditzler, Nidhal Carla Bouaynaya and Roman Shterenberg. "AKRON: An Algorithm for Approximating Sparse Kernel Reconstruction" Signal Processing Vol. 144 (2018) p. 265 - 270 Available at: http://works.bepress.com/nidhal-bouaynaya/3/