Fast Implementation of ℓ ¹-Greedy Algorithm

We present an algorithm for finding sparse solutions of the system of linear equations A x = b with the rectangular matrix A of size n ×N, where n < N. The algorithm basic constructive block is one iteration of the standard interior-point linear programming algorithm. To find the sparse representation we modify (reweight) each iteration in the spirit of Petukhov (Fast implementation of orthogonal greedy algorithm for tight wavelet frames. Signal Process. 86, 471–479 (2006)). However, the weights are selected according to the ℓ ¹-greedy strategy developed in Kozlov and Petukhov (Sparse solutions for underdetermined systems of linear equations. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, pp. 1243–1259. Springer, Berlin (2010)). Our algorithm combines computational complexity close to plain ℓ ¹-minimization with the significantly higher efficiency of the sparse representations recovery than the reweighted ℓ ¹-minimization (Candes et al.: Enhancing sparsity by reweighted ℓ ₁ minimization. J. Fourier Anal. Appl. 14, 877–905 (2008) (special issue on sparsity)), approaching the capacity of the ℓ ¹-greedy algorithm.