Dimensionality reduction via linear random projections are used in numerous applications including data streaming, information retrieval, data mining, and compressive sensing (CS). While CS has traditionally relied on normal random projections, corresponding to ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> distance preservation, a large body of work has emerged for applications where ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> approximate distances may be preferred. Dimensionality reduction in ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> use Cauchy random projections that multiply the original data matrix B ∈ 葷 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D×n</sup> with a Cauchy random matrix R ∈ 葷 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n×k</sup> (k « min(n,D)), resulting in a projected matrix C ∈ 葷 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D×k</sup> . This paper focuses on developing signal reconstruction algorithms from Cauchy random projections, where the large suite of reconstruction algorithms developed in compressive sensing perform poorly due to the lack of finite second-order statistics in the projections. In particular, a set of regularized coordinate-descent Myriad regression based reconstruction algorithms are developed using, both l <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> and Lorentzian norms as sparsity inducing terms. The l <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> -regularized algorithm shows superior performance to other standard approaches. Simulations illustrate and compare accuracy of reconstruction.