Recent work on dimensionality reduction using Cauchy random projections has emerged for applications where ℓ 1 distance preservation is preferred. An original sparse signal b ϵ ℝ n is multiplied by a Cauchy random matrix R ϵ ℝ n× k (k≪ n), resulting in a projected vector c ϵ ℝ k. Two approaches for fast recover of b from the Cauchy vector c are proposed. The two algorithms are based on a regularized coordinate-descent Myriad regression using both ℓ 0 and convex relaxation as sparsity inducing terms. The key element is to start, in the first