  Sparse recovery and subset selection are fundamental problems in varied
communities, including signal processing, statistics and machine learning.
Herein, we focus on an important greedy algorithm for these problems: Backward
Stepwise Regression. We present novel guarantees for the algorithm, propose an
efficient, numerically stable implementation, and put forth Stepwise Regression
with Replacement (SRR), a new family of two-stage algorithms that employs both
forward and backward steps for compressed sensing problems. Prior work on the
backward algorithm has proven its optimality for the subset selection problem,
provided the residual associated with the optimal solution is small enough.
However, the existing bounds on the residual magnitude are NP-hard to compute.
In contrast, our main theoretical result includes a bound that can be computed
in polynomial time, depends chiefly on the smallest singular value of the
matrix, and also extends to the method of magnitude pruning. In addition, we
report numerical experiments highlighting crucial differences between forward
and backward greedy algorithms and compare SRR against popular two-stage
algorithms for compressed sensing. Remarkably, SRR algorithms generally
maintain good sparse recovery performance on coherent dictionaries. Further, a
particular SRR algorithm has an edge over Subspace Pursuit.
