A popular approach for recovering the support of \({\mbox{$\theta $}}^*\)  is using an \(\ell ^1\)  regularized quadratic programming problem, also known as the Least Absolute Shrinkage and Selection Operator (LASSO) [1]}. The LASSO is cast as a convex problem, and can be solved using efficient optimization schemes [2]}, [3]}. Several authors have introduced iterative algorithms improving the support recovery capabilities of the LASSO, these include: Iterative Re-weighted Least Squares (IRLS) [4]}, Iteratively Re-weighted \(\ell ^1\)  minimization (IRL1) [5]}, and Iterative Support Detection (ISD) [6]}. Other solutions for support recovery include greedy algorithms such as Orthogonal Matching Pursuit (OMP) [7]}, and its extensions [8]}, [9]}, [10]}, or non convex schemes such as the Trimmed LASSO (TL) [11]}, smoothly clipped absolute deviation (SCAD) [12]}, or stochastic gates (STG) [13]}. For a more complete survey of the existing methodologies, we refer the reader to [14]}, [15]}, [16]}, [17]}.
Following the approach of Randomly Aggregated Least Squares (RAWLS) proposed by the authors in [18]}, we introduce Refined Least Squares (RLS), a procedure for estimating the support of \({\mbox{$\theta $}}^*\)  based on the noisy vector \({\mbox{$y$}}\)  and the observations matrix \({\mbox{$X$}}\) . Our algorithm is greedy, relying on estimating the support (and sign) of one coefficient at a time. We demonstrate that Refined Least Squares (RLS) effectively recovers the support, specifically in the low information regime where \(N\)  is much smaller than \(D\) , the regime where the noise is high and there is a large number of active coefficients (\(k\) ).
