On the optimality of the backward greedy algorithm for the subset selection problem

The following linear inverse problem is considered: Given a full column ran k m x n data matrix A and a length m observation vector b, find the best le ast-squares solution to Ax = b with at most r <n nonzero components. The ba ckward greedy algorithm computes a sparse solution to Ax = b by removing gr eedily columns from A until r columns are left. A simple implementation bas ed on a QR downdating scheme using Givens rotations is described. The backw ard greedy algorithm is shown to be optimal for the subset selection proble m in the sense that it selects the "correct" subset of columns from A if th e perturbation of the data vector b is small enough. The results generalize to any other norm of the residual.